意义与机制
排序是按照给定顺序重新排列数据的过程。冒泡排序比较相邻数据，归并排序则将拆分后的列表合并。
算法的循环结构决定输入规模增大时工作量如何增长。即使数据规模相同，初始顺序与实现中的停止条件也可能影响结果。
关系与条件
对于典型的冒泡排序，比较规模为 O(n²)，而归并排序的规模为 O(n log n)。需要注意的是，具体的比较次数和渐近表示法 O 并不相同。
该实验并非一个基于统计价值比较、交换和写入次数来衡量计算机实际时间的基准。它不会将数据写入和位置交换视为相同的操作。
观察实验中需要注意的事物
比较的计数取决于大小、初始顺序以及算法。
我们计算值比较和交换，而不是经过的时间。合并写入是独立的。
关键关系与符号
bubble: n(n−1)/2 · merge: O(n log₂n)
| 符号 | 含义 | 单位 |
|---|---|---|
| n | 输入数据项的数量 | 个 |
| O(n log n) | 根据输入规模的，渐近增长的上界表达式。 | 复杂度 |
工作实例
合并写操作和交换操作是否是相同的操作？
不同的运算·比较取决于大小、初始顺序以及算法。
常见误解
- 比较次数较少，并不意味着在所有计算机和输入下，实际运行时间都会按同样的比例缩短。