快速排序和调整快速排序之间的根本区别是什么？快速排序有何改进？ Java 如何决定使用它而不是合并排序？
正如蜥蜴比尔所说，调整的快速排序仍然具有与基本快速排序相同的复杂性 - O(N log N) 平均复杂度 - 但调整的快速排序使用一些不同的方法来尝试避免 O(N^2) 最坏情况的复杂性以及使用一些优化来减少平均运行时间 N log N 前面的常数。
最坏情况时间复杂度
当每一步的分区一侧始终具有零个元素时，快速排序会出现最坏情况的时间复杂度。当一个分区中的元素与另一分区中的元素的比率远离 1:1（例如 10000:1）时，就会出现接近最坏情况的时间复杂度。这种最坏情况复杂性的常见原因包括但不限于：
一种快速排序算法，始终选择子数组中具有相同相对索引的元素作为主元。例如，对于已经排序的数组，始终选择子数组最左边或最右边元素作为主元的快速排序算法的复杂度为 O(N^2)。始终选择中间元素的快速排序算法为风琴管数组提供 O(N^2)（[1,2,3,4,5,4,3,2,1] 就是一个例子）。
不处理数组中重复/重复元素的快速排序算法可以是 O(N^2)。一个明显的例子是对包含所有相同元素的数组进行排序。明确地说，如果快速排序将数组排序为分区，例如 [ = p ]，那么左侧分区将始终有零个元素。
这些是如何补救的呢？第一个通常可以通过随机选择枢轴来解决。使用几个元素的中位数作为主元也有帮助，但排序的概率为 O(N^2) 高于使用随机主元。当然，随机选择一些元素的中位数也可能是一个明智的选择。这里通常选择三个随机选择的元素的中值作为基准。
第二种情况，重复的元素，通常可以用类似的方法来解决（链接到pdf）或解决方案荷兰国旗问题 http://en.wikipedia.org/wiki/Dutch_national_flag_problem。然而，Bentley-McIlroy 分区更常用，因为它通常更快。我想出了一种比它更快的方法，但这不是本文的重点。
优化
以下是上面列出的方法之外的一些常见优化，可帮助应对最坏的情况：
使用收敛指针快速排序而不是基本快速排序。如果您想对此进行更多详细说明，请告诉我。
当子数组低于特定大小时，对子数组进行插入排序。插入排序的渐进复杂度为 O(N^2)，但对于足够小的 N，它优于快速排序。
使用带有显式堆栈的迭代快速排序，而不是递归快速排序。
展开部分循环以减少比较次数。
将主元复制到寄存器并使用数组中的该空间来减少交换元素的时间成本。
其他注意事项
Java 在对对象进行排序时使用归并排序，因为它是一种稳定排序（保留具有相同键的元素的顺序）。快速排序可以是稳定的，也可以是不稳定的，但稳定版本比不稳定版本慢。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
