哪种排序算法在添加元素时使用的比较次数最少？
Which sorting algorithm uses the fewest number of comparisons while elements are being added?
我有很多音乐，我想按从最不喜欢到最喜欢的顺序排列它们（这需要很多天）。我想一次比较两个音乐文件（2 向比较）。我看到一些关于算法的问题，比较最少。但要注意的是（因为这是一个漫长的过程）我想向 collection 添加新音乐，在那种情况下我不想重新开始对所有内容进行排序（因此创建了更多的比较步骤）。
哪种算法的比较次数最少，同时仍允许添加需要比较的新元素？
我对仅对少数项目进行最少数量的比较不感兴趣。假设至少有 1000 件商品。
如果算法支持 N-way 比较（其中 N > 2），则奖励，以防我想比较图片。
编辑：比较两首歌是一个手动过程，通过听它们（因此很慢），需要排序算法在最少的比较中对它们进行排名
您的问题似乎分为两个阶段。第一阶段是对您已有的所有歌曲进行排序，第二阶段是将新歌曲一首一首地插入到已经排序的顺序中。
第一阶段是标准排序算法所做的。在这个阶段，输入是一个假定完全无序的数组，所有的排序都是一次性完成的。您希望使用尽可能少的比较次数来执行此操作。
这个问题没有完美的答案；没有已知的排序算法对所有输入使用可证明的最小比较次数。信息论给出 n log2 n - 1.443 n + O(log n) 作为平均比较次数的理论下限，但尚未达到此下限。
目前已知的最接近上述界限的排序算法是merge-insertion sort（也称为 Ford–Johnson 算法）及其变体。合并插入排序平均执行大约 n log₂ n - 1.415 n 次比较，非常接近到理论界。对于 1024 个项目，您可能会进行类似 ~8,790 次比较，而理论界限类似于 ~8,760。
根据 this other Stack Overflow answer 截至 2018 年 12 月，none 改进合并插入排序的算法是 "freely documented"，其中我的意思是这些改进的算法只出现在学术论文中。更多 public 信息可用于合并插入排序，并且变体没有太大的改进空间，所以我建议使用这个算法而不是涉足学术文献；除非你的 n 大得多，否则没有什么好处。
第二阶段与排序算法解决的问题不同。在此阶段，您需要一个 "online" 算法，允许将新项目添加到当前排序顺序中。
你不能用少于 ⌈log₂ (n + 1)⌉ 每次插入的比较，因为有 n + 1新项目在当前订单中的位置，每次比较都会提供一位信息。
binary search algorithm works to find the correct position in a sorted array; or you could use a balanced binary search tree数据结构。无论哪种方式，每次插入都将使用最佳比较次数来实现。使用二叉搜索树的好处是插入总体上需要O(log n)时间；插入排序数组需要 O(log n) 比较，但 O(n) 时间在数组中移动其他元素。
假设您的音乐库没有顺序，合并排序是最好的排序算法。虽然在进行合并排序时添加元素并不那么容易。
我认为最好的选择是像 2-3 tree 或红黑树这样的深度受限搜索树。我个人建议使用 2-3 树，因为红黑是它的变体，每个节点的复杂度较低，但最小深度范围更差。
使用这棵树，您可以根据维基百科上明确描述的规则简单地开始向其中添加歌曲，并且您添加的每首歌曲都将按排序顺序排列。这还有一个额外的好处，当插入一首歌时，它会被连续多次比较，因此它会在你的记忆中是新鲜的，所以你可能不需要每次比较都听它。
此方法一次对您的歌曲进行排序，因此如果出现一首您希望立即排名的新歌曲，您可以将其添加到其余未排序的歌曲之前。
您可能需要编写一个程序来帮助您维护顺序和树结构。我能想到的唯一手动方法是使用嵌套文件夹作为节点，这使得添加和重新排列树成为可能。它确实使查询有点麻烦，具体取决于您想要做什么。
非比较排序算法，如radix sort，可以对数据进行0次比较排序！这些不像合并或插入排序等比较排序算法那么通用，但如果您的数据满足必要的要求，它们可以获得更好的运行时间。
本质上，如果您了解数据的 分布 ，则可以比 O(n log n) 更快地进行排序。例如，如果您正在对 n 个数字进行排序，并且知道它们是 1 和 N 之间的整数，您可以使用 counting sort 将它们排序为 O(n + N)。您也可以为 O(1) 迭代添加元素。
将此应用于音乐排名问题更具挑战性（歌曲不是整数），但您可以做一个变体 bucket sort，首先将音乐分为 10% "tiers"：顶部 0-10%、10-20%、20-30%、...、90-100%（即底部）。然后，您可以递归地将桶排序应用于那些（前 0-1%、1-2% 等）或应用标准排序算法。最终，您需要进行标准的比较排序。这种方法，与仅使用比较排序相比，将减少比较次数log(n)/log(n/B)，其中 B 是桶的数量。对于 100 个桶和 10000 首歌曲，这是 2 个减少因子。
另一种节省比较的方法是使用改进的二分搜索进行插入排序（用于初始排序和后续插入）：而不是设置在 0 和 n 处进行二进制搜索，将它们设置为基于您确定最终结果的直觉的值，例如 0 和 n/10，如果它绝对在您的前 10%。执行此操作的粒度越细，需要的比较就越少。
注意： 对于桶排序和修改后的二分查找，如果你错了，你需要做额外的比较来纠正你的错误。
最后一句话：这个问题假设存在是一个正确的排名并且它可以通过比较来实现。如果你有循环偏好，比如a > b, b > c, and c > a，a la rock-paper-scissors，那么就无法构建排名。算法仍会完成，但结果列表将不一致。
我有很多音乐，我想按从最不喜欢到最喜欢的顺序排列它们（这需要很多天）。我想一次比较两个音乐文件（2 向比较）。我看到一些关于算法的问题，比较最少。但要注意的是（因为这是一个漫长的过程）我想向 collection 添加新音乐，在那种情况下我不想重新开始对所有内容进行排序（因此创建了更多的比较步骤）。
哪种算法的比较次数最少，同时仍允许添加需要比较的新元素？
我对仅对少数项目进行最少数量的比较不感兴趣。假设至少有 1000 件商品。
如果算法支持 N-way 比较（其中 N > 2），则奖励，以防我想比较图片。
编辑：比较两首歌是一个手动过程，通过听它们（因此很慢），需要排序算法在最少的比较中对它们进行排名
您的问题似乎分为两个阶段。第一阶段是对您已有的所有歌曲进行排序，第二阶段是将新歌曲一首一首地插入到已经排序的顺序中。
第一阶段是标准排序算法所做的。在这个阶段，输入是一个假定完全无序的数组，所有的排序都是一次性完成的。您希望使用尽可能少的比较次数来执行此操作。
这个问题没有完美的答案；没有已知的排序算法对所有输入使用可证明的最小比较次数。信息论给出 n log2 n - 1.443 n + O(log n) 作为平均比较次数的理论下限，但尚未达到此下限。
目前已知的最接近上述界限的排序算法是merge-insertion sort（也称为 Ford–Johnson 算法）及其变体。合并插入排序平均执行大约 n log₂ n - 1.415 n 次比较，非常接近到理论界。对于 1024 个项目，您可能会进行类似 ~8,790 次比较，而理论界限类似于 ~8,760。
根据 this other Stack Overflow answer 截至 2018 年 12 月，none 改进合并插入排序的算法是 "freely documented"，其中我的意思是这些改进的算法只出现在学术论文中。更多 public 信息可用于合并插入排序，并且变体没有太大的改进空间，所以我建议使用这个算法而不是涉足学术文献；除非你的 n 大得多，否则没有什么好处。
第二阶段与排序算法解决的问题不同。在此阶段，您需要一个 "online" 算法，允许将新项目添加到当前排序顺序中。
你不能用少于 ⌈log₂ (n + 1)⌉ 每次插入的比较，因为有 n + 1新项目在当前订单中的位置，每次比较都会提供一位信息。
binary search algorithm works to find the correct position in a sorted array; or you could use a balanced binary search tree数据结构。无论哪种方式，每次插入都将使用最佳比较次数来实现。使用二叉搜索树的好处是插入总体上需要O(log n)时间；插入排序数组需要 O(log n) 比较，但 O(n) 时间在数组中移动其他元素。
假设您的音乐库没有顺序，合并排序是最好的排序算法。虽然在进行合并排序时添加元素并不那么容易。
我认为最好的选择是像 2-3 tree 或红黑树这样的深度受限搜索树。我个人建议使用 2-3 树，因为红黑是它的变体，每个节点的复杂度较低，但最小深度范围更差。
使用这棵树，您可以根据维基百科上明确描述的规则简单地开始向其中添加歌曲，并且您添加的每首歌曲都将按排序顺序排列。这还有一个额外的好处，当插入一首歌时，它会被连续多次比较，因此它会在你的记忆中是新鲜的，所以你可能不需要每次比较都听它。
此方法一次对您的歌曲进行排序，因此如果出现一首您希望立即排名的新歌曲，您可以将其添加到其余未排序的歌曲之前。
您可能需要编写一个程序来帮助您维护顺序和树结构。我能想到的唯一手动方法是使用嵌套文件夹作为节点，这使得添加和重新排列树成为可能。它确实使查询有点麻烦，具体取决于您想要做什么。
非比较排序算法，如radix sort，可以对数据进行0次比较排序！这些不像合并或插入排序等比较排序算法那么通用，但如果您的数据满足必要的要求，它们可以获得更好的运行时间。
本质上，如果您了解数据的 分布 ，则可以比 O(n log n) 更快地进行排序。例如，如果您正在对 n 个数字进行排序，并且知道它们是 1 和 N 之间的整数，您可以使用 counting sort 将它们排序为 O(n + N)。您也可以为 O(1) 迭代添加元素。
将此应用于音乐排名问题更具挑战性（歌曲不是整数），但您可以做一个变体 bucket sort，首先将音乐分为 10% "tiers"：顶部 0-10%、10-20%、20-30%、...、90-100%（即底部）。然后，您可以递归地将桶排序应用于那些（前 0-1%、1-2% 等）或应用标准排序算法。最终，您需要进行标准的比较排序。这种方法，与仅使用比较排序相比，将减少比较次数log(n)/log(n/B)，其中 B 是桶的数量。对于 100 个桶和 10000 首歌曲，这是 2 个减少因子。
另一种节省比较的方法是使用改进的二分搜索进行插入排序（用于初始排序和后续插入）：而不是设置在 0 和 n 处进行二进制搜索，将它们设置为基于您确定最终结果的直觉的值，例如 0 和 n/10，如果它绝对在您的前 10%。执行此操作的粒度越细，需要的比较就越少。
注意： 对于桶排序和修改后的二分查找，如果你错了，你需要做额外的比较来纠正你的错误。
最后一句话：这个问题假设存在是一个正确的排名并且它可以通过比较来实现。如果你有循环偏好，比如a > b, b > c, and c > a，a la rock-paper-scissors，那么就无法构建排名。算法仍会完成，但结果列表将不一致。