昨天理解 Quick Sort 的運作方式後，今天決定自己試著把流程轉成程式碼。

先簡單回顧 Quick Sort 幾個重要概念：

• Pivot：選擇一個基準值。
• Partition：根據 Pivot 將資料分成較小、相等、較大的部分。
• Recursive：對分割後的資料重複進行相同的事情。

開始寫之前，我先思考幾個問題：

• 如何取得 Pivot？
• 怎麼把比 Pivot 小的數字放左邊，大的放右邊？
• 分割完成後，左右兩邊要怎麼再次進行相同的切割？
• 最後又該怎麼把結果重新組合？

先從 Pivot 和 Partition 開始

我先選擇陣列第一個數字作為 Pivot，並建立 lessArr 和 moreArr。

假設資料是：

[17, 3, 42, 8, 91, 26, 55, 13, 74, 6]

使用 for 迴圈第一輪會得到：

pivot = [17]

lessArr = [3, 8, 13, 6]

moreArr = [42, 91, 26, 55, 74]

到這裡我原本想：

那是不是再寫一個 for，繼續處理 lessArr？

但很快就發現，如果每切一次就再寫一個迴圈，那下一層、下下一層怎麼辦？

這時才發現，前面學的遞迴終於派上用場了。

不需要一直寫 for，而是再次呼叫 quickSort

既然 quickSort() 本身就會做「找 Pivot → Partition」這件事，那分割完成後，其實只要把左右兩邊再次交給它：

quickSort(lessArr)

quickSort(moreArr)

例如第一次的：

lessArr = [3, 8, 13, 6]

再次進入 quickSort() 後，就會變成：

pivot = [3]

lessArr = []

moreArr = [8, 13, 6]

一開始我有個疑問：

這次的 moreArr 不會把上一層的 moreArr 蓋掉嗎？

後來才理解，因為 lessArr、moreArr 都宣告在 quickSort() 裡，所以每呼叫一次函式，都會建立屬於這一次呼叫的新變數。

也就是：

第一層 moreArr = [42, 91, 26, 55, 74]

第二層 moreArr = [8, 13, 6]

名字雖然一樣，但其實是不同層的資料。

遞迴什麼時候才會停止？

如果一直呼叫自己，程式就永遠不會結束，所以還需要 Base Case：

if (arr.length <= 1) {
  return arr
}

當陣列只剩一個數字或沒有數字時，就代表不需要再切割，直接把結果 return 給上一層。

這裡我原本也以為左右兩邊會同時執行，但實際上會先執行 quickSort(lessArr)，一路走到 Base Case 並把結果回傳後，再繼續處理 quickSort(moreArr)。

最後每一層再把結果組合起來：

return [...quickSort(lessArr), ...pivot, ...quickSort(moreArr)]

也就是：

排好的左邊 + Pivot + 排好的右邊

最後完成的 Quick Sort

const quickSort = (arr: number[]) => {
  const pivot = [arr[0]] as number[]
  console.log('一開始的初始值', pivot)

  const lessArr = [] as number[]
  const moreArr = [] as number[]

  if (arr.length <= 1) {
    console.log('已經沒數字了 或 只剩下最後一個數字', arr)
    return arr
  }

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot[0]) {
      lessArr.push(arr[i])
    }

    if (arr[i] > pivot[0]) {
      moreArr.push(arr[i])
    }

    if (arr[i] === pivot[0]) {
      pivot.push(arr[i])
    }
  }

  console.log('lessArr = ', lessArr)
  console.log('moreArr = ', moreArr)

  return [
    ...quickSort(lessArr),
    ...pivot,
    ...quickSort(moreArr)
  ]
}

console.log(
  quickSort([17, 3, 42, 8, 91, 26, 55, 13, 74, 6])
)

把遞迴過程展開

如果把整個遞迴過程展開，可以想成：

quickSort([17,3,42,8,91,26,55,13,74,6])
│
│  pivot = 17
│  less = [3,8,13,6]
│  more = [42,91,26,55,74]
│
├─ quickSort([3,8,13,6])
│  │
│  │  pivot = 3
│  │  less = []
│  │  more = [8,13,6]
│  │
│  ├─ quickSort([])
│  │     └─ return []
│  │
│  └─ quickSort([8,13,6])
│        │
│        │  pivot = 8
│        │  less = [6]
│        │  more = [13]
│        │
│        ├─ quickSort([6])
│        │     └─ return [6]
│        │
│        └─ quickSort([13])
│              └─ return [13]
│
└─ quickSort([42,91,26,55,74])
   │
   │  pivot = 42
   │  less = [26]
   │  more = [91,55,74]
   │
   ├─ quickSort([26])
   │     └─ return [26]
   │
   └─ quickSort([91,55,74])
         │
         │  pivot = 91
         │  less = [55,74]
         │  more = []
         │
         ├─ quickSort([55,74])
         │  │
         │  │  pivot = 55
         │  │  less = []
         │  │  more = [74]
         │  │
         │  ├─ quickSort([])
         │  │     └─ return []
         │  │
         │  └─ quickSort([74])
         │        └─ return [74]
         │
         └─ quickSort([])
               └─ return []

最後再一層一層把結果組合回來：

[3, 6, 8, 13] + [17] + [26, 42, 55, 74, 91]

↓

[3, 6, 8, 13, 17, 26, 42, 55, 74, 91]

最後

今天實際自己寫過一次後，我才真正理解，Quick Sort 的重點不只是「選 Pivot 再分左右」，而是每次分割後，把新的問題再次交給同一個函式處理，直到碰到停止條件，再一層一層把結果組合回來。

前面學遞迴時還覺得有點抽象，這次實際套進 Quick Sort 後，終於比較能理解遞迴到底是在做什麼了。