排序算法
排序是把一组数据按照某个比较规则排列。下面的实现默认按升序排序，并且都不修改输入数组。如果只要求原地排序，可以直接在输入数组上交换元素。
1. 冒泡排序
重复比较相邻元素，把较大的元素逐步交换到数组末尾。某一轮没有发生交换时，说明数组已经有序，可以提前结束。
function bubbleSort(items) {
const result = [...items];
for (let end = result.length - 1; end > 0; end--) {
let swapped = false;
for (let i = 0; i < end; i++) {
if (result[i] > result[i + 1]) {
[result[i], result[i + 1]] = [result[i + 1], result[i]];
swapped = true;
}
}
if (!swapped) break;
}
return result;
}
- 最好时间复杂度：
O(n)（已经有序且使用提前结束）；
- 平均、最坏时间复杂度：
O(n²)；
- 额外空间复杂度：
O(n)（这里的拷贝用于保护输入；原地版本为 O(1)）；
- 稳定排序：相等元素不会交换。
2. 选择排序
每一轮从未排序区间中找到最小值，放到区间起点。它的交换次数较少，但比较次数不会因数组已有序而明显减少。
function selectionSort(items) {
const result = [...items];
for (let i = 0; i < result.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < result.length; j++) {
if (result[j] < result[minIndex]) minIndex = j;
}
if (minIndex !== i) {
[result[i], result[minIndex]] = [result[minIndex], result[i]];
}
}
return result;
}
- 最好、平均、最坏时间复杂度：
O(n²)；
- 额外空间复杂度：
O(n)（原地版本为 O(1)）；
- 通常不稳定：把最小值交换到前面时，可能跨过相等元素。
3. 插入排序
维护一个已经有序的前缀，每次取出下一个元素，从右向左移动较大的元素，再把它插入正确位置。数据量小或接近有序时很实用。
function insertionSort(items) {
const result = [...items];
for (let i = 1; i < result.length; i++) {
const current = result[i];
let j = i - 1;
while (j >= 0 && result[j] > current) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = current;
}
return result;
}
- 最好时间复杂度：
O(n)；
- 平均、最坏时间复杂度：
O(n²)；
- 额外空间复杂度：
O(n)（原地版本为 O(1)）；
- 稳定排序：只移动严格大于当前值的元素。
4. 快速排序
选择一个基准值，将元素划分为“较小”和“较大”两部分，再递归处理子数组。下面使用双指针分区，并用随机基准降低遇到特殊输入的概率。
function quickSort(items) {
const result = [...items];
function partition(left, right) {
const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
const pivot = result[pivotIndex];
[result[pivotIndex], result[right]] = [result[right], result[pivotIndex]];
let storeIndex = left;
for (let i = left; i < right; i++) {
if (result[i] < pivot) {
[result[i], result[storeIndex]] = [result[storeIndex], result[i]];
storeIndex++;
}
}
[result[storeIndex], result[right]] = [result[right], result[storeIndex]];
return storeIndex;
}
function sort(left, right) {
if (left >= right) return;
const pivotIndex = partition(left, right);
sort(left, pivotIndex - 1);
sort(pivotIndex + 1, right);
}
sort(0, result.length - 1);
return result;
}
- 平均时间复杂度：
O(n log n)；
- 最坏时间复杂度：
O(n²)（分区极不均衡）；
- 平均额外空间复杂度：
O(log n)（递归栈），最坏为 O(n)；
- 通常不稳定；
- 实际实现应注意递归深度、重复元素和基准值选择。
5. 归并排序
把数组不断拆成两半，分别排序后合并两个有序数组。它的时间复杂度稳定，但需要线性辅助空间。
function mergeSort(items) {
if (items.length <= 1) return [...items];
const middle = Math.floor(items.length / 2);
const left = mergeSort(items.slice(0, middle));
const right = mergeSort(items.slice(middle));
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
// 相等时优先取左侧元素，从而保持稳定性。
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i), right.slice(j));
}
- 最好、平均、最坏时间复杂度：
O(n log n)；
- 额外空间复杂度：
O(n)；
- 稳定排序；
- 适合链表排序、外部排序，以及需要保证最坏时间复杂度的场景。
6. JavaScript 内置排序
Array.prototype.sort() 会原地修改数组。比较数字时必须传入比较函数，否则元素会按字符串顺序比较：
const numbers = [10, 2, 1];
const ascending = [...numbers].sort((a, b) => a - b);
const descending = [...numbers].sort((a, b) => b - a);
比较函数返回值的含义是：负数表示 a 排在 b 前，正数表示 a 排在 b 后，0 表示两者顺序相同。现代 JavaScript 标准要求 sort 稳定，但面试中仍应先说明运行环境和比较规则。
7. 排序算法对比
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) 原地 | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) 原地 | 不稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) 原地 | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) 平均 | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
这里的空间复杂度按原地版本统计；上面的示例为了不修改输入，都额外复制了数组。
8. 如何选择
- 数据量小、基本有序：插入排序简单且通常很快；
- 需要稳定性：选择归并排序，或使用稳定的内置排序；
- 平均性能优先且能接受最坏情况：快速排序；
- 需要严格的最坏
O(n log n)：归并排序；
- 生产代码：优先使用语言内置排序，并正确传入比较函数。
9. 常见面试题
- 手写快速排序时如何避免最坏情况？ 随机选择基准、三数取中、三路分区，并控制递归深度。
- 快排和归并排序的区别？ 快排通常原地、常数较小，但最坏为
O(n²) 且不稳定；归并排序稳定、最坏为 O(n log n)，但需要 O(n) 辅助空间。
- 什么是稳定排序？ 如果两个元素的排序键相等，排序后仍保持它们在输入中的相对顺序。
- 为什么数字排序要写比较函数？
sort() 默认比较字符串，[10, 2, 1] 可能被排成 [1, 10, 2]。
- 如何验证排序实现？ 至少覆盖空数组、单元素、重复元素、已经有序、逆序和负数，并检查结果是否修改了输入。
