Day 27 ： 快速排序法 Quick Sort

今天要来实作的快速排序法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