返回主页

三大基础排序算法详解

汇总一下三大基础排序算法的写法以及时间空间复杂度、稳定性

Markdown发布于 2026/08/20编辑于 2026/10/29#排序

在学习信息学竞赛的路上,选择排序、插入排序、冒泡排序是逃不开的三座大山。它们的时间复杂度都是 O(n²),背后的思路和应用场景截然不同,这里和同学们一起汇总一下写法:

约定:本文所有代码均采用信奥常见写法,数组下标从 1 开始,有效数据存储在 a[1] ~ a[n],a[0] 仅作为占位不使用。使用 swap() 进行交换,需包含 <algorithm> 头文件。

冒泡排序

原理

冒泡排序的核心思想是:相邻两两比较,大的元素像泡泡一样往后"冒"。

每一轮都会把当前未排序部分的最大值"冒"到最后面。

代码

这里加入了 flag 优化:如果某一轮没有发生任何交换,说明数组已经有序,可以提前退出。

C++
void bubble_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        bool flag = true;                 // 假设本轮已有序
        for (int j = 1; j <= n - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);     // 大的往后冒
                flag = false;             // 发生交换,说明还没排好
            }
        }
        if (flag) break;                  // 整轮无交换,提前结束
    }
}

特点

项目说明
平均时间复杂度O(n²)
最坏时间复杂度O(n²)
最好时间复杂度O(n)(配合 flag 优化,数据已有序时一轮即停)
空间复杂度O(1),原地排序
稳定性✅ 稳定(相邻交换,不改变相等元素的相对顺序)

适用场景:数据量小,或数据基本有序。代码逻辑最直观,非常适合作为排序算法的入门学习。

插入排序

原理

插入排序的核心思想是:将当前元素插入到前面已经排好序的序列中的正确位置。

就像打扑克牌时整理手牌一样,每摸到一张新牌,就把它插到手中已有牌的正确位置上。

代码

插入排序有两种常见写法:

  1. 后移法:交换次数更少,效率略高,但代码稍长。
C++
void insert_sort(int a[], int n) {
    for (int i = 2; i <= n; i++) {      // 从第2个元素开始,依次插入前面有序序列
        int key = a[i];                 // 记录当前要插入的值
        int j = i - 1;                  // 从已排序部分的最后一个位置往前找

        // 将比 key 大的元素往后移动一位
        while (j >= 1 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        // 找到插入位置,将 key 放进去
        a[j + 1] = key;
    }
}
  1. 相邻交换法:使用 swap 交换,代码更简洁。
C++
void insert_sort(int a[], int n) {
    for (int i = 2; i <= n; i++) {
        // 将 a[i] 向左交换到正确位置
        for (int j = i; j >= 2 && a[j] < a[j - 1]; j--) {
            swap(a[j], a[j - 1]);
        }
    }
}

特点

项目说明
平均时间复杂度O(n²)
最坏时间复杂度O(n²)
最好时间复杂度O(n)(数据已有序时,只比较不交换)
空间复杂度O(1),原地排序
稳定性✅ 稳定(相邻交换,不改变相等元素的相对顺序)

适用场景:数据量小,或数据基本有序时效率极高(接近 O(n)),是三大排序中在部分有序数据下表现最好的。

选择排序

原理

选择排序的核心思想是:每一轮从未排序的部分中选出最小的元素,放到已排序部分的末尾。

用一句话记忆:"每轮选最小的放前面"。

代码

C++
void select_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int idx = i;                      // 假设当前位置最小
        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[idx])
                idx = j;   // 找到更小的,更新下标
        }
        if (idx != i) swap(a[i], a[idx]); // 将最小元素交换到前面
    }
}

特点

项目说明
平均时间复杂度O(n²)
最坏时间复杂度O(n²)
最好时间复杂度O(n²)
空间复杂度O(1),原地排序
稳定性❌ 不稳定(远距离交换可能改变相等元素的相对顺序)
交换次数最少(最多 n-1 次),当交换操作代价高时优先考虑

适用场景:数据量小,且对稳定性没有要求时适用。


三大排序横向对比总结

对比项选择排序插入排序冒泡排序
平均时间复杂度O(n²)O(n²)O(n²)
最坏时间复杂度O(n²)O(n²)O(n²)
最好时间复杂度O(n²)O(n)O(n)(优化后)
空间复杂度O(1)O(1)O(1)
稳定性❌ 不稳定✅ 稳定✅ 稳定
交换次数最少(≤ n-1次)较多(平均 n²/4 次)较多(平均 n²/2 次)
数据基本有序时仍为 O(n²)效率最高效率较高
核心记忆选最小放前面像打牌理牌大的往后冒

写在最后

三大基础排序虽然在实际竞赛中很少直接使用(因为 sort() 更高效),但它们是理解更复杂排序算法(如快速排序、归并排序)的基石。

当你彻底理解了这三兄弟,就可以向 快速排序、归并排序、堆排序 等更高效的算法发起挑战了!🚀