快速排序的复杂度是O(nlogn),一般来说比归并、堆排序要快。然而快排本身最坏情况下退化为冒泡排序,不够稳定。

这种“最坏情况”源于轴点(pivot)的选取:考虑完全有序的序列{0, 1, 2, ..... n}, 如果选择最左侧的元素为轴点,每一次算法过程都会将区间分为长度为1和长度为n-1的子序列,因而复杂度是O(n^2);而对于完全反序的序列{n, n-1, n-2, ..... 1, 0},如果选择最右侧的元素为轴点,区间的划分情况同样最坏。

一般情况下,对应于一组可能的输入,如果轴点选取为每一次都划分出长度为1的子序列的元素,将达到最坏情况。

一种常见的策略是随机选取轴点。鉴于大部分快排选择最左侧元素为轴点,在不破坏现有实现的基础上,在递归开始后首先随机选择一个元素和最左侧元素交换,其余过程不变,这样就等效为随机选了一个元素作为轴点。这种方法的期望比较次数是1.386nlogn。

第二种方法是选择待排序序列的最左、最右和中间三个元素中的中位数作为轴点。期望比较次数降为1.188nlogn,代价是3%左右的交换次数。这一步骤可以反复进行,比如,可以先将区间分为三段,每一段使用上述方法选取一个轴点,然后再比较这三个点,取其中位数,称之为ninther。

第二种方法的原理可以大致理解为,从首尾和中部选择三个元素的中位数,可以充分接近于原序列的中位数。我们知道,如果每一次轴点都在线性时间选择为中位数,那么快排是稳定的O(nlogn)算法。因此这种方法可以降低最坏情况发生的概率(输入序列随机的情况),且多次重复这个过程,可以进一步优化。

如果我们能在线性时间里找到原序列的中位数就好了!这就是一个n/2-选取问题。现有快排的普遍策略即quickselect,而采用五取样划分,可以在线性时间内找到一个序列第k大的数。

关于五取样划分,也就是linearselect的问题,这里不再赘述。因为这种优化方法在实际中几乎没有应用(常数过大,只有数据集极大时有效,在这种情况下,introsort更好)