正如比尔蜥蜴说的那样,调整后的快速排序仍然具有与基本快速排序相同的复杂性 - 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 |]这样的分区中 > = p],那么左分区将始终具有零元素.
这些如何补救？第一种通常是通过随机选择枢轴来解决的.使用几个元素的中值作为枢轴也可以帮助,但排序的概率为O(N ^ 2)高于使用随机枢轴.当然,一些随机选择的元素的中位数也可能是明智的选择.三个随机选择的元素作为枢轴的中位数是这里的常见选择.
第二种情况,即重复元素,通常用Bentley-McIlroy分区(链接到pdf)或荷兰国旗问题的解决方案来解决.然而,Bentley-McIlroy分区更常用,因为它通常更快.我想出了一种比它更快的方法,但这不是这篇文章的重点.
优化
以下是上面列出的方法之外的一些常见优化,以帮助解决最坏的情况:
使用汇聚指针快速排序而不是基本的快速排序.如果您想对此进行更详细的说明,请与我们联系.
插入排序子阵列低于一定大小时.插入排序渐近为O(N ^ 2),但是对于足够小的N,它会快速排序.
使用具有显式堆栈的迭代快速排序而不是递归快速排序.
展开部分循环以减少比较次数.
将数据透镜复制到寄存器并使用数组中的该空间来减少交换元素的时间成本.
其他说明
Java在排序对象时使用mergesort,因为它是一个稳定的排序(保留具有相同键的元素的顺序).Quicksort可以稳定或不稳定,但稳定版本比不稳定版本慢.