快速排序

-描述：
快速排序是一種分治的排序算法，它將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，將兩部分獨(dú)立地排序。
分治法的基本思想是：將原問題分解為若干個(gè)規(guī)模更小但是結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

-步驟：

1. 從數(shù)列中挑出一個(gè)元素，稱為“基準(zhǔn)”。
2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以放到任一邊）。
3. 遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

-Java語言：

public class Quick{
  public static void sort(Comparable[] a){
    StdRandom.shuffle(a);        //消除對輸入的依賴
    sort(a, 0, a.length - 1);
  }
  
  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);                     //將左半部分a[lo...j-1]排序
    sort(a, j+1, hi);                      //將有半部分a[j+1....hi]排序
  }
  // 切分
  private static int partition(Comparable[] a, int lo, int hi){
    int i = lo, j = hi +1;
    Comparable v = a[lo];
     while (true){
        while (less(a[++i], v)) if (i == hi) break;
        while (less(v, a[--j])) if (j == lo) break;
        if (i >=j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);        
    return j;
  } 
}

快速排序軌跡

sort()方法的關(guān)鍵在于切分，這個(gè)過程使數(shù)組滿足下面三個(gè)條件：

• 對于某個(gè)j， a[j]已經(jīng)排定；
• a[lo] 到a[j-1]中所有元素都不大于a[j]；
• a[j+1]到a[hi]中的所有元素都不小于a[j];

切分方法partition(),一般的策略是先隨意的取a[lo]作為切分元素，即那個(gè)將會被排定的袁術(shù)，然后我們從數(shù)組的左端開始想右掃描直到找到一個(gè)大于等于它的元素，再從數(shù)組的右端開始向左掃描直到找到一個(gè)小于等于它的元素。這兩個(gè)元素顯然是沒有排定的，因此我們交換它們的位置。如此繼續(xù)，我們就可以保證左指針i的左側(cè)元素都不大于切分元素，右指針j的右側(cè)元素都是不小于切分元素，當(dāng)兩個(gè)指針相遇時(shí)，我們只需要將切分元素a[lo]和左子數(shù)組最右側(cè)的元素（a[j]）交換然后返回j即可。

切分

切分軌跡

簡而言之：（我的理解）

1. 首先取數(shù)組的第一個(gè)元素作為切分的基準(zhǔn)。
2. 把不大于這個(gè)元素的放到左邊。
3. 把不小于這個(gè)元素的放到右邊。
4. 把左邊，右邊的一段數(shù)據(jù)重復(fù)1,2,3步驟。（因?yàn)榇藭r(shí)，左邊的元素只是保證是小于基準(zhǔn)的，還不是有序的，所以還需要在切分排序。右邊同理。）