Decade
常用排序算法的选择之道
Zhongjun Qiu 元婴开发者
  2025-10-03 14:08:40   2025-10-05 00:27:36    3.4k Words  13 Mins  

本文深入探讨常用排序算法的原理、实现及其优缺点，面试专用。

排序算法是计算机科学的基石之一。理解不同排序算法的特性，不仅能帮助我们写出更高效的代码，也是衡量工程师基本功的重要标准。本文将排序算法分为两大类，并逐一解析。

  • 比较排序 (Comparison Sorts): 通过比较元素之间的大小关系来排序，其时间复杂度的理论下界为 O(nlog n)。
  • 非比较排序 (Non-comparison Sorts): 不通过比较来排序，它们利用元素的自身特性（如数值大小、构成部分），在特定条件下可以突破 O(nlog n) 的限制。

比较排序算法

插入排序 (Insertion Sort)

插入排序将数组分为“已排序”和“未排序”两部分。它不断从未排序部分取出一个元素，并将其插入到已排序部分的正确位置。

这个过程就像我们玩扑克牌时，一张张地拿起牌，并将它们插入到手中已排好序的牌里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertionSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 从后向前扫描，为 key 找到插入位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
  • 时间复杂度: O(n2)。在数据基本有序时，接近 O(n)。
  • 空间复杂度: O(1)。
  • 稳定性: 稳定。

优点: 实现简单，空间开销小，对于小规模或基本有序的数据集效率很高。 缺点: 在大规模乱序数据集上性能不佳。

归并排序 (Merge Sort)

归并排序是分治思想的经典应用。它将数组递归地对半切分，直到子数组只包含一个元素，然后自底向上地将这些有序的子数组两两合并，最终得到一个完全有序的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    mergeSort(arr, 0, arr.length - 1);
}

private static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    // 使用双指针合并两个有序子数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

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

    // 将合并后的结果拷回原数组
    System.arraycopy(temp, 0, arr, left, temp.length);
}
  • 时间复杂度: O(nlog n) (包括最坏情况)。
  • 空间复杂度: O(n)，需要辅助数组。
  • 稳定性: 稳定。

优点: 性能稳定，最坏情况表现优秀。 缺点: 需要额外的存储空间。

快速排序 (Quick Sort)

快速排序同样采用分治策略，但其核心在于“划分”（Partition）。它选择一个“基准”（Pivot）元素，将数组重新排列，使得所有小于基准的元素都在其左边，所有大于基准的元素都在其右边。然后对左右两个子数组递归地应用此过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 基础版本
public static void quickSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, ++i, high);
    return i;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
  • 时间复杂度: 平均 O(nlog n)，最坏 O(n2)。
  • 空间复杂度: O(log n)，递归栈的开销。
  • 稳定性: 不稳定。

快速排序的优化

基础快排有两个主要问题： 1. 最坏情况退化: 如果每次选取的基准都是当前数组的最小或最大值（例如，在一个已排序的数组上），递归树会变得极不平衡，时间复杂度退化到 O(n2)。 - 解决方案: 随机化基准。在划分前，随机选择一个元素与末尾元素交换，作为基准。这使得最坏情况的出现概率降至极低。

  1. 大量重复元素: 当数组中存在大量重复元素时，即使随机化，划分出的两个子数组也可能极不平衡，同样导致性能退化。
    • 解决方案: 三向切分 (3-way Partitioning)。将数组划分为三部分：小于、等于、大于基准。之后只需递归排序小于和大于的两部分，等于基准的部分自然就位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 优化版：随机化 + 三向切分
public static void optimizedQuickSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    quickSort3Way(arr, 0, arr.length - 1);
}

private static void quickSort3Way(int[] arr, int low, int high) {
    if (l >= r) return 0;
    int ridx = new Random().nextInt(l, r + 1);
    swap(ridx, r, nums);
    int p = nums[r], lowi = l - 1, upi = r + 1;
    for (int i = l;i < r;i++) {
        if (nums[i] < p) swap(++lowi, i, nums);
    }
    swap(lowi + 1, r, nums);
    for (int i = r;i > lowi + 1;i--) {
        if (nums[i] > p) swap(--upi, i, nums);
    }
    quickSort3Way(l, lowi, nums, k);
    quickSort3Way(upi, r, nums, k);
}

优点: 平均性能极佳，是原地排序，空间开销小，常数因子低，通常是同阶算法中最快的。 缺点: 最坏情况性能差（尽管可优化），且不稳定。

堆排序 (Heap Sort)

堆排序利用了堆这种数据结构的特性。它首先将待排序数组构建成一个大顶堆（Max-Heap），此时堆顶元素（数组第一个元素）就是最大值。然后，它将堆顶元素与数组末尾元素交换，并将堆的大小减一，再对堆顶进行调整（heapify），使其重新满足大顶堆性质。重复此过程，直到堆为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void heapSort(int[] nums, int k) {
    int n = nums.length;
    for (int i = n / 2 - 1;i >= 0;i--) {
        down(i, n, nums);
    }
    for (int i = 0;i < n;i++) {
        swap(0, n - i - 1, nums);
        down(0, n - i - 1, nums);
    }
    return nums[0];
}

private void down(int i, int n, int[] nums) {
    int ori = nums[i];
    while (2 * i + 1 < n) {
        int son = 2 * i + 1;
        if (son + 1 < n && nums[son + 1] < nums[son]) ++son;
        if (nums[son] < ori) {
            nums[i] = nums[son];
            i = son;
        } else {
            break;
        }
    }
    nums[i] = ori;
}
  • 时间复杂度: O(nlog n) (包括最坏情况)。
  • 空间复杂度: O(1)。
  • 稳定性: 不稳定。

优点: 性能稳定，空间开销小。 缺点: 在实际应用中，由于其缓存局部性差，常数因子较大，通常比同阶的快速排序慢。

非比较排序算法

这类算法通过利用元素的数值特性来工作，适用于特定类型的数据。

计数排序 (Counting Sort)

计数排序是一个高效的线性时间排序算法，但它要求输入数据必须是整数，并且范围不能过大。其核心思想是统计每个整数出现的次数，然后根据统计结果将元素放回原数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void countingSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    
    int[] count = new int[range];
    int[] output = new int[arr.length];
    
    // 1. 统计每个元素的出现次数
    for (int num : arr) {
        count[num - min]++;
    }
    
    // 2. 累加计数，确定每个元素最终的位置
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // 3. 反向填充 output 数组，以保证稳定性
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
    
    // 4. 拷回原数组
    System.arraycopy(output, 0, arr, 0, arr.length);
}
  • 时间复杂度: O(n + k)，其中 k 是整数范围。
  • 空间复杂度: O(k)。
  • 稳定性: 稳定。

优点: 在数据范围 k 不比 n 大很多的情况下，速度极快。 缺点: 适用场景有限，只能处理整数，且对内存敏感。

桶排序 (Bucket Sort)

桶排序是计数排序的升级版，它将数据分布到有限数量的“桶”里，然后对每个桶内的数据分别进行排序（可以使用其他排序算法，如插入排序），最后依次将每个桶中的数据拼接起来。

  • 时间复杂度: 平均 O(n + k)，其中 k 是桶的数量。最坏 O(n2)（如果所有数据都落入同一个桶）。
  • 空间复杂度: O(n + k)。
  • 稳定性: 取决于桶内排序算法是否稳定。

适用场景: 数据均匀分布的场景。

基数排序 (Radix Sort)

基数排序是一种非比较型整数排序算法，它将整数按位数切割成不同的数字，然后按每个位数分别比较。通常从最低位开始（LSD），对每一位进行一次排序（通常使用稳定的计数排序），直到最高位。

  • 时间复杂度: O(d ⋅ (n + k))，其中 d 是数字的最大位数，k 是基数（如十进制为10）。
  • 空间复杂度: O(n + k)。
  • 稳定性: 稳定。

适用场景: 适用于整数或可按位拆分的数据，特别是当数字位数 d 较小时。

排序算法的选择之道

没有“最好”的算法，只有“最合适”的算法。以下是决策指南：

1. 关键指标对比

算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 特点
插入排序 O(n2) O(n2) O(1) 稳定 对小规模或近乎有序的数据集极快
归并排序 O(nlog n) O(nlog n) O(n) 稳定 性能稳定，保证最坏情况，需要额外空间
快速排序 O(nlog n) O(n2) O(log n) 不稳定 原地排序，平均速度最快，但最坏差
堆排序 O(nlog n) O(nlog n) O(1) 不稳定 原地排序，保证最坏情况，但常数因子大
计数排序 O(n + k) O(n + k) O(k) 稳定 线性时间，但要求数据范围不能过大
桶排序 O(n + k) O(n2) O(n + k) 依赖内部 适用于均匀分布的数据
基数排序 O(d(n + k)) O(d(n + k)) O(n + k) 稳定 线性时间，适用于位数固定的整数

2. 决策流程

  1. 数据类型和范围？
    • 如果是整数且范围不大，计数排序是首选。
    • 如果是小数或字符串，且均匀分布，可考虑桶排序。
    • 如果是位数固定的整数，基数排序非常高效。
  2. 对稳定性有要求吗？
    • 是： 必须在稳定排序中选择，如归并排序、插入排序、计数/基数排序。例如，对一个包含（姓名，年龄）的对象列表按年龄排序，希望同龄人的相对顺序不变。
    • 否： 可以选择快速排序或堆排序。
  3. 对空间复杂度有要求吗？
    • 是（要求 O(1) 或 O(log n)）： 快速排序和堆排序是最佳选择。归并排序需要 O(n) 的额外空间，可能不适用。
    • 否： 归并排序的稳定性使其成为一个很好的备选项。
  4. 数据规模有多大？
    • 小规模 (n < 50)： 插入排序简单且高效，常被用作更复杂排序算法的“收尾”工作。
    • 大规模： 应选择 O(nlog n) 级别的算法。
  5. 对最坏情况性能有严格要求吗？
    • 是： 归并排序和堆排序能提供 O(nlog n) 的保证。快速排序有 O(n2) 的风险。
    • 否： 快速排序的平均性能通常是最好的。

3. 现代库中的混合策略

在实际工程中，各大语言的标准库往往结合多种算法的优点，形成混合排序策略，以达到在各种数据分布下的最优性能。

  • Introsort (内省排序): C++ 的 std::sort 采用此策略。
    • 它以快速排序开始，因为它平均速度最快。
    • 同时监测递归深度，当深度超过某个阈值（通常是 2log n）时，判断快速排序有退化为 O(n2) 的风险，便切换到堆排序，从而保证最坏情况下的时间复杂度为 O(nlog n)。
    • 当待排序的子数组规模变得很小时，切换到插入排序，因为对于小数组，插入排序的常数因子更小，效率更高。
  • Timsort: Java (Arrays.sort 对对象数组) 和 Python (list.sort, sorted()) 的标准排序算法。
    • 它是一种高度优化的混合稳定排序算法，结合了归并排序和插入排序。
    • 它首先在数据中寻找已经存在的连续升序或降序的片段（run），然后用插入排序扩展这些 run 的长度。
    • 最后，像归并排序一样，将这些 run 高效地合并起来。
    • Timsort 对真实世界中广泛存在的“部分有序”数据表现极其出色，同时保持了 O(nlog n) 的最坏情况性能和 O(n) 的空间复杂度（在最优情况下空间为 O(log n)）。

总结

  • 追求极致平均速度且不要求稳定性，选快速排序。
  • 要求稳定性或严格的最坏性能保证，选归并排序。
  • 要求原地排序且保证最坏性能，选堆排序。
  • 数据是小范围整数，选计数排序。
  • 数据基本有序或规模很小，用插入排序。

在不确定时，直接使用你所用语言标准库提供的排序函数，因为它们通常是经过高度优化的混合排序，足以应对绝大多数场景。

常用排序算法的选择之道
2025/10/03/MS-Sort/
Author
Zhongjun Qiu
Published
2025-10-03 14:08
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 比较排序算法
    1. 插入排序 (Insertion Sort)
    2. 归并排序 (Merge Sort)
    3. 快速排序 (Quick Sort)
      1. 快速排序的优化
    4. 堆排序 (Heap Sort)
  2. 非比较排序算法
    1. 计数排序 (Counting Sort)
    2. 桶排序 (Bucket Sort)
    3. 基数排序 (Radix Sort)
  3. 排序算法的选择之道
    1. 1. 关键指标对比
    2. 2. 决策流程
    3. 3. 现代库中的混合策略
    4. 总结
  1. 比较排序算法
    1. 插入排序 (Insertion Sort)
    2. 归并排序 (Merge Sort)
    3. 快速排序 (Quick Sort)
      1. 快速排序的优化
    4. 堆排序 (Heap Sort)
  2. 非比较排序算法
    1. 计数排序 (Counting Sort)
    2. 桶排序 (Bucket Sort)
    3. 基数排序 (Radix Sort)
  3. 排序算法的选择之道
    1. 1. 关键指标对比
    2. 2. 决策流程
    3. 3. 现代库中的混合策略
    4. 总结