排序与时间复杂度
一句话定义:排序是把一堆数按大小重新排队,时间复杂度是给这个排队过程称重的那杆秤。 抓住"比较次数随 n 怎么长"这条主线,排序题和复杂度题就都通了。
一、为什么这两件事要一起学
排序算法解决"怎么排",时间复杂度解决"排得有多快"。刷题也好、做项目也好,这两件事总被绑在一起问。
概念
回答的问题
常见的例子
排序算法
数据怎么排好
冒泡、选择、插入
时间复杂度
排好要多少步
O(n²)、O(n log n)
能排对不等于够用:三种排序都能排出正确答案,可数据量一大,慢的那个就顶不住了。
int a[5] = {5, 2, 4, 1, 3};
sort(a, a + 5); // 一行排完,但它是个黑盒,学排序要的是过程
💡 类比:排序是"把还回来的书按编号插回书架",复杂度是"这活儿要干多久"。10 本书随便插,1000 本书就得先想清楚从哪插。
二、时间复杂度:给算法称重
2.1 大 O 只关心"长得快不快"
int sum = 0;
for (int i = 0; i < n; i++) sum += a[i]; // 循环 n 次 → O(n)
没人关心这台机器上跑了几毫秒,因为换台电脑数字就变了。大 O 只看一件事:数据量 n 翻倍时,运算量涨几倍。
三条规矩:
-
常数扔掉:
3n + 5记作O(n) -
只留最高项:
n² + n + 100记作O(n²) -
默认说最坏:"冒泡排序是
O(n²)",说的是最坏情况
2.2 复杂度阶梯
快 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) 慢
复杂度
n = 1000 时大约几步
常见的例子
O(1)
1 步
取 a[5] 的值
O(log n)
约 10 步
二分查找(后面才学)
O(n)
1000 步
一遍求和
O(n log n)
约 10000 步
sort(后面才学)
O(n²)
100 万步
冒泡、选择、插入
O(2ⁿ)
算到宇宙尽头
递归求斐波那契
2.3 三招数循环
循环写法
复杂度
一句话
单层循环
O(n)
循环 n 次
两层嵌套
O(n²)
循环 n×n 次
每次砍一半
O(log n)
n → n/2 → n/4,十几次就到底
for (int i = 0; i < n; i++) // 单层:O(n)
sum += a[i];
for (int i = 0; i < n; i++) // 两层:O(n²)
for (int j = 0; j < n; j++)
cnt++;
while (n > 1) n = n / 2; // 每次砍一半:O(log n)
⚠️ 两层循环不一定正好 n²:
for (i) for (j = i + 1; ...)实际跑 n(n-1)/2 次,但 1/2 是常数,扔掉还是O(n²)。
三、三种排序算法
后面三节都拿同一组数走一遍:5 2 4 1 3。
3.1 冒泡排序:大的往后冒
相邻两个比一比,谁大谁往右挪,一趟下来最大的就被顶到末尾。
int a[5] = {5, 2, 4, 1, 3};
for (int i = 0; i < 4; i++) // 一共排 4 趟
for (int j = 0; j < 4 - i; j++) // 每趟比到没排好的末尾
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]); // 大的往后挪
初始 5 2 4 1 3
一趟 2 4 1 3 5 ← 5 冒到末尾
二趟 2 1 3 4 5 ← 4 到位
三趟 1 2 3 4 5 ← 全排好
四趟 1 2 3 4 5 ← 一趟白干
💡 加一个 flag:某趟一次都没交换,说明已经有序,直接结束。这样已排好的数据只需 n-1 次比较。
3.2 选择排序:每轮挑最小的
从还没排的那一段里挑出最小值,换到这段的最前面。
int a[5] = {5, 2, 4, 1, 3};
for (int i = 0; i < 4; i++) {
int k = i; // 先假设 i 位最小
for (int j = i + 1; j < 5; j++)
if (a[j] < a[k]) k = j; // 记住真正最小的下标
swap(a[i], a[k]); // 换到最前面
}
初始 5 2 4 1 3
一趟 1 2 4 5 3 ← 1 换到第 0 位
二趟 1 2 4 5 3 ← 2 本来就在位
三趟 1 2 3 5 4 ← 3 换到第 2 位
四趟 1 2 3 4 5
3.3 插入排序:像摸扑克牌
手里是已排好的牌,摸到新牌就往里插:比它大的都往右挪一格,空出来的位置放它。
int a[5] = {5, 2, 4, 1, 3};
for (int i = 1; i < 5; i++) {
int t = a[i], j = i - 1; // t 是刚摸到的牌
while (j >= 0 && a[j] > t) { // 比它大的都往右挪
a[j + 1] = a[j];
j–;
}
a[j + 1] = t; // 空出来的位置放下 t
}
初始 5 2 4 1 3
一趟 2 5 4 1 3 ← 2 插到 5 前面
二趟 2 4 5 1 3 ← 4 插到 5 前面
三趟 1 2 4 5 3 ← 1 一路插到最前
四趟 1 2 3 4 5
3.4 三种排序对照
排序
每轮干什么
1000 个随机数的比较次数
稳定吗
冒泡
相邻两两交换
499500
✔ 稳定
选择
找最小值换到前面
499500
❌ 不稳定
插入
往已排好的部分插
258560
✔ 稳定
💡 口诀:冒泡换得多,选择比得多,插入遇上有序就偷懒。
三兄弟的时间复杂度都是 O(n²),更快的排序算法留到后面再学。
四、复杂度是怎么数出来的
4.1 冒泡:把比较次数加起来
第 1 趟比 n-1 次,第 2 趟比 n-2 次,一直到最后一趟比 1 次:
(n-1) + (n-2) + … + 1 = n(n-1)/2 → 扔掉 1/2,记作 O(n²)
n
比较次数
复杂度
5
10
O(n²)
100
4950
O(n²)
1000
499500
O(n²)
4.2 选择:比较一样多,交换少得多
比较次数同样是 n(n-1)/2,但每轮最多换一次,总共最多换 n-1 次。
1000 个随机数实测:比较 499500 次,交换只有 992 次。
⚠️ 交换少不等于快:选择排序一次比较都没省下来,复杂度和冒泡一样是
O(n²)。
4.3 插入:数据越乱越慢
数据情况
1000 个数的比较次数
已经有序
999
随机打乱
258560
完全逆序
499500
已排好的数据只比 n-1 次,所以插入排序最好情况是 O(n),最坏还是 O(n²),一般统一按 O(n²) 记。
4.4 稳定性的含义
两个人分数一样,排序后原来在前面的那个还在前面,这叫稳定。
struct S { int score; char id; };
S v[3] = {{2, ‘a’}, {2, ‘b’}, {1, ‘c’}}; // a 和 b 同分,a 在前
排完序看 a 和 b 的先后:冒泡、插入得到 cab,a 还在前;选择排序得到 cba,a 和 b 被换了个位置。
💡 口诀:要稳定用冒泡、插入;选择排序漂亮地少换了几次,代价就是不保序。
五、估算:看数据范围反推算法
经验值:1 秒大约能做 1 亿次(1e8)简单操作。够不够快,全看这条线。
n 最大到
能用的复杂度
说明
1000
O(n²) 轻松
100 万次操作,冒泡毫无压力
10000
O(n²) 勉强
1 亿次,正好卡在线上
100000
必须 O(n log n)
冒泡要 50 亿次,根本跑不完
1000000
O(n) 或 O(n log n)
冒泡彻底没戏
数据规模在 1000 以内时,三种基础排序随便用;一旦看到 n = 100000,其实是在提示:O(n²) 根本跑不完,该换个思路了。
六、六个常见陷阱
6.1 冒泡内层边界
for (int j = 0; j < 4 - i; j++) // ✔ 第 i 趟比到 4-i,越界前收手
for (int j = 0; j < 5; j++) // ❌ 写死 5,a[j+1] 读到数组外面
6.2 选择排序只赋值不交换
swap(a[i], a[k]); // ✔ 两个位置互换
a[i] = a[k]; // ❌ 只覆盖,a[i] 原来的值丢了
6.3 插入排序 while 的条件顺序
while (j >= 0 && a[j] > t) // ✔ 先挡住越界,短路救了你
while (a[j] > t && j >= 0) // ❌ j 先变成 -1 就先去读 a[-1],越界
6.4 结构体排序要整体换
swap(s[i], s[j]); // ✔ 姓名和分数一起搬
swap(s[i].score, s[j].score); // ❌ 分数换了,姓名没换,全串位
6.5 稳定性不能靠猜
选择排序用 swap 实现时不稳定——同分的两个元素,可能因为一次"最小值和第 i 位交换"被打乱先后。
6.6 输出的空格
for (int i = 0; i < n; i++) {
if (i > 0) cout << ’ '; // ✔ 空格放在前面,末尾不留
cout << a[i];
}
七、全部排序算法性能总表
前面只讲了三兄弟。工程和题库里还会碰到一串名字,这张表把它们一次列全,后面几行现在看不懂没关系,先认识它们的"牌面"。
算法
最好
平均
最坏
额外空间
稳定
一句话
冒泡
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(n log n)
O(n^1.3)
O(n²)
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²)
O(log n)
❌
平均最快,遇有序数据会退化
堆
O(n log n)
O(n log n)
O(n log n)
O(1)
❌
不管数据长啥样都是 n log n
计数
O(n+k)
O(n+k)
O(n+k)
O(n+k)
✔
值域 k 很小时秒杀一切
基数
O(d(n+k))
O(d(n+k))
O(d(n+k))
O(n+k)
✔
按个位、十位分批清点
桶
O(n)
O(n+k)
O(n²)
O(n+k)
✔
数据均匀分布时接近线性
读表三件事:
-
冒泡和插入的最好
O(n)是靠优化换来的:冒泡要加"本趟没换就结束"的 flag,插入本来就会在中途停下; -
快排的平均最快,但最坏会退化成
O(n²),堆排序则永远稳在O(n log n); -
计数、基数、桶不算"比较排序",它们靠清点而不是两两比较,才绕过了
O(n log n)这条线,代价是必须知道数据值域。
1000 个随机数实测,比较次数分别是:归并约 8700、快排约 14000、堆约 16800。但同样 1000 个数如果本来就排好了,拿第一个数当轴的快排会飙到 499500 次——正好是 n(n-1)/2;堆排序三种情况都在 1.6 万到 1.8 万之间,几乎不看数据顺序。
💡 选型口诀:数据少或基本有序用插入,要稳定又不缺内存用归并,内存紧还要保性能用堆,平均最快用快排,值域小就直接计数。
⚠️ 表里没有哪一行能同时做到
O(n log n)、稳定、O(1)空间——这三样想要全占,就得付时间或内存的代价。
八、自测七题
先自己算,再对答案。
题号
题目
答案
1
对 5 2 4 1 3 做冒泡排序,第一趟结束后数组是?
2 4 1 3 5
2
100 个数做冒泡排序,最坏比较多少次?
4950
3
已经排好序的 1000 个数做插入排序,比较多少次?
999
4
1000 个数做选择排序,最多交换几次?
999
5
O(n²)、O(n log n)、O(n)、O(log n) 谁最快?
O(log n)
6
选择排序稳定吗?
不稳定
7
1000 个数,要求排完保持稳定,内存又够用,优先选哪个?
归并排序
💡 第 2 题算
100 × 99 ÷ 2,第 4 题记"每轮最多换一次,一共 n-1 轮"。
总结
💡 全文一句话:三种基础排序都是
O(n²);想更快就往最后那张表的O(n log n)一档找——而复杂度只看 n 翻倍时步数涨几倍。
-
冒泡:相邻交换,稳定,比较次数是 n(n-1)/2
-
选择:每轮找最小,比较最多、交换最少,不稳定
-
插入:像摸牌,遇上有序数据只比 n-1 次
-
复杂度看最高项,常数和系数全扔掉
-
十种排序一张表:值域小用计数,要稳定用归并,平均最快用快排
-
1 秒 1e8 次:n ≤ 1000 随便用,n ≥ 100000 就别上
O(n²)
⚠️ 最后一记警钟:排序写错,很少错在思路,多半错在边界——
4 - i写成5、j >= 0写到后面去、结构体只换了分数忘了姓名。写完先用5 2 4 1 3手推一遍,比对着代码空想快得多。