Skip to content

排序算法深入

实现冒泡、插入、归并和快速排序;理解其稳定性、复杂度和权衡。

你将学到

  • 基于比较的排序和 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 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

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

查看错误