一、排序思想

• 將數(shù)組中的一個(gè)數(shù)作為基準(zhǔn)，比該數(shù)小的放到左邊，比該數(shù)大的放到右邊；
• 對(duì)左右兩邊再進(jìn)行上述操作，即把左邊當(dāng)成一個(gè)新數(shù)組，找新的基準(zhǔn)數(shù)，右邊也一樣；
• 直到不能再分割下去為止。

案例：

假如待排序列如下：

• 選定6為基準(zhǔn)數(shù)，然后先從右邊開(kāi)始遍歷，找到一個(gè)比基準(zhǔn)數(shù)小的數(shù)，如下圖：

• 右邊找到比基準(zhǔn)數(shù)小的時(shí)候，右邊先停下，再?gòu)淖筮?/strong>開(kāi)始遍歷，找到比基準(zhǔn)數(shù)大的，如下圖：

• 這個(gè)時(shí)候，左右兩邊都先停下，交換5和7的位置，結(jié)果如下：

• 然后繼續(xù)從右邊開(kāi)始遍歷，即從7的位置開(kāi)始，找到比基準(zhǔn)數(shù)小的數(shù)，如下：

• 找到后停下，再?gòu)淖笸艺冶然鶞?zhǔn)數(shù)大的，即從5開(kāi)始找，結(jié)果如下：

• 這個(gè)時(shí)候，左右兩邊都停下，交換9和4的位置，結(jié)果如下：

• 再?gòu)挠疫呴_(kāi)始找比基準(zhǔn)數(shù)小的，找到了3，然后從左邊找比基準(zhǔn)數(shù)大的，左邊指針移動(dòng)到3的時(shí)候，左右指針重合了，如下：

• 指針重合了，就將基準(zhǔn)數(shù)和指針重合時(shí)所指的數(shù)交換位置，即交換6和3的位置，如圖：

• 此時(shí)6左邊的都是比它小的，右邊的都是比它大的。左邊部分和右邊部分看成是兩個(gè)新的待排序列，兩個(gè)序列都按照上述方式再進(jìn)行排序，先排左邊，再排右邊。

二、代碼實(shí)現(xiàn)

結(jié)合上面的案例，以及代碼中的注釋?zhuān)梢哉f(shuō)是思路十分清晰了，完整代碼如下：

public static void sort(int[] arr, int left, int right) {
  if (arr == null || arr.length == 1) {
   return;
  }
  if (left > right) {
   return;
  }
  int base = arr[left]; // 最左邊的數(shù)當(dāng)作基準(zhǔn)數(shù)
  int i = left; // 從左往右遍歷的指針
  int j = right; // 從右往左遍歷的指針
  int temp = 0; // 用來(lái)保存臨時(shí)變量
  // 當(dāng)左右指針不相遇的時(shí)候，就進(jìn)行檢索
  while(i != j) {
   // 先從右往左檢索，直到檢索到比基準(zhǔn)數(shù)小的
   while (arr[j] >= base && i < j) {
    j--;
   }
   // 再?gòu)淖笸覚z索，直到檢索到比基準(zhǔn)數(shù)大的
   while (arr[i] <= base && i < j) {
    i++;
   }
   // 跳出了上面兩個(gè)while循環(huán)，表示右邊找到了基準(zhǔn)數(shù)小的，左邊找到了比基準(zhǔn)數(shù)大的，交換位置
   temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
  // 跳出了最外層while循環(huán)，表示i和j相等，左右指針相遇了，交換基準(zhǔn)數(shù)和此時(shí)指針指的元素
  arr[left] = arr[i];
  arr[i] = base;
  // 此時(shí)，第一趟排序完成，左邊和右邊看成新數(shù)組，重復(fù)上述步驟
  sort(arr, j+1, right); // 排右邊
  sort(arr, left, i-1); // 排左邊
}

快速排序之所以成為快速排序，那就是因?yàn)樗欤?jīng)測(cè)試，排1千萬(wàn)數(shù)據(jù)大概是1秒的樣子，還真是有兩把刷子。