---
tags: DSA in JavaScript
---
# Ch.16 Quick Sort

> ~~顧名思義，很快。~~

同樣使用遞迴，但是 quick sort 比起 merge sort 還要更艱深一點，理解上需要一點時間。

- 首先新增基準點，起始點以及終點。
- 利用一個基準點 (假設是第一個元素)，與其他元素去做比對，若比基準點大就維持不變，比基準點小就放基準點之前 (這邊不用排序)，目的是求出基準點元素經過排序後的正確位置
- 以正確位置為基準點分成兩個陣列 (比喻上)，起點到正確位置的陣列，與正確位置到終點的陣列
- 將兩個陣列重複上面動作，分割為四個、八個...，直到起始點超過終點。

一樣先上 helper function

function pivot (arr, start = 0, end = arr.length + 1) {
  // 基準值與正確位置先做出來
  const pivot = arr[start]
  let swapIdx = start
  for (let i = start + 1; i < end; i++) {
  // 若基準點的值比 arr[i] 還大，移動正確位置，然後將 arr[i] 與正確位置的值互換
    if (pivot > arr[i]) {
      swapIdx++
      [arr[swapIdx], arr[i]] = [arr[i], arr[swapIdx]]
    }
  }
  // 最後再將起始點的值與正確位置的值再互換
  [arr[start], arr[swapIdx]] = [arr[swapIdx], arr[start]]
  // 最後回傳正確位置
  return swapIdx
}

重點來了，大概 5 ~ 6 行的解法，乍看之下很簡單，實際上需要一點時間去理解

function quickSort (arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 再求出 pivotIndex (正確位置) 的時候，我的 arr 就已經開始在排序了
    const pivotIndex = pivot(arr, left, right)
    // left
    quickSort(arr, left, pivotIndex - 1)
    // right
    quickSort(arr, pivotIndex + 1, right)
  }
  return arr
}

快速排序法的時間複雜度也是 $O(n log{_2} n)$，但是面對已經排序完畢的陣列，時間複雜度會提升到 $O(n{^2})$，而空間複雜度則是 $O(log{_2}n)$，比起 merge sort，感覺省下來的只有空間而已。