用JS实现快速排序算法
快速排序的原理
快速排序是一种分治算法，通过选择一个基准元素（pivot）将数组分为两部分，一部分小于基准，另一部分大于基准，然后递归地对这两部分进行排序。
代码实现
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
const equal = [];
for (let element of arr) {
if (element < pivot) left.push(element);
else if (element > pivot) right.push(element);
else equal.push(element);
}
return [...quickSort(left), ...equal, ...quickSort(right)];
}使用示例
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // 输出: [1, 1, 2, 3, 6, 8, 10]优化版本（原地排序）
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);
}
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 log n)
- 最坏情况：O(n²)（当数组已经排序或逆序时）
注意事项
- 对于小型数组（如长度小于10），插入排序可能比快速排序更高效。
- 基准选择策略会影响性能，常见方法包括选择第一个元素、最后一个元素、中间元素或随机元素。
- 快速排序是不稳定的排序算法，相等元素的相对位置可能会改变。
