用JS实现快速排序算法
实现快速排序的基本思路
快速排序是一种分治算法，通过选择一个基准元素将数组分为两部分，一部分小于基准，另一部分大于基准，递归地对两部分进行排序。
基础实现代码
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) left.push(arr[i]);
else right.push(arr[i]);
}
return [...quickSort(left), pivot, ...quickSort(right)];
}原地分区优化版本
减少空间复杂度，直接在原数组上进行分区操作：
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const pivotIndex = partition(arr, left, right);
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
return arr;
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}时间复杂度分析
- 最佳情况：$O(n \log n)$（每次分区都能均匀划分）
- 最差情况：$O(n^2)$（每次分区都极端不平衡）
- 平均情况：$O(n \log n)$
使用示例
const unsorted = [5, 3, 8, 4, 2];
console.log(quickSort(unsorted)); // 输出 [2, 3, 4, 5, 8]
console.log(quickSortInPlace([...unsorted])); // 输出 [2, 3, 4, 5, 8]
