今天要來實作的快速排序法Quick Sort，雖然不是最佳的(以前學習的時候看到他的名字以為它會是最快的)，不過它仍是必須學習的經典。

我們就直接開始吧！

Input: nums = [5,1,1,2,0,0]

一開始我們要先先挑一個基準數（pivot），這邊我拿每次都固定subArray的第一個元素當作pivot（當然你也可以隨便拿一個數當作pivot，只要我們確定拿的是哪以個方便之後操作），假設為n，而後我們希望把大於Ｐ的數移到它的右邊，小於Ｐ的數移到它的左邊

這裡我們直接挑5為pivot（P），然後我們建立一個left pointer（L）放在pivot的右邊，這裡也就是nums[1] = 1的位置 以及 建立一個 right pointer（R）放在nums的最後一個位置也就是nums[nums.length -1 ] = 0的地方

接下來我們要把
左邊指標（Ｌ）指到的數和Ｐ比較，如果他小於或等於Ｐ我們就把Ｌ往右移動，直到遇到比Ｐ大的數停止
右邊指標（Ｒ），如果他大於Ｐ我們就把Ｒ往左移動，直到遇到比Ｐ小的數停止

然後我們把Ｌ指到的數和Ｒ指到的數交換swap

接下來要做的事情會重複到左指標越過右指標，我們拿右指標和pivot做交換

而pivot換到的位置，會是它最後的位置，也就是說它會是已經被排好不會再改變。而和pivot做完交換後pivot的左右兩邊會產生兩個subArray分別繼續執行quick sort。

nums = [5,1,1,2,0,0]
        ^ ^       ^
        | |       |
        P L       R

--------------------------
R：第一次我們發現 0 < 5 所以符合我們要停留的條件
L：過程中的都符合小於5的條件，直接飛越過了R

nums = [5,1,1,2,0,0]
        ^         ^
        |         |
        P         R
                    ^
                    |
                    L
--------------------------
因為L超越了R，把P和R做swap交換的動作
nums = [0,1,1,2,0,5]
        ^         ^
        |         |
        P         R
                    ^
                    |
                    L
--------------------------
我們現在得到了 [0,1,1,2,0,5]
其中5是已經確定排好的
所以繼續把subArray[0,1,1,2,0]來執行quick sort 
--------------------------
nums = [0,1,1,2,0,5]
        ^ ^     ^
        | |     |
        P L     R

--------------------------
因為 L指的1 > 0，且R指的0沒有大於0，
所以這裡L和R要做swap的動作
nums = [0,0,1,2,1,5]
        ^ ^     ^
        | |     |
        P L     R
--------------------------
然後L和R再繼續下一步
可以發現L走到１就發現1>0
而R要走到0才回停止，這時因為R和L已經交會
就把P和R交換得到
nums = [0,0,1,2,1,5]
--------------------------
現在我們的頭 [.,0,...,5]這兩個數是已經排好的了
我們剩下 [0]和[1,2,1]兩個subArray去呼叫quicksort繼續執行
因為[0]的長度是1已經可以停止
於是我們把P,L,R分別擺在
nums = [0,0,1,2,1,5]
            ^ ^ ^
            | | |
            P L R
--------------------------
按照之前的行為我們可以獲得
nums = [0,0,1,1,2,5]

我們來看平均時間複雜度: O(nlogn)，空間複雜度為: O(logn)

• 在最糟的情況會遇到由大到小排列像是[5,4,3,2,1]，這種會需要O(n^2)
• 而最好的情況會是pivot剛好切在中間的時候，時間為O(nlogn)
• 空間複雜度推薦大家閱讀Tail Call Elimination

function quickSort(array) {
  quicksortHelper(array, 0, array.length - 1);
  return array;
}

function quicksortHelper(array, start, end) {
  // array的長度為０或１
  if (start >= end) return;
  // pivot為subArray的第一個元素
  const pivot = start;
  let left = start + 1;
  let right = end;
  while (right >= left) {
    // 確定是否需要左右交換
    if (array[left] > array[pivot] && array[right] < array[pivot]) {
      swap(left, right, array);
    }
    if (array[left] <= array[pivot]) left++;
    if (array[right] >= array[pivot]) right--;
  }
  swap(pivot, right, array);
  // 確保最多呼叫O(logn)空間複雜度
  // 我們採取每次先呼叫較小的subarray，利用tail recursion的方式
  const leftSubArrIsSmaller = right - start < end - right;
  if (leftSubArrIsSmaller) {
    quicksortHelper(array, start, right - 1);
    quicksortHelper(array, right + 1, end);
  } else {
    quicksortHelper(array, right + 1, end);
    quicksortHelper(array, start, right - 1);
  }
}

function swap(a, b, array) {
  let tmp = array[b];
  array[b] = array[a];
  array[a] = tmp;
}

建議一開始不熟的時候最好拿紙筆出來畫畫看！
畫的時候寫一下pseudo code，對於組成整個答案就會有信心許多！

明日預告：Merge Sort