一、排序就是按某个规则站队

一批数 5 3 8 4 2 7 1 6，按从小到大排是 1 2 3 4 5 6 7 8，按从大到小是 8 7 6 5 4 3 2 1。 数据一个没变，只是顺序变了。所以排序改变的是「位置」，不是「内容」。 这句话决定了后面所有算法的形状：它们做的都是「比较两个数、必要时换个位置」，从不新建或删掉数据。

既然只是换位置，那「换成什么顺序」就成了第一个要回答的问题——而这个答案不在算法里，在你脑子里。

二、第一件事是说清按什么排

演示里给了三种常见规则：

前两种是「一条规矩」，第三种是「几条规矩排队」。 字典序那行值得看一眼：pear、apple、fig 排成 apple fig pear，是因为按字母逐个比，a 最小、 f 其次、p 最大。跟长度无关。 这也是排序能用在字符串上的原因：只要能定出「谁在前」，就能排。数字能定，字母能定，日期能定， 所以它们都能排。

三、多条件排序才是真实业务里最常见的

「按销售额排名」这句话在真实业务里几乎总要加一句：「同额按回款时间排」。 不加这一句，就会出现两个人算出来不一样的排名——不是谁算错了， 是规则没定全，剩下的顺序由算法自己决定。 这和第 4.3 讲的「并列名次还是密集排名」是同一类问题：口径没定，就没有对错。

工程上的做法是把规则写全并写死：第一关键字、第二关键字、第三关键字， 一直写到「能分出唯一顺序」为止。 实在分不出来（所有字段都一样），就再加一个「按原始录入顺序」——这条兜底能保证结果每次一样。

四、评一个排序算法，看三个数

演示里那张表是全章的评价标准：

这三个数的关系是：比较便宜，挪动贵，内存最贵。所以「交换少」的算法在记录很大时更受欢迎。 为什么挪动更贵？因为比较只要读两个数，挪动要写回内存；一条记录几百 KB 的时候，这个差别非常明显。 第 5.2 会看到选择排序的交换次数特别少——它的价值就在这里，尽管比较次数跟别人一样多。

五、还有一个指标不写在表里：稳定性

稳定性问的是：两个相等的数，排完还保持原来的先后吗？ 举例：两个人都是 92 分，原来张三在前李四在后。排完之后还是这个顺序，就叫稳定。 为什么重要？批量报表按分数排名，同分的人顺序变了，看表的人会觉得数据错了。

这一点很微妙：结果在数学上完全正确，但在人眼里是错的。算法不光要对，还要可预期。 后面 5.5 的总表里有一列「稳定」，那一列会决定同一份数据该选哪个算法。

六、小数据上看步数，不看毫秒

这一章所有算法都用同一批数据：[5, 3, 8, 4, 2, 7, 1, 6]。八个数字，跑起来都在微秒级。 八个数上测毫秒毫无意义——机器抖一下就盖过算法之间的差别了。 所以教材的写法是数步数：比较了几次、交换了几次。步数只跟算法和数据有关，跟机器无关。

这也回应了第 4.1 那句「循环次数就是代价」：排序算法的全部差别，就是它们各自要跑多少次内层循环。

七、动手 Demo：同一批数，两种规则，顺便数清比较和交换

先拿八个数按从小到大、从大到小各排一遍，看数据本身有没有变。 再手写一个最笨的选择排序，把每一轮的结果打出来。 最后数一下它比较了几次、交换了几次。

a = [5, 3, 8, 4, 2, 7, 1, 6]
print(sorted(a))
print(sorted(a, reverse=True))
print('原数组没动', a)

cmp_cnt = 0
swap_cnt = 0
b = a[:]
for i in range(len(b) - 1):
    m = i
    for j in range(i + 1, len(b)):
        cmp_cnt += 1
        if b[j] < b[m]:
            m = j
    if m != i:
        b[i], b[m] = b[m], b[i]
        swap_cnt += 1
print(b, '比较', cmp_cnt, '交换', swap_cnt)

print(sorted(['pear', 'apple', 'fig']))

实跑输出：

--------------------------------------------------------------------
排序是什么：先定规则，再谈算法
--------------------------------------------------------------------


  ① 排序就是按某个规则站队
  --------------------------------------------------------------------
  原始顺序：[5, 3, 8, 4, 2, 7, 1, 6]
  按从小到大：[1, 2, 3, 4, 5, 6, 7, 8]
  按从大到小：[8, 7, 6, 5, 4, 3, 2, 1]
  同一批数据，换一个规则就是另一种结果。
  所以排序的第一件事不是写算法，是说清按什么排——按分数、按姓氏、按时间，
  还是按「分数相同再按姓氏」。

  ② 三种常见的排序规则
  --------------------------------------------------------------------

| 规则 | 例子 | 结果 |
|---|---|---|
| 数值大小 | 5 3 8 4 | 3 4 5 8 |
| 字符串字典序 | pear apple fig | apple fig pear |
| 多个条件 | 先按分数降序，同分按姓名升序 | 要写比较函数 |

  第三种才是真实业务里最常见的。
  「按销售额排名」几乎总要加一句「同额按回款时间排」，不写清就会出现两个人算出来不一样的排名。

  ③ 评一个排序算法，看三个数
  --------------------------------------------------------------------

| 指标 | 什么意思 | 为什么要看 |
|---|---|---|
| 比较次数 | 两个数比了几次大小 | 比较是最基本的操作 |
| 交换次数 | 数据挪了几次位置 | 挪数据比比较更贵 |
| 额外内存 | 除了原数组还要多少空间 | 数据大到装不下时这最要命 |

  还有一个不出现在表里的指标：稳定性——两个相等的数，排完还保持原来的先后吗。
  批量报表按分数排名，同分的人顺序变了，看表的人会觉得数据错了。

  ④ 8 个数，排一下要多久
  --------------------------------------------------------------------
  这一章所有算法都用同一批数据：[5, 3, 8, 4, 2, 7, 1, 6]
    数据量小，快慢看不出差别；所以这一章不比时间，比「比较次数」和「交换次数」。
  这也是教材的写法：小数据上看「做了多少步」，比看「跑了几毫秒」更能说明问题。
  毫秒会被机器、语言、编译器搅乱，步数不会。

①sorted(a) 返回新数组，a 一点没变。这正好演示了「排序只换位置、不动内容」。 ②选择排序的内层循环是 for j in range(i + 1, ...)，从 i+1 开始， 因为自己不用跟自己比——又是那个 n-1。 ③数出来 28 次比较、6 次交换。28 = 7+6+5+4+3+2+1，下一节会推这个公式。 ④最后一行是字符串排序：apple fig pear。按字母逐个比，跟长度无关。

30 秒实验

1. 把比较改成 b[j] > b[m]，看结果变成升序还是降序。
2. 给数据加两个重复的数（比如两个 4），看它们排完的先后有没有变。
3. 想一个你工作里的「多条件排序」，把第一、第二、第三关键字写下来。

常见误区

1. 「排序就是把数据重排一遍。」只换位置，不增不删。所以排序算法都在做交换。
2. 「按分数排名就完了。」同分怎么排没说清，两个人就会算出两个结果。
3. 「跑得快就是好算法。」还要看交换次数、额外内存、稳不稳定。

规则和指标都有了，从下一节开始看具体算法。第一个最不像排序，但它最快——因为它根本不比较。

• ☐ （本篇完，下一篇 5.2 桶排序与选择排序）

相关笔记

• 桶排序与选择排序
• 最高分、最低分与排名
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引