1.基本特点

①原地排序（之U型要很小的辅助栈）
②将长度为N的数组排序所需要的时间和NlgN成正比(平均排序)
快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序，当两个子数组排好序了整个数组也就排好序了。归并：两个子数组已经排好序了，将它们组合起来整个数组就排好序了。

image.png

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]
我们通过递归地调用切分来进行排序，因为切分过程总是能够排定一个元素。

image.png

计算切分：
①取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.
②三向切分
实际应用中经常会出现含有大量重复元素的数组。加入一个数组全是重复的元素，我们就不需要继续进行排序了，但是我们的算法还是会继续切分。

三向切分

• 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

三向切分

如果只有若干个主键地 随机数组，归并排序是线性对数的，三向切分排序则是线性的。