快速排序為什么這么快？-有解無憂

快速排序

首先選一個基準 pivot，然后過一遍陣列，

把小于 pivot 的都挪到 pivot 的左邊，
把大于 pivot 的都挪到 pivot 的右邊，

這樣一來，這個 pivot 的位置就確定了，也就是排好了 1 個元素，

然后對 pivot 左邊 ?? 的數排序，
對 pivot 右邊 ?? 的數排序，
就完成了，

那怎么排左邊和右邊？

答：同樣的方法，

所以快排也是用的分治法的思想，

「分」

選擇一個 pivot，就把問題分成了

pivot 左邊
pivot 右邊

這兩個問題，

「治」

就是最開始描述的方法，直到每個區間內沒有元素或者只剩一個元素就可以回傳了，

「合」

放在一起自然就是，

但是如何選擇這個 pivot？

取中間的？

取第一個？

取最后一個？

舉個例子：{5, 2, 1, 0, 3}.

比如選最后一個，就是 3.

然后我們就需要把除了 3 之外的數分成「比 3 大」和「比 3 小」的兩部分，這個程序叫做 partition（劃分），

這里我們仍然使用「擋板法」的思想，不用真的弄兩個陣列來存這兩部分，而是用兩個擋板，把區間劃分好了，

我們用「兩個指標」（就是擋板）把陣列分成「三個區間」，那么

左邊的區間用來放小于 pivot 的元素；
右邊的區間用來放大于 pivot 的元素；
中間是未排序區間，

那么初始化時，我們要保證「未排序區間」能夠包含除了 3 之外的所有元素，所以

未排序區間 = [i, j]

這樣左邊和右邊的區間就成了：

[0, i)：放比 3 小的數；
(j, array.length -2]：放比 3 大的數

注意 ?? i, j 是不包含在左右區間里的呢，

那我們的目的是 check 未排序區間里的每一個數，然后把它歸到正確的區間里，以此來縮小未排序區間，直到沒有未排序的元素，

從左到右來 check：

Step1.

5 > 3, 所以 5 要放在右區間里，所以 5 和 j 指向的 0 交換一下：

這樣 5 就排好了，指標 j --，這樣我們的未排序區間就少了一個數；

Step2.

0 < 3，所以就應該在左邊的區間，直接 i++；

Step3.

2 < 3，同理，i++；

Step4.

1 < 3，同理，i++；

所以當兩個指標錯位的時候，我們結束回圈，

但是還差了一步，3 并不在正確的位置上呀，所以還要把它插入到兩個區間中間，也就是和指標 i 交換一下，

齊姐宣告：這里并不鼓勵大家把 pivot 放最左邊，

基本所有的書上都是放右邊，既然放左右都是一樣的，我們就按照大家默認的、達成共識的來，沒必要去“標新立異”，

就比如圍棋的四個星位，但是講究棋道的就是先落自己這邊的星位，而不是伸著胳膊去夠對手那邊的，

那當我們把 pivot 換回到正確的位置上來之后，整個 partition 就結束了，

之后就用遞回的寫法，對左右兩邊排序就好了，

最后還有兩個問題想和大家討論一下：

回到我們最初選擇 pivot的問題，每次都取最后一個，這樣做好不好？

答：并不好，

因為我們是想把陣列分割的更均勻，均勻的時間復雜度更低；但是如果這是一個有序的陣列，那么總是取最后一個是最不均勻的取法，

所以應該隨機取 pivot，這樣就避免了因為陣列本身的特點總是取到最值的情況，

pivot 放在哪

隨機選取之后，我們還是要把這個 pivot 放到整個陣列的最右邊，這樣我們的未排序區間才是連續的，否則每次走到 pivot 這里還要想著跳過它，心好累哦，

class Solution {
  public void quickSort(int[] array) {
    if (array == null || array.length <= 1) {
      return;
    }
    quickSort(array, 0, array.length - 1);
  }
  private void quickSort(int[] array, int left, int right) {
    // base case
    if (left >= right) {
      return;
    }

    // partition
    Random random = new Random(); // java.util 中的亂數生成器
    int pivotIndex = left + random.nextInt(right - left + 1);
    swap(array, pivotIndex, right);

    int i = left;
    int j = right-1;
    while (i <= j) {
      if (array[i] <= array[right]) {
        i++;
      } else {
        swap(array, i, j);
        j--;
      }
    }
    swap(array, i, right);

    //「分」
    quickSort(array, left, i-1);
    quickSort(array, i+1, right);
  }
  private void swap(int[] array, int x, int y) {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
  }
}