跳到主要内容

排序算法

概览​

排序算法是面试高频考点，需要掌握各种排序的原理、实现、复杂度。

算法时间复杂度(平均)时间复杂度(最坏)空间复杂度稳定性
冒泡排序O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)✅ 稳定
选择排序O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)❌ 不稳定
插入排序O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)✅ 稳定
希尔排序O(n1.3)O(n^{1.3})O(n2)O(n^2)O(1)O(1)❌ 不稳定
归并排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(n)O(n)✅ 稳定
快速排序O(nlog⁡n)O(n \log n)O(n2)O(n^2)O(log⁡n)O(\log n)❌ 不稳定
堆排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(1)O(1)❌ 不稳定
稳定性是什么？

如果两个相等的元素，排序后相对位置不变，则称该排序算法是稳定的。 例如：[3a, 1, 3b] 排序后 [1, 3a, 3b]（3a 仍在 3b 前面）就是稳定的。

冒泡排序 Bubble Sort​

原理​

相邻元素两两比较，将较大的元素"冒泡"到末尾。

实现​

bubbleSort.ts
function bubbleSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // 每轮将最大的数冒泡到末尾
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

优化：提前退出​

bubbleSortOptimized.ts
function bubbleSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // 标记本轮是否发生交换
    let swapped = false;

    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // 如果没有交换，说明已经有序
    if (!swapped) break;
  }

  return arr;
}
复杂度
  • 时间：O(n2)O(n^2)，优化后最好情况 O(n)O(n)
  • 空间：O(1)O(1)
  • 稳定：✅

变体：鸡尾酒排序 Cocktail Sort​

也叫双向冒泡排序，先从左到右把最大的冒到右边，再从右到左把最小的冒到左边，交替进行。

cocktailSort.ts
function cocktailSort(arr: number[]): number[] {
  let left = 0;
  let right = arr.length - 1;
  let swapped = true;

  while (swapped) {
    swapped = false;

    // 从左到右，把最大的冒到右边
    for (let i = left; i < right; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    right--;

    if (!swapped) break;

    swapped = false;

    // 从右到左，把最小的冒到左边
    for (let i = right; i > left; i--) {
      if (arr[i] < arr[i - 1]) {
        [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
        swapped = true;
      }
    }
    left++;
  }

  return arr;
}
鸡尾酒排序的优势

当数据两端有序、中间无序时（如 [2, 3, 4, 5, 1]），鸡尾酒排序比普通冒泡排序更快，因为它能同时从两端向中间收缩。

希尔排序 Shell Sort​

原理​

希尔排序是插入排序的改进版。核心思想是将数组按一定**间隔（gap）**分组，对每组进行插入排序，然后逐渐缩小间隔，直到间隔为 1（即标准插入排序）。

原始数组: [8, 3, 6, 2, 5, 1, 7, 4]

gap=4: 分成 4 组，分别插入排序
  组1: [8, 5] → [5, 8]
  组2: [3, 1] → [1, 3]
  组3: [6, 7] → [6, 7]
  组4: [2, 4] → [2, 4]
  结果: [5, 1, 6, 2, 8, 3, 7, 4]

gap=2: 分成 2 组，分别插入排序
  组1: [5, 6, 8, 7] → [5, 6, 7, 8]
  组2: [1, 2, 3, 4] → [1, 2, 3, 4]
  结果: [5, 1, 6, 2, 7, 3, 8, 4]

gap=1: 标准插入排序
  结果: [1, 2, 3, 4, 5, 6, 7, 8]

实现​

shellSort.ts
function shellSort(arr: number[]): number[] {
  const n = arr.length;

  // 初始间隔为数组长度的一半，逐步缩小
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 对每个间隔进行插入排序
    for (let i = gap; i < n; i++) {
      const current = arr[i];
      let j = i;

      // 在同组中，将比 current 大的元素向后移动
      while (j >= gap && arr[j - gap] > current) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = current;
    }
  }

  return arr;
}

优化：Knuth 间隔序列​

不同的间隔序列会影响希尔排序的性能。Knuth 提出的序列 1, 4, 13, 40, 121...（h = 3h + 1）在实践中表现更好。

shellSortKnuth.ts
function shellSort(arr: number[]): number[] {
  const n = arr.length;

  // 使用 Knuth 间隔序列: 1, 4, 13, 40, 121, ...
  let gap = 1;
  while (gap < Math.floor(n / 3)) {
    gap = gap * 3 + 1;
  }

  while (gap >= 1) {
    for (let i = gap; i < n; i++) {
      const current = arr[i];
      let j = i;

      while (j >= gap && arr[j - gap] > current) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = current;
    }

    gap = Math.floor(gap / 3);
  }

  return arr;
}
复杂度
  • 时间：平均约 O(n1.3)O(n^{1.3})，最坏 O(n2)O(n^2)（取决于间隔序列）
  • 空间：O(1)O(1)
  • 稳定：❌（相同元素可能被分到不同组，交换后相对位置改变）
为什么希尔排序比插入排序快？

插入排序每次只能将元素移动一位，而希尔排序通过大间隔可以让元素跨越式移动，更快地接近最终位置。当间隔缩小到 1 时，数组已经基本有序，此时插入排序的效率接近 O(n)O(n)。

选择排序 Selection Sort​

原理​

每轮从未排序部分选择最小的元素，放到已排序部分的末尾。

实现​

selectionSort.ts
function selectionSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // 找到未排序部分的最小值索引
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // 将最小值交换到已排序部分的末尾
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}
复杂度
  • 时间：O(n2)O(n^2)，无论什么情况都是 O(n2)O(n^2)
  • 空间：O(1)O(1)
  • 稳定：❌（交换可能改变相等元素的相对位置）

插入排序 Insertion Sort​

原理​

将未排序的元素插入到已排序部分的正确位置，类似打扑克牌时整理手牌。

实现​

insertionSort.ts
function insertionSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    const current = arr[i];  // 待插入的元素
    let j = i - 1;

    // 将比 current 大的元素向后移动
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }

    // 插入到正确位置
    arr[j + 1] = current;
  }

  return arr;
}
复杂度
  • 时间：O(n2)O(n^2)，最好情况（已排序）O(n)O(n)
  • 空间：O(1)O(1)
  • 稳定：✅
使用场景

插入排序在数据量小或基本有序时效率很高，常用于其他排序算法的优化（如快排在小规模数据时切换到插入排序）。

归并排序 Merge Sort​

原理​

分治思想：将数组分成两半，分别排序，然后合并。

实现​

mergeSort.ts
function mergeSort(arr: number[]): number[] {
  // 基准情况：数组长度 <= 1 直接返回
  if (arr.length <= 1) return arr;

  // 分割
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // 合并
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0;
  let j = 0;

  // 比较两个数组的元素，按顺序放入结果
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // 将剩余元素放入结果
  return result.concat(left.slice(i)).concat(right.slice(j));
}

原地归并（优化空间）​

mergeSortInPlace.ts
function mergeSort(arr: number[], left = 0, right = arr.length - 1): number[] {
  if (left >= right) return arr;

  const mid = Math.floor((left + right) / 2);
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  mergeInPlace(arr, left, mid, right);

  return arr;
}

function mergeInPlace(
  arr: number[],
  left: number,
  mid: number,
  right: number
): void {
  const temp: number[] = [];
  let i = left;
  let j = mid + 1;

  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp.push(arr[i++]);
    } else {
      temp.push(arr[j++]);
    }
  }

  while (i <= mid) temp.push(arr[i++]);
  while (j <= right) temp.push(arr[j++]);

  // 将排序结果复制回原数组
  for (let k = 0; k < temp.length; k++) {
    arr[left + k] = temp[k];
  }
}
复杂度
  • 时间：O(nlog⁡n)O(n \log n)，任何情况都是
  • 空间：O(n)O(n)
  • 稳定：✅

快速排序 Quick Sort​

原理​

分治思想：选择一个基准元素（pivot），将数组分成两部分：小于 pivot 的在左边，大于 pivot 的在右边，然后递归排序。

实现（简洁版）​

quickSortSimple.ts
function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x < pivot);
  const right = arr.slice(1).filter(x => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

实现（原地排序版）​

quickSortInPlace.ts
function quickSort(
  arr: number[],
  left = 0,
  right = arr.length - 1
): number[] {
  if (left >= right) return arr;

  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);

  return arr;
}

function partition(arr: number[], left: number, right: number): number {
  // 选择最右边的元素作为 pivot
  const pivot = arr[right];
  let i = left;

  // 将小于 pivot 的元素移到左边
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  // 将 pivot 放到正确位置
  [arr[i], arr[right]] = [arr[right], arr[i]];

  return i;
}

优化：随机选择 pivot​

quickSortRandom.ts
function partition(arr: number[], left: number, right: number): number {
  // 随机选择 pivot，避免最坏情况
  const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  [arr[randomIndex], arr[right]] = [arr[right], arr[randomIndex]];

  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}
复杂度
  • 时间：平均 O(nlog⁡n)O(n \log n)，最坏 O(n2)O(n^2)（已排序数组选第一个作为 pivot）
  • 空间：O(log⁡n)O(\log n)（递归栈）
  • 稳定：❌
最坏情况 O(n2)O(n^2)

最坏时间复杂度出现在每次 partition 都极度不均匀的情况——pivot 总是选到最大或最小元素，导致一侧为空、另一侧有 n-1 个元素，递归退化为线性。

典型触发场景：

  1. 数组已经有序（升序或降序），且 pivot 选第一个或最后一个元素——如 [1, 2, 3, 4, 5]，pivot=1，左侧空，右侧 4 个元素，每层只减少 1 个
  2. 数组所有元素相同，如 [5, 5, 5, 5, 5]——每次划分也是极度不均匀（三路快排可解决）
  3. 数组近乎有序——基本排好序只有个别元素乱序

本质原因：递归树从 O(log⁡n)O(\log n) 层退化为 O(n)O(n) 层，每层还要遍历剩余元素，总计 n+(n−1)+(n−2)+⋯=O(n2)n + (n-1) + (n-2) + \cdots = O(n^2)。

解决方案：

  • 随机选 pivot：最简单有效，期望复杂度 O(nlog⁡n)O(n \log n)
  • 三数取中：取 left、mid、right 的中位数作为 pivot
  • 三路快排：等于 pivot 的元素单独分一组，解决大量重复元素的问题

变体：三路快排 Three-Way QuickSort​

当数组中有大量重复元素时，普通快排效率会下降。三路快排将数组分成三部分：小于 pivot、等于 pivot、大于 pivot。

threeWayQuickSort.ts
function threeWayQuickSort(
  arr: number[],
  left = 0,
  right = arr.length - 1
): number[] {
  if (left >= right) return arr;

  // 三路划分
  const [lt, gt] = threeWayPartition(arr, left, right);

  // 只需递归小于和大于的部分，等于的部分已经就位
  threeWayQuickSort(arr, left, lt - 1);
  threeWayQuickSort(arr, gt + 1, right);

  return arr;
}

function threeWayPartition(
  arr: number[],
  left: number,
  right: number
): [number, number] {
  const pivot = arr[left];
  let lt = left;      // arr[left..lt-1] < pivot
  let gt = right;     // arr[gt+1..right] > pivot
  let i = left + 1;   // arr[lt..i-1] === pivot

  while (i <= gt) {
    if (arr[i] < pivot) {
      // 小于 pivot，交换到左边
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      // 大于 pivot，交换到右边
      [arr[gt], arr[i]] = [arr[i], arr[gt]];
      gt--;
      // 注意：i 不变，因为交换过来的元素还没检查
    } else {
      // 等于 pivot，跳过
      i++;
    }
  }

  // 返回等于 pivot 区间的左右边界
  return [lt, gt];
}

执行过程示例：

arr = [5, 3, 5, 8, 5, 2, 5], pivot = 5

初始: lt=0, gt=6, i=1

i=1: arr[1]=3 < 5, 交换 arr[0] 和 arr[1]
     [3, 5, 5, 8, 5, 2, 5], lt=1, i=2

i=2: arr[2]=5 === 5, 跳过
     lt=1, i=3

i=3: arr[3]=8 > 5, 交换 arr[6] 和 arr[3]
     [3, 5, 5, 5, 5, 2, 8], gt=5, i=3（不变）

i=3: arr[3]=5 === 5, 跳过
     i=4

i=4: arr[4]=5 === 5, 跳过
     i=5

i=5: arr[5]=2 < 5, 交换 arr[1] 和 arr[5]
     [3, 2, 5, 5, 5, 5, 8], lt=2, i=6

i=6 > gt=5, 结束

结果: [3, 2, 5, 5, 5, 5, 8]
      -----  ---------  -
      < 5    === 5      > 5

返回 [lt=2, gt=5]
三路快排的优势
  • 大量重复元素时，等于 pivot 的元素只需一次划分，无需递归
  • 时间复杂度在重复元素多时接近 O(n)O(n)
  • 荷兰国旗问题（Dutch National Flag Problem）就是三路划分的典型应用

堆排序 Heap Sort​

原理​

利用堆这种数据结构。先建立最大堆，然后依次取出堆顶（最大值）放到数组末尾。

实现​

heapSort.ts
function heapSort(arr: number[]): number[] {
  const n = arr.length;

  // 1. 建立最大堆（从最后一个非叶子节点开始）
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 2. 依次取出堆顶，放到数组末尾
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];  // 堆顶与末尾交换
    heapify(arr, i, 0);  // 重新调整堆
  }

  return arr;
}

// 调整以 i 为根的子树为最大堆
function heapify(arr: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);  // 递归调整
  }
}
复杂度
  • 时间：O(nlog⁡n)O(n \log n)，任何情况都是
  • 空间：O(1)O(1)
  • 稳定：❌

排序算法选择指南​

场景推荐算法原因
数据量小（< 50）插入排序常数因子小，简单高效
需要稳定排序归并排序O(nlog⁡n)O(n \log n) 且稳定
一般场景快速排序平均性能最好
空间受限堆排序O(1)O(1) 空间，O(nlog⁡n)O(n \log n) 时间
基本有序插入排序最好情况 O(n)O(n)

常见面试问题​

Q1: 快速排序和归并排序的区别？​

对比项快速排序归并排序
思想先分区再递归先递归再合并
稳定性不稳定稳定
最坏时间O(n2)O(n^2)O(nlog⁡n)O(n \log n)
空间O(log⁡n)O(\log n)O(n)O(n)
适用场景一般场景需要稳定排序

Q2: 为什么快排比堆排序快？​

虽然都是 O(nlog⁡n)O(n \log n)，但快排的常数因子更小：

  1. 快排的内存访问是连续的，缓存命中率高
  2. 堆排序需要频繁跳跃访问，缓存不友好

Q3: 什么时候用计数排序/桶排序/基数排序？​

这些是非比较排序，适用于特定场景：

  • 计数排序：数据范围小（如 0-100 的整数）
  • 桶排序：数据分布均匀
  • 基数排序：整数或字符串排序

LeetCode 练习题​

难度题目链接
中等912. 排序数组LeetCode
中等215. 数组中的第K个最大元素LeetCode
简单88. 合并两个有序数组LeetCode
中等148. 排序链表LeetCode
困难315. 计算右侧小于当前元素的个数LeetCode

相关链接​