algorithm - 在添加元素时，哪种排序算法使用的比较次数最少？

Question

我有很多音乐，我想将它们从最不喜欢到最喜欢排列（这需要很多天）。我想一次比较两个音乐文件（双向比较）。我看到了一些比较最少的算法问题。但问题是（因为这是一个漫长的过程）我想将新音乐添加到收藏中，在这种情况下我不想重新开始对所有内容进行排序（从而创建更多的比较步骤）。

哪种算法具有最少的比较量，同时仍允许添加也需要比较的新元素？

我对仅仅几个项目的最少比较不感兴趣。假设最少 1000 个项目。

如果算法支持 N 路比较（其中 N > 2），以防我想比较图片，则奖励。

编辑：比较两首歌曲是一个手动过程，通过听它们（因此很慢），需要排序算法以最少的比较次数对它们进行排名

标签： algorithmsortingoptimizationcomparison

Answer 1

您的问题似乎有两个阶段。第一阶段是对您已经拥有的所有歌曲进行排序，第二阶段是将新歌曲一一插入到已经排序的顺序中。

---

第一阶段是标准排序算法所做的事情。在这个阶段，输入是一个假定完全无序的数组，所有的排序都是一次性完成的。您希望使用尽可能少的比较次数来执行此操作。

这个问题没有完美的答案；没有已知的排序算法对所有输入使用可证明的最小比较次数。信息论给出了n log₂ n - 1.443 n + O(log n ) 作为平均比较次数的理论下限，但这个界限尚未实现。

目前已知的最接近上述界限的排序算法是合并插入排序（也称为福特-约翰逊算法）及其变体。合并插入排序平均执行大约n log₂ n - 1.415 n比较，这非常接近理论界限。对于 1024 个项目，您可能会进行大约 8,790 次比较，其中理论界限约为 8,760。

根据截至 2018 年 12 月的另一个 Stack Overflow 答案，没有一个改进合并插入排序的算法是“免费记录的”，我认为这些改进的算法只在学术论文中出现。更多公共信息可用于合并插入排序，并且变体没有太大改进空间，因此我建议使用该算法而不是涉足学术文献；除非你的n大得多，否则几乎没有什么好处。

---

第二阶段是与排序算法解决的问题不同的问题。在这个阶段，您需要一个“在线”算法，该算法允许将新项目添加到当前排序顺序中。

您不能在每次插入少于 ⌈log₂ ( n + 1)⌉ 比较的情况下执行此操作，因为新项目在当前顺序中可能属于n + 1 个位置，并且每次比较都会提供一位信息。

二分搜索算法用于在已排序的数组中找到正确的位置；或者您可以使用平衡的二叉搜索树数据结构。无论哪种方式，每次插入都将使用最佳比较次数来实现。使用二叉搜索树的优点是插入需要 O(log n ) 时间；插入排序数组需要 O(log n ) 比较，但需要 O( n ) 时间来移动数组中的其他元素。