快速排序法是一種高效的排序演算法，採用分治策略。它選擇一個樞紐元素，將陣列分為兩部分：小於樞紐的元素和大於樞紐的元素，然後遞歸地對兩部分排序。
| 項目 | 複雜度 | 說明 |
|---|---|---|
| 最壞時間複雜度 | O(n²) | 樞紐選擇不當時（如總選最大/最小值） |
| 平均時間複雜度 | O(n log n) | 樞紐選擇較好的一般情況 |
| 最佳時間複雜度 | O(n log n) | 樞紐總是分割點的中位數時 |
| 空間複雜度 | O(log n) | 遞歸呼叫棧的深度 |
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}