基础排序算法

Kingcq2026/7/10大约 9 分钟

引入：为什么需要先学排序

到目前为止，你已经能熟练操作数组、链表、栈和队列了。但很多时候，光把数据存起来还不够，你还需要让它们有序。

比如成绩表想按分数从高到低排、字典里的单词要按字母顺序排、商品列表要按价格排序。这些场景都离不开排序算法。排序也是很多更复杂算法的基础：二分查找要求数组有序，很多贪心、分治算法也要先排序。

这一篇我会带你实现三种最基础、最经典的排序算法：冒泡排序、选择排序和插入排序。它们思路简单，但已经足以帮你理解“算法复杂度”这个核心概念。

学习目标

理解冒泡、选择、插入三种排序的基本思想。
能独立写出它们的 C 语言实现。
知道什么是排序的稳定性。
会分析三种排序的时间复杂度和空间复杂度，并理解为什么复杂度分析很重要。

冒泡排序：相邻元素比大小

思路

冒泡排序就像水里冒泡泡一样，每一轮把当前未排序部分里最大的元素“冒”到最右边。

具体做法是：从左到右，依次比较相邻两个元素，如果左边比右边大，就交换它们。一轮结束后，最大的元素一定在最右边。下一轮就不用管最后一个元素了，继续对前面的元素重复这个过程。

名字的由来

因为每一轮最大的元素会像泡泡一样“浮”到最顶端（数组末尾），所以叫冒泡排序。

代码实现

#include <stdio.h>

void bubble_sort(int a[], int n) {
    int i, j, tmp;
    for (i = 0; i < n - 1; i++) {        // 需要 n-1 轮
        for (j = 0; j < n - 1 - i; j++) { // 每轮比较的范围逐渐缩小
            if (a[j] > a[j + 1]) {       // 左边更大就交换
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

int main(void) {
    int a[] = {5, 3, 8, 4, 2};
    int n = sizeof(a) / sizeof(a[0]);
    int i;

    bubble_sort(a, n);

    printf("冒泡排序结果：");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

输出：

冒泡排序结果：2 3 4 5 8

一个可以优化的小细节

如果某一轮完全没有发生交换，说明数组已经有序了，后面不用再排。可以加入一个标志位提前结束：

void bubble_sort_optimized(int a[], int n) {
    int i, j, tmp;
    int swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 已经有序，直接退出
    }
}

选择排序：每次选最小的放到前面

思路

选择排序更直接：每一轮从剩下的元素中找出最小的那个，把它放到当前未排序部分的最前面。

比如第一轮找到整个数组的最小值，放到 a[0]；第二轮从 a[1] 开始找最小值，放到 a[1]，以此类推。

代码实现

#include <stdio.h>

void selection_sort(int a[], int n) {
    int i, j, min_idx, tmp;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;                      // 假设当前位置最小
        for (j = i + 1; j < n; j++) {     // 在剩余部分找更小的
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        // 把最小值交换到前面
        if (min_idx != i) {
            tmp = a[i];
            a[i] = a[min_idx];
            a[min_idx] = tmp;
        }
    }
}

int main(void) {
    int a[] = {5, 3, 8, 4, 2};
    int n = sizeof(a) / sizeof(a[0]);
    int i;

    selection_sort(a, n);

    printf("选择排序结果：");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

输出：

选择排序结果：2 3 4 5 8

插入排序：像整理扑克牌

思路

插入排序的思想很生活化：想象你手里拿着一副扑克牌，一张一张地整理。每次拿到一张新牌，你把它插入到已经排好序的牌中的正确位置。

在数组中，我们假设前 i 个元素已经有序，然后把第 i+1 个元素插入到合适的位置。为了腾出位置，可能需要把比它大的元素依次往后挪。

代码实现

#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;
        // 把比 key 大的元素往后移
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;             // 放到正确位置
    }
}

int main(void) {
    int a[] = {5, 3, 8, 4, 2};
    int n = sizeof(a) / sizeof(a[0]);
    int i;

    insertion_sort(a, n);

    printf("插入排序结果：");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

输出：

插入排序结果：2 3 4 5 8

稳定性：什么是稳定排序

如果数组中有两个相等的元素，比如 {3, 2, 3*, 1}（我用 3* 标记第二个 3），排序后原来在后面的 3* 仍然在后面，这样的排序就叫稳定排序。

冒泡排序：稳定。相等时不交换，相对顺序不变。
选择排序：不稳定。比如 {2, 2*, 1}，第一次选择会把 1 和第一个 2 交换，导致两个 2 的相对顺序改变。
插入排序：稳定。相等时不移动，后面的元素插入到相等元素的后面。

稳定性在需要对多个关键字排序时很有用，比如先按成绩排序，再按学号排序，稳定排序能保证前面的排序结果不被打乱。

时间复杂度和空间复杂度分析

为什么要分析复杂度

学完这三种排序，你可能会问：它们都能把数组排好序，有什么区别？

如果只是对几十个元素排序，确实区别不大。但如果数据量变成一万、十万、一百万，不同算法的差距就会非常明显。复杂度分析就是让我们在不实际运行的情况下，预估算法随着数据规模增大会多慢、多占内存。

复杂度与运行环境无关

同样的算法，在快电脑和慢电脑上运行时间不同；但复杂度描述的是“运行时间随数据规模增长的趋势”，与具体机器无关。这样我们才能客观地比较算法。

三种排序的复杂度

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n)（优化后已有序）	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)（已有序）	O(n²)	O(n²)	O(1)	稳定

三种排序都只需要几个额外变量，所以空间复杂度都是 O(1)，也叫原地排序。

它们的时间复杂度都是 O(n²)。也就是说，如果数据量翻倍，最坏情况下运行时间大约会变成原来的 4 倍。对于大规模数据，这三种排序都不够快，后面我们会学习更高效的排序算法，比如快速排序和归并排序。

三种排序的适用场景

冒泡排序：思路最简单，适合教学理解。实际工程中很少用，但优化后的提前退出在接近有序的数据上有一定效果。
选择排序：交换次数最少，最多只交换 n-1 次。如果交换元素的代价很大（比如元素是结构体），选择排序有一点点优势，但稳定性差。
插入排序：对于小规模或基本有序的数据非常高效。很多高级排序算法在子数组很小时会切换成插入排序。

常见错误与注意事项

冒泡排序的内层循环边界：应该是 j < n - 1 - i，不要忘记减去已经排好序的 i 个元素。
选择排序的下标更新：min_idx 要及时更新，最后只交换一次，不要每找到一个更小的就交换。
插入排序的 while 条件：别忘了 j >= 0，否则会数组越界访问。
稳定性的理解：稳定性不是指算法正不正确，而是指相等元素的相对顺序是否保持不变。

排序算法还要说明比较规则

“升序”不是所有类型天然拥有的。排序结构体时，需要决定按成绩、姓名还是多个字段组合。比较器必须保持一致：不能出现 a < b、b < c，却又认为 c < a。

C 标准库提供 qsort：

int compare_int(const void *left, const void *right) {
    int a = *(const int *)left;
    int b = *(const int *)right;
    return (a > b) - (a < b);
}