排序算法进阶：时间复杂度、稳定性与性能实测对比

排序算法进阶：时间复杂度、稳定性与性能实测对比

1. 回顾与目标

上一篇文章中，我们用 C 语言实现了冒泡排序、选择排序和插入排序，并分别编写了升序和降序两个版本。

那篇文章的重点是 “怎么实现”——我们关注的是代码怎么写、逻辑怎么走。而本文要回答三个更深入的问题：

这次的结论不用感觉说话，用数据说话。我们将通过实测数据来验证理论分析，让理解从抽象概念变为具体认知。

2. 三种排序的核心思想速览

2.1 冒泡排序

核心思想：每一轮遍历，相邻元素两两比较，把当前未排序部分的最大值"浮"到最后面。
特点：实现简单，但效率较低，适合教学演示。

2.2 插入排序

核心思想：像打牌时理牌。每次摸一张新牌，在已排序的手牌中从右往左找位置插入。
特点：对基本有序的数据效率极高，实际应用广泛。

2.3 选择排序

核心思想：每轮从未排序部分选出最小值，直接放到已排序部分的末尾。一轮只交换一次。
特点：交换次数最少，但不稳定。## 4. 稳定性：容易被忽略的考点

4.1 什么是稳定性

排序后，相等元素的相对顺序不变，就是稳定。

原始：[4, 2, 3(A), 1, 3(B)]
稳定： [1, 2, 3(A), 3(B)] ← A 仍在 B 前面
不稳定：[1, 2, 3(B), 3(A)] ← 顺序可能颠倒

实际意义：比如学生信息先按分数排序，再按学号排序。如果第二次排序用的算法不稳定，可能打乱第一次排好的顺序。

4.2 三种排序的稳定性

冒泡：稳定

只交换相邻元素，条件是 arr[j] > arr[j+1]。相等元素永远不会交换。

插入：稳定

从右往左找位置，条件是 arr[j] > key。相等元素不触发移动，key 插在相等元素后面。

选择：不稳定

每轮找到最小值后，执行一次"跳远式交换"，可能跨过相等元素。

[5(A), 8, 5(B), 2]
第1轮：最小是 2（位置3），和位置0交换 → [2, 8, 5(B), 5(A)]
5(A) 被换到了 5(B) 后面，相对顺序颠倒。

5. 性能实测：让数据说话

5.1 测试代码（三种排序均为升序）

#include <stdio.h> // 包含 printf 函数
#include <stdlib.h> // 包含 malloc、free、srand、rand 函数
#include <time.h> // 包含 clock、clock_t、CLOCKS_PER_SEC 函数

// 冒泡排序（升序，优化版）
void bubbleSort(int arr[], int len) {
// 外层循环：控制排序轮数，共 len-1 轮
for (int i = 0; i < len – 1; i++) {
int flag = 0; // 标记本轮是否发生过交换

// 内层循环：相邻比较，把较大值往后"冒"
for (int j = 0; j < len – 1 – i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻两个元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1;
}
}

// 本轮无交换，数组已有序，提前结束
if (flag == 0) break;
}
}

// 插入排序（升序）
void insertionSort(int arr[], int len) {
// i：当前要插入的元素下标，从第 2 个元素（下标 1）开始
for (int i = 1; i < len; i++) {
int key = arr[i]; // 暂存当前要插入的值
int j = i – 1; // j 指向已排序部分的最后一个元素

// 在已排序部分从右往左找插入位置
// 如果已排序元素比 key 大，就右移一位，给 key 腾位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 元素右移一位
j—; // 继续向左比较
}

// 找到插入位置（j+1），放入 key
arr[j + 1] = key;
}
}

// 选择排序（升序）
void selectionSort(int arr[], int len) {
// i：当前要确定的位置，最后一个位置自动归位，所以 i < len-1
for (int i = 0; i < len – 1; i++) {
int minIndex = i; // 假设当前位置就是最小值

// 在剩余未排序部分中找真正的最小值
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小值的下标
}
}

// 如果找到的最小值不在当前位置，交换
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

// 主函数：性能测试
int main() {
int sizes[] = {1000, 5000, 10000}; // 测试三种数据规模
int n_tests = 3; // 共 3 组测试

// 打印表头
printf("%-10s %-12s %-12s %-12s\\n", "数据量", "冒泡(ms)", "选择(ms)", "插入(ms)");
printf("———————————————–\\n");

// 依次测试每种数据规模
for (int t = 0; t < n_tests; t++) {
int n = sizes[t]; // 当前数据量

// 动态分配三份相同数据的数组，保证对比公平
int *arr1 = (int*)malloc(n * sizeof(int));
int *arr2 = (int*)malloc(n * sizeof(int));
int *arr3 = (int*)malloc(n * sizeof(int));

// 生成随机数据，三份数组初始值完全相同
srand(42); // 固定随机种子，保证每次运行结果可复现
for (int i = 0; i < n; i++) {
arr1[i] = rand() % 10000; // 生成 0~9999 的随机数
arr2[i] = arr1[i];
arr3[i] = arr1[i];
}

clock_t start, end; // 用于计时的变量
double t1, t2, t3; // 存储三种排序的耗时（毫秒）

// 测试冒泡排序
start = clock(); // 记录开始时间
bubbleSort(arr1, n); // 执行排序
end = clock(); // 记录结束时间
t1 = (double)(end – start) / CLOCKS_PER_SEC * 1000; // 转换为毫秒

// 测试选择排序
start = clock();
selectionSort(arr2, n);
end = clock();
t2 = (double)(end – start) / CLOCKS_PER_SEC * 1000;

// 测试插入排序
start = clock();
insertionSort(arr3, n);
end = clock();
t3 = (double)(end – start) / CLOCKS_PER_SEC * 1000;

// 打印当前数据规模的测试结果
printf("%-10d %-12.2f %-12.2f %-12.2f\\n", n, t1, t2, t3);

// 释放动态分配的内存
free(arr1);
free(arr2);
free(arr3);
}
return 0;
}

在这里插入图片描述

5.2 实测结果

环境：VMware Workstation 17 + Ubuntu 24.04 LTS，4 vCPU / 8GB 内存，gcc -O0

5.3 结果分析

上述表格中的数据是通过运行前面提供的测试代码，在控制台中实际测量得到的。为了更直观地展示程序运行效果，下面是一张模拟的终端输出截图：

图：程序运行后的控制台输出，清晰显示了三种排序算法在不同数据规模下的耗时对比慢。** 每次比较只要条件成立就交换，一次交换三次赋值，总成本最高。

选择比冒泡快。 每轮只交换一次，但比较次数仍是 O(n²)。

插入最快。 内层是"移位赋值"而不是交换，常数因子最小。随机数据下平均只扫一半就找到位置。

数据量从 1000 到 10000，数据量变为 10 倍，三种排序耗时均变为约 60 倍（冒泡 1.93→116.57）。这符合 O(n²) 的预期：数据量 10 倍，时间约 100 倍。由于数据量较小时函数调用等固定开销占比更大，实测的 60 倍属于合理范围。

从最新数据可以看出：

• 插入排序在三种算法中表现最优，10000 个数据仅需 26.93ms
• 选择排序次之，比冒泡快约 2.6 倍
• 冒泡排序虽然经过优化，但交换操作频繁，性能仍最差

6. 总结与选型建议

7. 我的收获与思考

在撰写这篇博客之前，我对这三种排序算法的理解仅停留在"能用代码实现"的层面。通过这次深入分析，我获得了以下收获：

7.1 理论到实践的跨越

• 时间复杂度不再是抽象概念：通过实测数据，我直观地看到了 O(n²) 的实际含义——数据量增加 10 倍，耗时增加约 60 倍
• 稳定性变得具体：在纸上模拟选择排序的交换过程时，看到 5(A) 被"跳远交换"到 5(B) 后面，稳定性这个抽象概念瞬间变得生动

7.2 性能差异的深层原因

• 冒泡排序的瓶颈在于频繁的交换操作（每次交换需要三次赋值）
• 插入排序的优势在于移位赋值，常数因子最小
• 选择排序虽然比较次数多，但交换次数最少

7.3 学习方法的反思

以前只是记住"插入排序比冒泡快"这个结论，但通过亲手测试（冒泡 116.57ms vs 插入 26.93ms），这个概念从记忆变成了直觉。这种"知道为什么"的理解深度，远胜于单纯的"知道答案"。

写技术博客最大的价值在于：代码跑通只是第一步，能够清晰解释原理、分析优劣、给出实用建议，才算真正掌握了知识。这个过程强迫我理清思路、填补认知空白，这正是我坚持写作的原因。## 8. 下篇预告

O(n²) 在万级数据量已经吃力。下一篇将学习快速排序——平均时间复杂度 O(n log n)，也是 C 标准库 qsort 的底层实现。同样会实测对比，看看它比插入排序快多少。