1.基本特点
①原地排序（之U型要很小的辅助栈）
②将长度为N的数组排序所需要的时间和NlgN成正比(平均排序)
快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序，当两个子数组排好序了整个数组也就排好序了。归并：两个子数组已经排好序了，将它们组合起来整个数组就排好序了。
关键：将一个数组按某个元素进行切分，切分元素左边的全部小于等于切分元素，切分元素的右边全部大于等于切分元素。实际上在最终的排序结果中切分元素的位置就确定不变了。
2. 快速排序过程
public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
assert isSorted(a);
}
// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
assert isSorted(a, lo, hi);
}
快速排序的关键在于切分，这个过程使得数组满足三个条件：
①对于某个j，a[j]已经排定
②a[lo]到a[j-1]中的额所有元素都不大于a[j]
③a[j+1]到a[hi]中的所有元素都不小于a[j]
我们通过递归地调用切分来进行排序，因为切分过程总是能够排定一个元素。
计算切分：
①取a[lo]作为切分元素。
②i=lo，不断增大i直到遇到元素大于切分元素
③j=hi，不断减小j直到遇到元素小于切分元素
④交换exch（a，i，j）
上述②③步骤不断重复，直到i>=j
⑤最后将切分元素放入到正确的位置：exch（a，lo，j）
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
// find item on lo to swap
while (less(a[++i], v))
if (i == hi) break;
// find item on hi to swap
while (less(v, a[--j]))
if (j == lo) break; // redundant since a[lo] acts as sentinel
// check if pointers cross
if (i >= j) break;
exch(a, i, j);
}
// put partitioning item v at a[j]
exch(a, lo, j);
// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
整个快速排序的全过程：
3. 性能分析
①快速排序算法的效率依赖于切分元素的值
②快速排序的最好情况是每次都能正好将数组对半分。C（N） = 2C（N/2） + N.2C（N/2）表示将两个子数组进行排序的成本，N表示用切分元素和所有元素进行比较的成本。快速排序的平均性能为NlgN。
③快速排序最多需要N^2/2次比较。切分元素所在的一端总是为空。
4. 快速排序算法的改进
①对于小数组插入排序比快速排序更快
将sort中if(hi<=lo) return替换成if(hi<=lo+M) {Intersection.sort(a,lo,hi);return;}参数M的最佳值和系统相关，一般取5~15.
②三向切分
实际应用中经常会出现含有大量重复元素的数组。加入一个数组全是重复的元素，我们就不需要继续进行排序了，但是我们的算法还是会继续切分。
从左到右遍历数组：i=lo
- a[i]<v时，将 a[i]和 a[lt]交换，lt和i加一
- a[i]>v时，将 a[i]和 a[gt]交换，gt减一
- a[i]==v时，将i加1
// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1);
sort(a, gt+1, hi);
assert isSorted(a, lo, hi);
}
Example
如果只有若干个主键地 随机数组，归并排序是线性对数的，三向切分排序则是线性的。
