Skip to content

排序算法

一句话解释

排序算法将集合中的元素按某种定义的顺序(升序、降序或自定义)重新排列。

用大白话说

排序算法接收一组元素,将其重排为有序——数值序、字母序或按任意比较函数。排序是计算机科学中研究最充分的问题之一,因为有序数据更易搜索、展示和分析。常见算法包括冒泡排序(简单但 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)。

相关术语

相关资源

相关课程

  • 算法

    学习排序与查找算法。

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表