推荐答案
// www.javascriptcn.com code example
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
// 示例用法
const arr = [3, 6, 8, 10, 1, 2, 1];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出: [1, 1, 2, 3, 6, 8, 10]本题详细解读
快速排序的基本思想
快速排序是一种分治算法，它通过选择一个“基准”（pivot）元素，将数组分为两部分：一部分比基准小，另一部分比基准大。然后递归地对这两部分进行排序，最终将整个数组排序。
代码解析
- 基准条件：如果数组的长度小于等于1，那么它已经是有序的，直接返回。
- 选择基准：我们选择数组中间的元素作为基准（
pivot）。 - 分割数组：
left：包含所有小于基准的元素。middle：包含所有等于基准的元素。right：包含所有大于基准的元素。
- 递归排序：对
left和right部分递归调用quickSort，然后将结果拼接起来。
时间复杂度
- 平均情况：O(n log n)
- 最坏情况：O(n^2)（当每次选择的基准都是最小或最大元素时）
空间复杂度
- O(n)（由于递归调用栈和创建新数组）
适用场景
快速排序在大多数情况下表现良好，尤其适用于大规模数据集的排序。然而，在最坏情况下，它的性能会下降，因此在实际应用中可能需要结合其他优化策略（如随机选择基准）。