一叠乱序观测记录，怎样排得又对又省事？
先比较哪张更早，再移动整张记录，亲眼看数据怎样排好。
拍完一组照片，记录卡被打乱了。每张卡都有一个数字和一个身份字母，你想按数字从小到大整理，还不能把数字相同的两张卡弄丢。
打开互动课程 →
先猜一下
两条观测记录的排序值都是 2，排序时应该删掉其中一条吗？
查看答案与解释
不应该，两条记录都保留 — 数值相同不等于记录相同；排序只改顺序，不负责去重。
再把体验和科学连起来
先把记录摊开
每张卡的字母是记录身份，数字是排序依据。同一个数字可以出现多次，不能因此丢掉记录。
输入是一组记录，不是只剩互不相同的数
每次只做一个明确动作
移动进度，橙色标出比较或交换的卡。程序在比较阶段只看值，在交换阶段移动完整记录。
比较 → 决定是否交换
换一种做法，结果还要一样
原书给出逐对交换、先找最小、分区快排。不同步骤可以得到相同的升序值，但相同值的记录未必保持原顺序。
SIMPLE / BETTER / QUICKSORT
数据变多，步骤数就重要
前两种方法的比较次数随N²增长；快排通常约N log N，但不保证每种输入都最快。计数是本例实测，不是机器运行秒数。
比较次数、交换次数与实际耗时要区分
把计算链展开
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条记录的身份与内容保持完整
这是算法规则课，没有一个代入即得的天文公式。比较决定顺序，交换必须移动整条记录；相同键值不表示可丢弃记录。
试一试
用同一组卡片比较三种方法；把进度拖到100%，核对数字升序且A—H记录仍全在。
动手看一遍 →
符号不用背
- N
- 记录数量，本课画面为8条
- 比较
- 查看两个值的次序；快排也会与基准值比较
- 交换
- 把两张完整记录互换位置
- 基准值
- 快排用来划分两边的数值
- 稳定性
- 相同排序值的记录是否保持原先相对次序
算法、精度与适用范围
原书第6章印刷页55–58、表6.A。实现三种算法：SIMPLE SORT按前后位置逐对比较并交换，BETTER先找剩余最小值再交换，QUICKSORT采用中间元素值为基准的双指针分区和显式栈。本课省略原BASIC按区间长短优化栈顺序的细节，保留分区结果及实际比较/交换轨迹；不声称快排最坏情况为N log N。演示卡片数字无真实日期单位，字母仅标记身份。进度百分比映射到该算法的离散步骤，并显示真实步骤编号。比较和交换分别计数，不测运行秒数；同值记录顺序不保证稳定。章节末尾字符串ASCII排序介绍在文字中说明，交互只实现数值排序。本地AA+未找到排序专用模块，结果用独立原生数值排序与每步排列不变量核验。
我的理解检查
比较两张记录时，数据一定立刻交换吗？
不一定 — 比较和交换是不同动作，只有算法条件满足时才交换。
排序后的数字一样，就代表同值记录的顺序也一定一样吗？
不一定 — 是否保留同值记录的先后关系涉及稳定性；本课三种实现不提供稳定排序保证。
原书旧电脑上测得的秒数，可以直接当成今天网页的耗时吗？
不可以 — 硬件、语言和实现不同；本课比较可复现的操作次数，不复用旧机器秒数。
排序先保证记录完整、次序正确，再比较操作成本；数值相同的记录不能被当作重复垃圾丢掉。
Jean Meeus · Astronomical Algorithms, 2nd ed. · 第 6 章