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

排序算法进阶时间复杂度、稳定性与性能实测对比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[j1]。相等元素永远不会交换。插入稳定从右往左找位置条件是 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 测试代码三种排序均为升序#includestdio.h// 包含 printf 函数#includestdlib.h// 包含 malloc、free、srand、rand 函数#includetime.h// 包含 clock、clock_t、CLOCKS_PER_SEC 函数// 冒泡排序升序优化版voidbubbleSort(intarr[],intlen){// 外层循环控制排序轮数共 len-1 轮for(inti0;ilen-1;i){intflag0;// 标记本轮是否发生过交换// 内层循环相邻比较把较大值往后冒for(intj0;jlen-1-i;j){if(arr[j]arr[j1]){// 交换相邻两个元素inttemparr[j];arr[j]arr[j1];arr[j1]temp;flag1;}}// 本轮无交换数组已有序提前结束if(flag0)break;}}// 插入排序升序voidinsertionSort(intarr[],intlen){// i当前要插入的元素下标从第 2 个元素下标 1开始for(inti1;ilen;i){intkeyarr[i];// 暂存当前要插入的值intji-1;// j 指向已排序部分的最后一个元素// 在已排序部分从右往左找插入位置// 如果已排序元素比 key 大就右移一位给 key 腾位置while(j0arr[j]key){arr[j1]arr[j];// 元素右移一位j--;// 继续向左比较}// 找到插入位置j1放入 keyarr[j1]key;}}// 选择排序升序voidselectionSort(intarr[],intlen){// i当前要确定的位置最后一个位置自动归位所以 i len-1for(inti0;ilen-1;i){intminIndexi;// 假设当前位置就是最小值// 在剩余未排序部分中找真正的最小值for(intji1;jlen;j){if(arr[j]arr[minIndex]){minIndexj;// 更新最小值的下标}}// 如果找到的最小值不在当前位置交换if(minIndex!i){inttemparr[i];arr[i]arr[minIndex];arr[minIndex]temp;}}}// 主函数性能测试intmain(){intsizes[]{1000,5000,10000};// 测试三种数据规模intn_tests3;// 共 3 组测试// 打印表头printf(%-10s %-12s %-12s %-12s\n,数据量,冒泡(ms),选择(ms),插入(ms));printf(-----------------------------------------------\n);// 依次测试每种数据规模for(intt0;tn_tests;t){intnsizes[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(inti0;in;i){arr1[i]rand()%10000;// 生成 0~9999 的随机数arr2[i]arr1[i];arr3[i]arr1[i];}clock_tstart,end;// 用于计时的变量doublet1,t2,t3;// 存储三种排序的耗时毫秒// 测试冒泡排序startclock();// 记录开始时间bubbleSort(arr1,n);// 执行排序endclock();// 记录结束时间t1(double)(end-start)/CLOCKS_PER_SEC*1000;// 转换为毫秒// 测试选择排序startclock();selectionSort(arr2,n);endclock();t2(double)(end-start)/CLOCKS_PER_SEC*1000;// 测试插入排序startclock();insertionSort(arr3,n);endclock();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);}return0;}在这里插入图片描述5.2 实测结果环境VMware Workstation 17 Ubuntu 24.04 LTS4 vCPU / 8GB 内存gcc -O0数据量冒泡(ms)选择(ms)插入(ms)10001.930.740.44500030.5511.267.0810000116.5744.4926.935.3 结果分析上述表格中的数据是通过运行前面提供的测试代码在控制台中实际测量得到的。为了更直观地展示程序运行效果下面是一张模拟的终端输出截图图程序运行后的控制台输出清晰显示了三种排序算法在不同数据规模下的耗时对比慢。** 每次比较只要条件成立就交换一次交换三次赋值总成本最高。选择比冒泡快。每轮只交换一次但比较次数仍是 O(n²)。插入最快。内层是移位赋值而不是交换常数因子最小。随机数据下平均只扫一半就找到位置。数据量从 1000 到 10000数据量变为 10 倍三种排序耗时均变为约 60 倍冒泡 1.93→116.57。这符合 O(n²) 的预期数据量 10 倍时间约 100 倍。由于数据量较小时函数调用等固定开销占比更大实测的 60 倍属于合理范围。从最新数据可以看出插入排序在三种算法中表现最优10000 个数据仅需 26.93ms选择排序次之比冒泡快约 2.6 倍冒泡排序虽然经过优化但交换操作频繁性能仍最差6. 总结与选型建议场景推荐理由数据量很小100插入简单常数因子小数据基本有序插入接近 O(n)要求稳定插入或冒泡选择不稳定不在乎稳定数据量小选择交换次数少数据量 10000都别用该学快排了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 的底层实现。同样会实测对比看看它比插入排序快多少。