快速排序

• 优点:
  • 原地排序（只需要很小的辅助栈）
  • 时间复杂度:NLgN
• 缺点:
  • 非常脆弱。有无数例子证明许多错误能致使它在实际运用中只有平方级别的性能

QuickSort是一种分治的算法，将一个数组分为两个小数组，将两部分独立排序。

与MergeSort比较

• MergeSort将数组分为两个子数组分别排序，然后将排好序的子数组Merge
  • 递归调用位于处理整个数组之前
  • 将数组分为两半
• QuickSort是当两个子数组都有序的时候，父数组自然有序了
  • 递归调用位于处理整个数组之后(即partition之后)
  • partition位置取决于数组的内容

关键在于partition

使得数组满足3个条件:

• 对于某个j，a[j]已经排定
• a[lo]到a[j-1]中的所有元素都不大于a[j]
• a[j+1]到a[hi]中的所有元素都不小于a[j]

切分的实现

一般选择a[lo]作为切分元素

我们先从数组左端开始扫描，找到第一个比切分元素大的元素，然后从数组右端开始找到第一个比切分元素小的元素。显然这两个元素是没有排定的，因此我们交换它们的位置。如此继续，我们可以保证左指针i左侧的元素都不大于切分元素，右指针j的右侧元素都不小于切分元素。当两个指针相遇的时候，将切分元素与左子数组最右侧的元素交换位置即可。

算法正确性

由于切分过程总是能排定一个元素，由归纳法可知一定能正确递归将整个数组排序

性能特点

QuickSort的内循环会用一个递增的index将数组的元素和一个定值比较(切分元素),shell sort 和 merge sort慢的原因在于它们在内层循环中移动元素

Quick sort另一速度优势在于比较次数少.

但是排序效率还是取决于切分数组的效果，切分实际上有可能发生于一个数组的任何位置。理想情况是将数组对半分。在这种情况下，quick sort所需的比较次数满足Cn = 2Cn/2 + N
.2Cn/2表示两个子数组的比较成本，N表示需要让左右指针于数组中间处相遇的比较次数.

如果第一次从最小的元素开始切分，第二次从第二小的元素切分，那么大数组每次都要被切分，效率极低，因此在排序之前将数组随机排序的主要原因就是要避免这种情况。

相关数学命题

命题K(按照算法书上的顺序)

将长度为N的无重复数组排序，快速排序平均需要~2NLnN次比较以及1/6NLnN的交换.具体证明见书

命题L

快速排序最多需要N^2/2次比较，但随机打乱数组能够预防这种情况。即:

若每次排序后总有其中一个数组是空的，则比较次数是∑n = N(N+1)/2 ~ N^2/2.

提升性能的几个方法

1.切换到插入排序

基于以下两点:

• 对于小数组，快速排序比插入排序要慢
• 因为递归，快速排序的sort()在小数组中也会调用自己
  方法: if (hi <= lo) return; => if (hi <= lo + 5) { Insertion.sort(a, lo, hi); return;}

2.三取样切分

使用子数组的一小部分元素的中位数来切分数组,取样大小为3并用大小剧中的元素切分效果最好.

3.熵最优的排序

简单的想法是将数组切分为三部分，分别对应于小于，等于，大于切分元素的数组元素.

Dijkstra解法:
维护一个lt指针，使得a[lo..lt-1]中的元素都小于v,一个gt指针使得a[gt+1..hi]中的元素都大于v,一个指针i使得a[lt..i-1]中的元素都等于v,a[i..gt]中的元素待定.

• a[i]小于v,交换a[lt]和a[i], lt和i ++
• a[i]大于v,交换a[i]和a[gt], --gt
• a[i]等于v, ++i

对于只有若干不同主键的随机数组，MergeSort的时间复杂度是NLgN，而quick3way则是线性的。3way的最坏情况正是所有主键不同，当存在重复主键时，性能会比merge sort好很多。三向切分是信息量最优的(熵值最低)，对于任意分布的输入，最优的基于比较的算法平均所需的比较次数和3way切分的quicksort平均所需比较次数处于常数因子范围内。

3way运行时间与输入的信息量的N倍成正比。实际运用中这个性质很重要，因为对于包含大量重复元素的数组，它将排序时间从线性对数降到了线性级别。这和元素的顺序没有关系，因为会事先打乱以避免前文所提到的最坏情况。

有人提出了不基于比较的排序算法，但仍然是quicksort的表现最优良见后文