1.基本特點

①原地排序（之U型要很小的輔助棧）
②將長度為N的數(shù)組排序所需要的時間和NlgN成正比(平均排序)
快速排序是一種分治的排序算法，它將一個數(shù)組分成兩個子數(shù)組，將兩部分獨立地排序，當(dāng)兩個子數(shù)組排好序了整個數(shù)組也就排好序了。歸并：兩個子數(shù)組已經(jīng)排好序了，將它們組合起來整個數(shù)組就排好序了。

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);
    }

快速排序的關(guān)鍵在于切分，這個過程使得數(shù)組滿足三個條件：
①對于某個j，a[j]已經(jīng)排定
②a[lo]到a[j-1]中的額所有元素都不大于a[j]
③a[j+1]到a[hi]中的所有元素都不小于a[j]
我們通過遞歸地調(diào)用切分來進行排序，因為切分過程總是能夠排定一個元素。

image.png

計算切分：
①取a[lo]作為切分元素。
②i=lo，不斷增大i直到遇到元素大于切分元素
③j=hi，不斷減小j直到遇到元素小于切分元素
④交換exch（a，i，j）
上述②③步驟不斷重復(fù)，直到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. 性能分析

①快速排序算法的效率依賴于切分元素的值
②快速排序的最好情況是每次都能正好將數(shù)組對半分。C（N） = 2C（N/2） + N.2C（N/2）表示將兩個子數(shù)組進行排序的成本，N表示用切分元素和所有元素進行比較的成本?？焖倥判虻钠骄阅転镹lgN。
③快速排序最多需要N^2/2次比較。切分元素所在的一端總是為空。

4. 快速排序算法的改進

①對于小數(shù)組插入排序比快速排序更快
將sort中if(hi<=lo) return替換成if(hi<=lo+M) {Intersection.sort(a,lo,hi);return;}參數(shù)M的最佳值和系統(tǒng)相關(guān)，一般取5~15.
②三向切分
實際應(yīng)用中經(jīng)常會出現(xiàn)含有大量重復(fù)元素的數(shù)組。加入一個數(shù)組全是重復(fù)的元素，我們就不需要繼續(xù)進行排序了，但是我們的算法還是會繼續(xù)切分。

三向切分

• 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

三向切分

如果只有若干個主鍵地 隨機數(shù)組，歸并排序是線性對數(shù)的，三向切分排序則是線性的。