快速排序採用分治法:
function quickSort(arr) {
if (arr.length <= 1) return arr; // 遞迴終止條件
// 選取中間元素作為基準(避免已排序陣列最壞情況)
var midIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(midIndex, 1)[0]; // 取出基準值,原陣列移除該元素
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 遞迴排序左右子陣列並合併
return quickSort(left).concat([pivot], quickSort(right));
}
// 測試
console.log(quickSort([32, 45, 37, 16, 2, 87])); // [2, 16, 32, 37, 45, 87]
arr.splice(midIndex, 1)[0]:同時獲取基準值並從陣列移除,避免後續比較時重複處理。concat:創建新陣列合併結果,不修改原陣列(函數式風格)。O(n log n),最壞 O(n²)(如陣列已有序且每次選首/尾元素為基準)。O(n log n)(遞迴調用棧 + 新陣列分配)。function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
var pivotIndex = partition(arr, left, right);
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
return arr;
}
function partition(arr, left, right) {
var pivot = arr[right]; // 選最右為基準
var i = left - 1;
for (var j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
荷蘭國旗問題思路,將陣列分為 < pivot、= pivot、> pivot 三區,避免重複元素導致的退化。
隨機選取基準或取「首、中、尾」三者中位數,大幅降低最壞情況概率。
const quickSort = (arr) =>
arr.length <= 1
? arr
: quickSort(arr.filter(x => x < arr[0]))
.concat(arr.filter(x => x === arr[0]))
.concat(quickSort(arr.filter(x => x > arr[0])));
// 注意:此寫法易讀但會多次遍歷陣列,效能不如迴圈版本
Array.sort 內部即採用快排變體)。arr.sort((a,b)=>a-b),僅在教學、面試或特殊定制場景手寫實現。