排序算法
一句话解释
排序算法将集合中的元素按某种定义的顺序(升序、降序或自定义)重新排列。
用大白话说
排序算法接收一组元素,将其重排为有序——数值序、字母序或按任意比较函数。排序是计算机科学中研究最充分的问题之一,因为有序数据更易搜索、展示和分析。常见算法包括冒泡排序(简单但 O(n²))、插入排序(适合小规模或近乎有序数据)、归并排序(O(n log n)、稳定、分治)、快速排序(平均 O(n log n)、原地、广泛使用)和堆排序(O(n log n)、原地、不稳定)。它们在速度、内存、稳定性与最坏情况之间各有取舍。多数语言提供内置排序,采用高度调优的混合算法(如 Python 与 V8 的 Timsort,结合归并与插入)。生产中很少自己写排序,但理解其原理对面试以及在内置排序不适用时选对方案至关重要。
示例
javascript
// 快速排序——分治
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const less = arr.slice(1).filter(x => x < pivot);
const more = arr.slice(1).filter(x => x >= pivot);
return [...quickSort(less), pivot, ...quickSort(more)];
}
console.log(quickSort([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 1, 2, 3, 4, 5, 6, 9]快排选取基准,将其余分为更小/更大两组,再递归排序各组。平均 O(n log n)。
相关术语
相关资源
相关课程
- 算法
学习排序与查找算法。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。