排序与时间复杂度

一句话定义:排序是把一堆数按大小重新排队,时间复杂度是给这个排队过程称重的那杆秤。 抓住"比较次数随 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 翻倍时,运算量涨几倍。

三条规矩:

  1. 常数扔掉:3n + 5 记作 O(n)

  2. 只留最高项:n² + n + 100 记作 O(n²)

  3. 默认说最坏:"冒泡排序是 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)

✔

数据均匀分布时接近线性

读表三件事:

  1. 冒泡和插入的最好 O(n) 是靠优化换来的:冒泡要加"本趟没换就结束"的 flag,插入本来就会在中途停下;

  2. 快排的平均最快,但最坏会退化成 O(n²),堆排序则永远稳在 O(n log n);

  3. 计数、基数、桶不算"比较排序",它们靠清点而不是两两比较,才绕过了 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 手推一遍,比对着代码空想快得多。


本站由 奇迹欧埃 使用 Stellar 创建。