在了解快速排序法的概念之前要先理解partition演算法,不過單用文字敘述還是蠻抽象的,所以搭配示意圖來做說明,假如現在有個陣列[2, 6, 3, 9, 1, 5]
取陣列的最後一個值5作為pivot基準值
接下來從index 0開始, 2小於5所以標記為綠色
再來是6,6大於5所以標記為橘色
輪到3,發現比5小所以把3標記為綠色,因為要把比5小的值都集中到左邊,所以跟6交換位置
接下來是9, 比5大標記成橘色
輪到1,比5小所以把1標記為綠色,因為比5小的值都要集中到左邊,所以要跟6交換位置
最後再讓支點5與最大值群組(橘色的便條紙)中的第一個值做交換,5這個數字就完成了排序
不過這時你會發現綠色的陣列並沒有由小到大排序好,這邊假設我們也不知道橘色陣列是否有排序好, 所以接下來也對左右兩個陣列,利用遞迴的方式持續做一樣的動作。
函式內部實作為:
進行完一輪之後,若左群體[比基準值小的陣列]或右群體[比基準值大的陣列]的長度大於1的話,則再次呼叫quickSort函式(遞迴),最後將[比基準小的陣列] 、基準值、[比基準大的陣列]依序組合起來就是排序好的陣列。
const partition = (arr, left, right) => {
let pivot = arr[right];
//用來計算有幾個數字小於pivot
let i = left - 1;
//從最左邊找到pivot的前一個停止
for (let j = left; j <= right - 1; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
return i + 1;
};
const quickSort = (arr, left, right) => {
if (left < right) {
let sortedIndex = partition(arr, left, right);
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
return arr;
};
const arr = [2, 6, 3, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
//輸出 [1, 2, 3, 5, 6, 9]
第二種解法比較容易理解
函式內部實作為:
若A or B陣列長度大於1,則再次呼叫quickSort函式(遞迴),最後將[比基準小的陣列] 、基準值、[比基準大的陣列]依序組合起來就是排序過後的陣列。
用js實作第二種快速排序法
const quickSort2 = (arr) => {
if (arr.length <= 1) return arr;
const small = [];
const big = [];
const pivot = arr[arr.length - 1];
for (let i = 0; i < arr.length - 1; i++) {
if (pivot > arr[i]) {
small.push(arr[i]);
} else {
big.push(arr[i]);
}
}
return [...quickSort2(small), pivot, ...quickSort2(big)];
};
const arr1 = [2, 6, 3, 9, 1, 5];
quickSort2(arr1);
//輸出 [1, 2, 3, 5, 6, 9]