添加元素时，哪种排序算法使用的比较次数最少? [英] Which sorting algorithm uses the fewest number of comparisons while elements are being added?

问题描述

我有很多音乐，我想将它们从最不喜欢的音乐排到最喜欢的音乐(这需要很多天).我想一次比较两个音乐文件(2向比较).我看到了一些算法比较最少的问题.但是要注意的是(由于这是一个漫长的过程)，我想向收藏中添加新音乐，在这种情况下，我不想从所有内容的排序开始(因此要创建更多的比较步骤).

I have a lot of music and i want to rank them from least favorite to favorite (this will take many days). I would like to compare two music files at a time (2-way comparison). I saw some questions on algorithms with the fewest comparisons. But the catch is that (since it's a long process) i want to add new music to the collection and in that case i don't want to start over sorting everything (thus creating a lot more comparison steps).

哪个算法的比较次数最少，同时仍然允许添加也需要比较的新元素?

Which algorithm has the least amount of comparisons while still allowing new elements to be added which need to be compared too?

我对最少的几个项目的比较不感兴趣.假设最少有1000件.

I'm not interested in least amount of comparisons for just a few items. Let's say 1000 items minimum.

如果该算法支持N次比较(其中N> 2)，请在我想比较图片的情况下获得奖励.

Bonus if the algorithm supports N-way comparison (where N > 2) in case i would like to compare pictures instead.

比较两首歌曲是人工过程(通过缓慢聆听)，因此需要一种排序算法，以便以最少的比较量对它们进行排名

comparing two songs are a manual process by listening to them (thus slowly), the sorting algorithm is needed to rank them in the fewest amount of comparisons

推荐答案

一种非比较排序算法，例如基数排序，可以对0个比较的数据进行排序！这些不像合并或插入排序之类的比较排序算法那样通用，但是如果您的数据满足必要的要求，则运行时会更好.

A non-comparative sorting algorithm, like radix sort, can sort data with 0 comparisons! These are not as generic as comparative sorting algorithms like merge or insertion sort, but can get far better runtime if your data meets the necessary requirements.

从本质上讲，如果您了解数据的分布，则排序速度可以比 O(n log n)快.例如，如果您要对 n 个数字进行排序，并且知道它们是 1 和 N 之间的整数，则可以使用

Essentially, if you have knowledge about the distribution of your data, you can sort faster than O(n log n). For instance, if you are sorting n numbers, and know that they are integers between 1 and N, you can use counting sort to sort them in O(n + N). You can iteratively add elements for O(1) as well.

将其应用于您的音乐排名问题更具挑战性(歌曲不是整数)，但是您可以对 log(n)/log(n/B)，其中 B 是桶数.对于100个存储桶和10000首歌曲，这减少了2倍.

Applying this to your problem of ranking music is more challenging (songs are not integers), but you can you do a variation of bucket sort where you first bin your music into, say, 10% "tiers": top 0-10%, 10-20%, 20-30%, ..., 90-100% (i.e., the bottom). Then you can either recursively apply bucket sort to those (top 0-1%, 1-2%, etc.) or apply standard sorting algorithms. Eventually, you'll need to do a standard comparison sort. This approach, compared with only using comparison sort, will reduce the number of comparisons by a factor of log(n)/log(n/B), where B is the number of buckets. For 100 buckets and 10000 songs, this is a factor of 2 reduction.

另一种比较节省的方法是使用修改过的二进制搜索进行插入排序(用于初始排序和以后的插入):而不是将二进制搜索的初始边界设置为 0 和 n ，根据您自己可以确定最终位置的直觉将它们设置为值，例如 0 和 n/10 (如果它肯定在您的前10％中).您越能做到这一点，所需的比较就越少.

An alternative, comparison-saving approach is to do insertion sort (for both initial sorting and later insertions) with a modified binary search: instead of setting the initial bounds of the binary serach at 0 and n, set them to values based on your own intuition of where you are certain it will end up, like 0 and n/10, if it's definitely in your top 10%. The more granularly you can do this, the fewer comparisons you will need.

注意事项::同时进行存储桶排序和修改后的二进制搜索，如果您错了，则需要进行其他比较以解决错误.

Caveat: with both bucket sort and the modified binary search, if you are wrong, you will need to do additional comparisons to fix your mistake.

最后一个词:这个问题假设 exists 存在正确的排名 ，并且可以通过比较来实现.如果您有圆形偏好设置，例如 a> b，b> c和c> a (la剪刀石头布剪刀)，则无法构建排名.算法仍将完成，但结果列表将不一致.

And one final word: this question assumes that there exists is a correct ranking and that it can be achieved via comparisons. If you have circular preferences, such as a > b, b > c, and c > a, a la rock-paper-scissors, then a ranking cannot be constructed. The algorithms will still complete, but the resulting list will be inconsistent.

这篇关于添加元素时，哪种排序算法使用的比较次数最少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！