袋鼠知识

主题

第七章 排序算法 ​

📖 ⏱️ 预计阅读时长

1. 为什么排序算法值得单独成章 ​

排序是数据处理中最基础、最常见的操作之一。所谓排序，就是按照某种关键字规则，把一组原本无序或部分有序的数据，重新排列成升序或降序序列。表面上看，排序只是“把数据排好顺序”，但从算法角度看，它实际上集中体现了算法设计中的许多核心思想，包括比较、交换、分治、递归、选择、局部有序、稳定性与复杂度分析。

在现实应用中，排序无处不在。成绩排名、商品价格展示、搜索结果排序、日志按时间排列、数据库中的 ORDER BY、操作系统调度中的优先级整理，都与排序思想密切相关。正因为排序既重要又典型，所以在数据结构与算法课程中，通常要单独用一个完整章节来系统讲解。

2. 排序的基本概念 ​

2.1 内部排序与外部排序 ​

  1. 内部排序：待排序记录全部存放在内存中，排序过程主要受 CPU 运算与内存访问影响。
  2. 外部排序：待排序数据量大到无法一次全部装入内存，需要借助外存分批处理。

本章讨论的重点主要是内部排序。

2.2 稳定性 ​

若序列中存在多个关键字相同的元素，排序后这些相同关键字元素的相对先后次序保持不变，则称该排序算法是稳定的；反之称为不稳定的。

稳定性在“按多个字段分层排序”时尤为重要。例如先按班级排序，再按成绩排序，如果第二次排序算法稳定，则同成绩同学的班级相对次序不会被破坏。

2.3 原地排序 ​

若排序过程中只使用少量辅助空间，而不需要额外开辟与数据规模同级别的存储空间，则常称为原地排序。原地排序通常更节省空间，但不一定在时间上最优。

2.4 排序算法评价指标 ​

评价排序算法通常从以下几个方面进行：

  1. 时间复杂度。
  2. 空间复杂度。
  3. 稳定性。
  4. 是否原地。
  5. 对原始数据分布是否敏感。
  6. 在小规模数据和大规模数据下的实际表现。

排序算法之所以值得深入研究，正是因为这些指标之间往往不能同时最优。一个算法可能时间复杂度好，但需要较多额外空间；另一个算法可能原地完成，但不稳定；还有的算法平均性能优秀，却在极端情况下可能退化。因此，排序学习的关键不是死记复杂度，而是理解各种代价之间的平衡关系。

3. 排序算法总览图 ​

上图说明，排序算法并不是一组彼此孤立的方法，而是可以按思想分为插入类、选择类、交换类、分治类和分配类。理解这一分类后，记忆和比较会更有体系。

4. 冒泡排序 ​

4.1 基本思想 ​

冒泡排序通过反复比较相邻两个元素，并在顺序错误时交换它们，使较大元素像气泡一样逐步“浮”到序列末端。

4.2 过程特点 ​

  1. 每一趟排序都会把当前未排序部分中的最大元素放到正确位置。
  2. 若某一趟没有发生交换，则说明整体已经有序，可以提前结束。

4.3 复杂度与性质 ​

  1. 最好时间复杂度：O(n)。
  2. 最坏时间复杂度：O(n^2)。
  3. 空间复杂度：O(1)。
  4. 稳定性：稳定。

4.4 动图示意 ​

冒泡排序动图

4.5 C 语言示例 ​

c
#include <stdio.h>

void bubble_sort(int a[], int n) {
    int i, j, temp, swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    int n = sizeof(a) / sizeof(a[0]);
    int i;
    bubble_sort(a, n);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

4.6 适用评价 ​

冒泡排序思想直观，非常适合教学入门，但效率较低，不适合大规模数据排序。

从原理上说，冒泡排序的低效来自大量局部交换。每次交换只能让元素向正确位置移动一小步，因此当逆序较多时，需要反复多趟扫描才能完成排序。

5. 选择排序 ​

5.1 基本思想 ​

选择排序每一趟从未排序区间中选择最小元素，将其放到当前应在的位置。

5.2 复杂度与性质 ​

  1. 时间复杂度：无论最好还是最坏，通常都为 O(n^2)。
  2. 空间复杂度：O(1)。
  3. 稳定性：通常不稳定。

5.3 动图示意 ​

选择排序动图

5.4 特点分析 ​

选择排序的交换次数相对较少，但比较次数仍然很多，因此总体效率并不高。它的教学意义大于工程意义。

它之所以通常不稳定，是因为“选出最小元素再交换到前面”这一动作，可能会跨越多个相同关键字元素，从而破坏它们原有的相对次序。

6. 插入排序 ​

6.1 基本思想 ​

插入排序把序列分成“已排序区”和“未排序区”，每次从未排序区取出一个元素，插入到已排序区的合适位置。

这种思想很像整理扑克牌：每次拿起一张新牌，插入到手中已经排好序的位置。

6.2 复杂度与性质 ​

  1. 最好时间复杂度：O(n)。
  2. 最坏时间复杂度：O(n^2)。
  3. 空间复杂度：O(1)。
  4. 稳定性：稳定。

6.3 动图示意 ​

插入排序动图

6.4 C 语言示例 ​

c
#include <stdio.h>

void insertion_sort(int a[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = a[i];
        j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int main(void) {
    int a[] = {8, 4, 6, 2, 7};
    int n = sizeof(a) / sizeof(a[0]);
    int i;
    insertion_sort(a, n);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

6.5 适用评价 ​

插入排序在数据量较小或序列本身“基本有序”时，实际表现往往优于许多看上去更高级的算法。因此，它常被用作复杂排序算法在小区间上的补充策略。

原因在于，当序列已经接近有序时，每次插入所需移动的距离很短，插入排序就不再体现为典型的二次复杂度，而会表现出接近线性的效率。

7. 希尔排序 ​

7.1 基本思想 ​

希尔排序可以看作对插入排序的改进。它先让相距较远的元素进行分组比较和插入，使整体序列逐步趋于有序，最后再进行一次普通插入排序。

7.2 特点分析 ​

  1. 它利用“先粗调、再精调”的思想改善插入排序在远距离逆序情况下移动过多的问题。
  2. 时间复杂度与增量序列选择有关，通常优于简单 O(n^2) 算法，但不如高效的 O(n log n) 算法稳定。
  3. 通常不稳定。

希尔排序在工程中不如快速排序、归并排序和堆排序常见，但在理解“改进插入思想”时很有代表性。

8. 归并排序 ​

8.1 基本思想 ​

归并排序采用典型的分治思想：

  1. 先把序列不断二分，直到每个子序列长度为 1。
  2. 再把两个有序子序列逐步合并成更大的有序序列。

8.2 复杂度与性质 ​

  1. 时间复杂度：O(n log n)。
  2. 空间复杂度：O(n)。
  3. 稳定性：稳定。

8.3 分治结构图 ​

8.4 动图示意 ​

归并排序动图

8.5 C 语言示例 ​

c
#include <stdio.h>

void merge(int a[], int left, int mid, int right, int temp[]) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    while (j <= right) {
        temp[k++] = a[j++];
    }
    for (i = left; i <= right; i++) {
        a[i] = temp[i];
    }
}

void merge_sort(int a[], int left, int right, int temp[]) {
    int mid;
    if (left >= right) {
        return;
    }
    mid = (left + right) / 2;
    merge_sort(a, left, mid, temp);
    merge_sort(a, mid + 1, right, temp);
    merge(a, left, mid, right, temp);
}

int main(void) {
    int a[] = {9, 4, 7, 3, 1, 8};
    int temp[6];
    int i, n = 6;
    merge_sort(a, 0, n - 1, temp);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

8.6 适用评价 ​

归并排序时间复杂度稳定，且具有稳定性优势，非常适合需要稳定排序的场景，也适合链表排序和外部排序思想的展开。但它需要额外辅助空间，因此不是典型原地排序。

归并排序之所以稳定，是因为在合并两个有序子序列时，若遇到相等元素，完全可以约定优先取左侧元素，从而保持原有相对次序。这说明稳定性并不是“附带性质”，而是与算法的合并方式直接相关。

9. 快速排序 ​

9.1 基本思想 ​

快速排序同样采用分治思想。它先选取一个基准元素，把序列划分成“比基准小”和“比基准大”的两部分，再对子区间递归排序。

9.2 复杂度与性质 ​

  1. 平均时间复杂度：O(n log n)。
  2. 最坏时间复杂度：O(n^2)。
  3. 空间复杂度：递归栈平均 O(log n)。
  4. 稳定性：通常不稳定。

9.3 动图示意 ​

快速排序动图

9.4 C 语言示例 ​

c
#include <stdio.h>

void quick_sort(int a[], int left, int right) {
    int i, j, pivot, temp;
    if (left >= right) {
        return;
    }

    i = left;
    j = right;
    pivot = a[left];

    while (i < j) {
        while (i < j && a[j] >= pivot) {
            j--;
        }
        while (i < j && a[i] <= pivot) {
            i++;
        }
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    a[left] = a[i];
    a[i] = pivot;

    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

int main(void) {
    int a[] = {6, 2, 8, 1, 9, 3, 5};
    int i, n = sizeof(a) / sizeof(a[0]);
    quick_sort(a, 0, n - 1);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

9.5 适用评价 ​

快速排序通常被认为是工程实践中非常高效的通用排序算法之一，因为它平均性能优秀、缓存局部性较好、原地特性较强。但若基准选择不合理，例如每次都选到极端值，就可能退化。

它之所以在实践中往往很快，是因为划分操作通常在原数组上完成，额外空间小，而且递归后的子区间往往还能较好地利用缓存。但它的最坏情况依然提醒我们：平均性能好不代表任何输入都好。

10. 堆排序 ​

10.1 基本思想 ​

堆排序先把序列构造成堆，再反复取出堆顶元素并重建堆，从而得到有序序列。

10.2 复杂度与性质 ​

  1. 时间复杂度：O(n log n)。
  2. 空间复杂度：O(1)。
  3. 稳定性：不稳定。

10.3 动图示意 ​

堆排序动图

10.4 特点分析 ​

堆排序的优势在于时间复杂度稳定且空间开销小，但由于频繁调整堆结构，其常数因子往往不如快速排序友好，因此在通用排序中常不是默认首选。

从思想上看，堆排序相当于把“反复找出当前最大值或最小值”的过程结构化。若用普通方法反复寻找最值，每次都可能要线性扫描；而堆则把这种需求预先编码在结构中，使得取堆顶和重建都更高效。

11. 计数排序与基数排序 ​

11.1 计数排序 ​

计数排序适用于关键字范围较小的整数序列。它统计每个取值出现次数，再根据计数结果重建有序序列。

其特点是：

  1. 时间复杂度通常为 O(n + k)，其中 k 是关键字范围。
  2. 不是基于比较的排序。
  3. 当关键字范围过大时，空间开销会明显上升。

11.2 基数排序 ​

基数排序按位或按位组对元素进行多轮分配和收集，通常适用于整数或固定长度字符串。

其特点是：

  1. 不依赖元素之间的直接比较。
  2. 常与计数排序等稳定排序配合使用。
  3. 效率与位数长度和分配方式有关。

12. 常见排序算法比较 ​

算法最好时间平均时间最坏时间空间复杂度稳定性备注
冒泡排序O(n)O(n^2)O(n^2)O(1)稳定入门直观
选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定交换次数少
插入排序O(n)O(n^2)O(n^2)O(1)稳定小规模数据常用
希尔排序依增量而定一般优于 O(n^2)依增量而定O(1)不稳定插入排序改进
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定分治典型
快速排序O(n log n)O(n log n)O(n^2)O(log n)不稳定实战常用
堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定利用堆结构
计数排序O(n + k)O(n + k)O(n + k)O(n + k)可稳定关键字范围小
基数排序与位数有关与位数有关与位数有关较大可稳定非比较排序

13. 排序算法的选择思路 ​

13.1 小规模数据 ​

小规模数据时，插入排序往往足够好，且实现简单。

13.2 需要稳定性 ​

若必须保持相同关键字的原有相对顺序，应优先考虑插入排序、归并排序、计数排序等稳定算法。

13.3 追求综合性能 ​

若目标是通用场景下的整体效率，快速排序通常是高频选择；若还要求最坏复杂度稳定，则更应考虑归并排序或堆排序。

13.4 关键字范围有限 ​

若数据是整数，且取值范围不大，则计数排序可能获得明显优势。

13.5 为什么教材里总反复比较“稳定”和“不稳定” ​

这是因为稳定性不仅影响排序本身，还影响多关键字处理。例如先按次关键字排，再按主关键字排时，若第二次排序稳定，则第一次排序形成的相对顺序不会被破坏。数据库、报表处理和业务数据整理中，这一点非常重要。

14. 本章小结 ​

排序算法既是数据结构课程的重要组成部分，也是算法思想训练的集中体现。冒泡、选择、插入代表了简单基础的排序方法；归并和快速体现了分治思想；堆排序把树形结构用于排序；计数排序和基数排序则说明排序并不一定完全依赖比较。掌握本章后，不应只停留在“记住几个名字和复杂度”的层面，而应能根据稳定性、时间复杂度、空间复杂度和数据特征，判断哪种排序更适合具体问题。

15. 配图与动图来源 ​

  1. 冒泡排序动图：Wikimedia Commons, Bubble-sort-example-300px.gif
  2. 选择排序动图：Wikimedia Commons, AnimazioneSelectionSort.gif
  3. 插入排序动图：Wikimedia Commons, Insertion_sort_animation.gif
  4. 归并排序动图：Wikimedia Commons, Merge-sort-example-300px.gif
  5. 快速排序动图：Wikimedia Commons, Quicksort-example.gif
  6. 堆排序动图：Wikimedia Commons, Heapsort-example.gif