登录js中，什么是快速排序（Quick Sort）
在 JavaScript 中，快速排序（Quick Sort） 是一种高效的、基于分治思想（Divide and Conquer） 的递归排序算法。它通过选择一个“基准值”（pivot），将数组划分为两个子数组：
- 一个包含所有 小于等于 pivot 的元素，
- 另一个包含所有 大于 pivot 的元素，
然后递归地对这两个子数组进行排序，最终合并得到有序数组。
✅ 快速排序的核心步骤（JS 版）
- 选基准（pivot）：通常选中间、首尾或随机元素。
- 分区（partition）：将数组按 pivot 分成左右两部分。
- 递归排序左右子数组。
- 合并结果（在非原地实现中）。
🧩 简洁版（函数式风格，非原地排序）
这是 JavaScript 中最常见、易读的快排写法（不修改原数组）：
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)]; // 选中间元素为 pivot
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 arr = [38, 27, 43, 3, 9, 82, 10];
console.log(quickSort(arr));
// 输出: [3, 9, 10, 27, 38, 43, 82]
✅ 优点：代码简洁、易理解、不会改变原数组。
❌ 缺点：不是原地排序，空间开销较大（每次创建新数组）。
🔧 原地排序版（In-place，更高效）
如果你希望直接修改原数组以节省内存，可以使用索引和分区函数：
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high); // 获取 pivot 正确位置
quickSortInPlace(arr, low, pi - 1); // 排序左半部分
quickSortInPlace(arr, pi + 1, high); // 排序右半部分
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high]; // 选最后一个为 pivot
let i = low - 1; // 小于 pivot 区域的边界
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]]; // pivot 归位
return i + 1;
}
// 示例
const arr = [38, 27, 43, 3, 9, 82, 10];
quickSortInPlace(arr);
console.log(arr);
// 输出: [3, 9, 10, 27, 38, 43, 82]
✅ 优点：原地排序，空间复杂度更低（O(log n) 递归栈）。
⚠️ 注意：会修改原始数组。
⏱️ 时间复杂度（JavaScript 中同样适用）
| 情况 | 时间复杂度 |
|---|---|
| 平均情况 | O(n log n) |
| 最好情况 | O(n log n) |
| 最坏情况 | O(n²)（如已排序 + 固定 pivot） |
💡 实际中可通过随机选 pivot 或 三数取中 来避免最坏情况。
🆚 与 Array.prototype.sort() 对比
- JS 内置的
arr.sort()在现代引擎（V8）中通常使用 Timsort 或 Introsort（快排+堆排+插入排序混合），性能更优且稳定。 - 手写快排主要用于学习算法原理或特定场景（如自定义比较逻辑）。
// 内置排序（推荐日常使用）
arr.sort((a, b) => a - b);
✅ 总结
| 特性 | 快速排序（JS） |
|---|---|
| 是否稳定 | ❌ 不稳定（它在分区（partition）过程中可能会改变相等元素的相对顺序。） |
| 是否原地 | 可实现（看具体写法） |
| 平均时间复杂度 | O(n log n) |
| 适用场景 | 学习分治思想、面试、自定义排序逻辑 |
