一尘不染

如何使用最少的写入次数对数组进行排序?

algorithm

我的朋友在面试中被问到一个问题:

面试官给了他一系列未排序的数字,并要求他进行排序。限制是写入次数应最小化,而读取次数没有限制。


阅读 225

收藏
2020-07-28

共1个答案

一尘不染

如果数组较短(即少于约100个元素),并且还希望减少写入次数,则选择排序通常是最佳选择。

从维基百科:

另一个主要区别是选择排序始终执行Θ(n)交换,而插入排序通常在平均和最坏情况下执行Θ(n
2)交换。因为交换需要写入数组,所以如果写入内存比读取要昂贵得多,则选择排序是更可取的。如果物品很大但钥匙很小,通常就是这种情况。
写入时间至关重要的另一个示例是存储在EEPROM或闪存中的阵列。 没有其他算法可以减少数据移动。

对于更大的数组/列表,Quicksort和朋友将提供更好的性能,但与选择排序相比,可能仍需要更多写入。

如果您感兴趣,这是一个很棒的排序可视化站点,您可以观看特定的排序算法完成其工作,还可以相互“竞争”不同的排序算法。

2020-07-28