排序算法中不同列表的比较数
我一直在研究排序算法，并对每种排序算法中的比较数提出了一个问题。
假设我们有一个排序算法(插入排序，快速排序，任何东西)。然后，我想使用不同的文件来计算比较的数量。这些文件中的项目是随机的，没有顺序的。例如，文件1有10个项目，包含字母a到j，然后我们有另一个文件(同样，10个项)包含整数1到10，然后我们有另一个文件(10个项)，包含浮点数1.1111111111到10.1111111111。如果我们想使用任何排序算法对这些进行排序(对于第一个排序算法，我们按字母顺序排序，其他排序从最小到最大)。
如果我们计算每个文件中的比较数(例如，在快速排序算法中)，它们是相同的，因为我们比较的是相同的项目数，还是条目的长度改变了比较的数量(a和10.1111111)？如果它们是相同的，是所有排序算法(至少是我提到的那些)的情况，还是只是一些？我不认为这是个难问的问题(对不起)，但我像往常一样想得太多了。我猜他们会是一样的，但我不是真的。有人愿意解释一下吗？
回答 1
Stack Overflow用户
发布于 2016-02-16 07:56:57
比较的数量取决于初始状态。排序算法和的具体实现。
例如：
- 该实现可以进行第一次检查，以检查该集是否已经被排序或下降，以避免不必要的工作，甚至是最坏的情况。这有一个较小的成本，但可以避免病理性病例。对于同一组实现来说，比较的数量将是非常不同的。
- 一些实现选择，例如在
qsort()中选择哪个元素作为支点，将极大地影响相同集合的比较数量。 - 更糟糕的是:为了避免在
qsort()中触发更不容易的二次最坏情况(如Kernighan的论文“反q排序”中所描述的那样)，可以使用一些随机性源实现qsort()来对枢轴值进行不确定的选择。对于这样的实现，比较的数量可能会有所不同，即使对相同的集合进行多次排序也是如此。注意，如果某些元素比较相等，由于qsort()的不稳定性，这会产生不同的顺序。
除非您知道初始状态和排序算法的具体实现，否则您的老师的问题无法得到精确的回答。即使是最好的情况和最坏的情况也取决于实现细节。
https://stackoverflow.com/questions/35425116
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号