JS 學資料結構與演算法 (排序篇)— 快速排序法 Quick Sort
大家好我是老莫，也可以叫我 Kyle
為什麼要寫這個主題？
之前在尋找實習職缺的過程中，遇到幾次當面或者電話面試考資料結構與演算法等技術題，測驗結束才發現自己沒有透徹了解這些概念，有些概念懂了卻不知道怎麼用程式語言實作出來，想當然面試結果並不理想。因此我決定設定這樣的主題，並以自己最擅長的語言 JavaScript 將資料結構或演算法實作出來，除了能夠了解背後的概念外，也有能力可以透過程式語言實作出來，並利用這些概念去解決真實狀況遇到的技術問題。
主題涵蓋的範圍？
這次 “JS 學資料結構與演算法” 系列預計會包含以下範圍：
- 排序 (sort)
- 搜尋 (sesrch)
- 動態程式規劃 (dynamic programming)
- Hash Table 雜湊表
- Linked List 鏈結串列
- Stack 堆疊
- Queue 佇列
- Tree 樹
- Graph 圖形
- Recursion 遞迴
其中各類別可能又會往下細分子類別依次介紹（如排序下細分各種排序法），我想這會是一個漫長的主題，但相信踏實地走完這趟旅程一定會讓基礎更加扎實，也能幫助像我一樣對這些觀念一知半解的讀者能有更透徹的理解，如果對這個主題有興趣的朋友們記得追蹤我囉！
*此後內容皆假設讀者了解基本演算法定義與時間複雜度概念
快速排序法
演算法定義：
快速排序法採用 Devide and Conquer 的概念，將一個大問題拆分成數個較小的子問題，再將子問題的結果整合成原問題的答案。
作法：
- 選定一個基準值 (Pivot)
- 將比基準值 (Pivot) 小的數值移到基準值左邊，形成左子串列
- 將比基準值 (Pivot) 大的數值移到基準值右邊，形成右子串列
- 分別對左子串列、右子串列作上述三個步驟
- 直到左子串列或右子串列只剩一個數值或沒有數值
快速排序法的效率和基準值 (Pivot) 的選擇息息相關，每次選擇的基準值 (Pivot) 愈接近數列的平均值或中位數愈好。
時間複雜度
最佳 :
O(n log n)，第一個基準值的位置剛好是中位數，將資料均分成二等份。
最差：
Ο(n^2)，當資料的順序恰好為由大到小或由小到大時，此時有分割跟沒有分割並沒有區別，反而做了多餘的操作。
平均：
O(n log n)
程式範例
let testArray = [34,25,78,67,109,1,18,76,200];
function quickSort(arr) { // 如果 array 為空陣列或只有一個元素，直接返回，不需排序。 if (arr.length <=1 ) { return arr; } let pivot = arr[arr.length -1]; // 將陣列元素最後一項設為基準值 let left = []; // 用來儲存比基準值小的元素 let right = []; // 用來儲存比基準值大的元素 for(let i = 0; i < arr.length - 1; i++) {
// 設定 i < arr.length - 1 是因為陣列最後一項被我們設為 pivot 因此不需考慮 if (arr[i] < pivot) { left.push(arr[i]) } else { right.push(arr[i]) } }return [...quickSort(left), pivot, ...quickSort(right)]// 也可以寫成： return quickSort(left).concat(pivot, quickSort(right))}const sortedArray = quickSort(testArray);console.log(sortedArray); // [ 1, 18, 25, 34, 67, 76, 78, 109, 200 ]
以上解法比較可能會讓讀者產生疑惑的是
return [...quickSort(left), pivot, ...quickSort(right)]這邊使用了遞迴方法與 ES6 Spread Operator 的語法，遞迴在後面的章節會 cover 到，對 ES6 語法不熟的讀者可以參考 這篇文章。
最後必須要強調的是，同一種演算法其實有無數種解題方式，上面的解法不過是其中一種，並且未必是最好的解法，雖然確實可以達到排序的目的，但是也許在效能或記憶體運用卻仍有可以改善的空間。因此如果你們發現上面解法可以改進的地方，歡迎討論，如果你對這個系列有興趣，也想跟我一起透過 JavaScript 強化自己對於資料結構與演算法的基礎，歡迎訂閱我，如果覺得這篇文章對你有幫助，也不要吝嗇幫我拍拍手吧！
下回預告 : 合併排序法
