排序算法深入
实现冒泡、插入、归并和快速排序;理解其稳定性、复杂度和权衡。
你将学到
- 基于比较的排序和 O(n log n) 下界
- 稳定排序与不稳定排序
- 原地排序与非原地排序
- 何时使用每种排序算法
概念讲解
排序算法深入
排序将元素按顺序排列。这是计算机科学中研究最多的问题之一,因为许多其他算法依赖有序数据。
O(n log n) 屏障
任何基于比较的排序在最坏情况下至少需要 Omega(n log n) 次比较。这是因为有 n! 种可能的排列,每次比较区分 2 种情况,所以至少需要 log2(n!) 约等于 n log n 次比较。要突破此屏障,必须使用非比较排序(计数排序、基数排序),它们利用数据结构。
稳定性
如果相等元素保持原始相对顺序,则排序是稳定的。归并排序和插入排序是稳定的;快速排序和堆排序不是。当按次要键排序时稳定性很重要。
主要算法
冒泡排序 O(n^2),简单但慢。插入排序最坏 O(n^2),最佳 O(n) 适合近乎有序数据。归并排序保证 O(n log n),稳定,但需 O(n) 额外空间。快速排序平均 O(n log n),最坏 O(n^2),原地,因缓存效率实际最快。
实际选择
大多数语言标准库使用混合排序:Python/Java 的 Timsort(归并+插入),C++ 的 introsort(快排+堆排+插入)。
示例代码
// Insertion sort - O(n^2) worst, O(n) best, stable, in-place
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
return arr;
}
// Merge sort - O(n log n) guaranteed, stable
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = arr.length >> 1;
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
const merged = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) merged.push(left[i++]);
else merged.push(right[j++]);
}
return merged.concat(left.slice(i), right.slice(j));
}
console.log(insertionSort([5, 2, 8, 1, 9, 3]));
console.log(mergeSort([5, 2, 8, 1, 9, 3]));
插入排序通过将每个元素插入正确位置,逐个构建有序数组。归并排序分割数组,递归排序两半,然后按序合并。
动手试一试
- Case Converter
排序和大小写转换都变换有序数据——观察稳定变换如何保持结构。
常见错误
错误写法
期望快速排序总是 O(n log n)。
正确做法
快速排序在最坏情况下为 O(n^2)(如已排序数据加朴素枢轴)。使用随机枢轴或三数取中可避免。
错误写法
按多键排序时忽略稳定性。
正确做法
如果在主键排序后按次键排序,第二次排序必须稳定,以在次键相等时保留主键顺序。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。