如何排序使用写入最小数量的数组？ [英] How to sort an array using minimum number of writes?

问题描述

我的朋友问了一个问题，在他的采访：​​

My friend was asked a question in his interview:

面试官给了他未分类的数字数组，请他进行排序。的限制是写入次数应该最小化而有上的读取的数目没有限制。

The interviewer gave him an array of unsorted numbers and asked him to sort. The restriction is that the number of writes should be minimized while there is no limitation on the number of reads.

推荐答案

如果数组较短（即低于约100元）一个的选择排序往往是最好的选择，如果你也想减少写入的次数。

If the array is shorter (ie less than about 100 elements) a Selection sort is often the best choice if you also want to reduce the number of writes.

从维基百科：

另一个关键的区别是，   选择排序始终执行Θ（N）   掉期交易，而插入排序执行   Θ（N ² ）交换的平均和最差   案例。由于互换要求写作   到阵列中，选择排序是   preferable如果要写入内存   显著比更贵   阅读。这通常是当壳体   该项目是巨大的​​，但关键是   小。 另一个例子，写作   时间是一个数组存储的关键   在EEPROM或闪存。不存在其他   算法较少的数据移动。

Another key difference is that selection sort always performs Θ(n) swaps, while insertion sort performs Θ(n²) swaps in the average and worst cases. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small. Another example where writing times are crucial is an array stored in EEPROM or Flash. There is no other algorithm with less data movement.

对于较大的阵列/列出的快速排序和朋友将提供更好的性能，但仍然有可能需要比选择排序更写。

For larger arrays/lists Quicksort and friends will provide better performance, but may still likely need more writes than a selection sort.

如果您有兴趣这是一个梦幻般的排序可视化网站，让您观看特定的排序算法做自己的工作，还有种族不同的排序算法对立起来。

If you're interested this is a fantastic sort visualization site that allows you to watch specific sort algorithms do their job and also "race" different sort algorithms against each other.

这篇关于如何排序使用写入最小数量的数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！