# 四种排序算法的设计、实现与性能比较

## 1. 实验目的

实现冒泡排序、插入排序、归并排序和快速排序，通过相同的随机数据测试四种算法的实际运行时间，并结合时间复杂度分析，验证 $O(n^2)$ 与 $O(n\log n)$ 算法在数据规模增大时的效率差异。

完整程序见 [sorting_benchmark.py](sorting_benchmark.py)，原始实验记录见 [raw_timings.csv](results/raw_timings.csv)，汇总数据见 [summary.csv](results/summary.csv)。

## 2. 算法设计

### 2.1 冒泡排序

从序列左端开始比较相邻元素，如果前一个元素较大就交换。每轮结束后，当前未排序部分的最大元素被移动到末尾。程序记录每轮最后一次交换的位置，用它缩小下一轮的扫描范围；若没有发生交换，则说明序列已经有序，可以提前结束。

### 2.2 插入排序

将序列分成左侧有序区和右侧未排序区。依次取出未排序区的第一个元素，将有序区内比它大的元素向右移动，再把该元素插入空出的位置。比较条件使用“大于”而非“大于等于”，因此相等元素的原有顺序不会改变。

### 2.3 归并排序

递归地把区间分成左右两半，分别排好序后，再把两个有序区间合并。实现中只申请一个长度为 $n$ 的辅助数组并在全部递归过程中复用，避免反复创建切片。合并时，相等元素优先取左侧元素，因此算法稳定。

### 2.4 快速排序

使用首、中、尾三个元素的中位数作为枢轴，并进行三路分区：小于枢轴、等于枢轴和大于枢轴。三路分区能较好地处理重复元素。程序只递归处理较短分区，用循环继续处理较长分区，把递归栈深度控制在 $O(\log n)$；这种优化不改变快速排序最坏情况下 $O(n^2)$ 的时间复杂度。

## 3. 理论复杂度

| 算法 | 最好时间 | 平均时间 | 最坏时间 | 辅助空间 | 稳定性 |
|---|---:|---:|---:|---:|---|
| 冒泡排序（带提前结束） | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 插入排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 归并排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$，另有递归栈 | 稳定 |
| 快速排序 | $\Theta(n)$¹ | $O(n\log n)$ | $O(n^2)$ | 本实现递归栈为 $O(\log n)$ | 不稳定 |

¹ 该最好情况来自本实现的三路分区：所有元素都相等时，一次线性扫描即可完成。对于通常的互异元素，最均衡的划分需要 $\Theta(n\log n)$ 时间。

快速排序只有在分区较均衡时才表现为 $O(n\log n)$。如果每次得到的两个分区规模长期接近 $0$ 和 $n-1$，其运行时间仍会退化为 $O(n^2)$。三数取中只能降低退化概率，不能消除理论最坏情况。

## 4. 实验方法

- 运行环境：Windows 11、Python 3.11.4、Intel Core i9-14900HX（24 核、32 逻辑处理器）、31.6 GB 内存。计时程序为单进程运行。
- 固定随机种子为 `20260919`，随机整数范围为 $[-10^9,10^9]$。
- 四种算法的共同测试规模为 512、1024、2048、4096 和 8192。
- 为继续观察 $O(n\log n)$ 算法在大规模数据上的变化，归并排序和快速排序额外测试 16384、32768、65536 和 131072。
- 每个“数据规模—算法”组合重复运行 5 次，以中位数作为最终结果。
- 同一轮的四种算法使用完全相同的原始序列。随机数据生成、列表复制、标准答案生成、正确性校验、打印和文件写入均不计入排序时间。
- 使用 `time.perf_counter_ns()` 计时，并循环改变算法的执行顺序，减小固定先后顺序造成的偏差。
- 正式计时前先进行预热；计时结束后，将每次排序结果与 Python 标准排序结果比较。
- 另外使用空序列、单元素、有序序列、逆序序列、全相等序列、重复值、负数和随机小样本进行了正确性测试，四种算法全部通过。

## 5. 实验结果

下表为 5 次运行的中位时间，单位为毫秒。“—”表示为了避免 $O(n^2)$ 算法耗时过长，没有继续测试该规模。

| 数据规模 $n$ | 冒泡排序 | 插入排序 | 归并排序 | 快速排序 |
|---:|---:|---:|---:|---:|
| 512 | 6.822 | 2.634 | 0.519 | 0.397 |
| 1024 | 29.309 | 12.159 | 1.201 | 0.879 |
| 2048 | 124.312 | 49.113 | 2.540 | 2.049 |
| 4096 | 516.917 | 198.473 | 5.492 | 4.410 |
| 8192 | 2080.730 | 817.677 | 11.495 | 9.045 |
| 16384 | — | — | 25.212 | 20.270 |
| 32768 | — | — | 53.308 | 41.165 |
| 65536 | — | — | 134.940 | 93.535 |
| 131072 | — | — | 262.884 | 205.911 |

![排序算法运行时间及增长倍数](results/sorting_benchmark.png)

### 5.1 数据规模翻倍时的耗时倍数

当运行时间的主导项近似为 $cn^2$ 时，$n$ 变为 $2n$ 后的理论增长倍数约为：

$$
\frac{(2n)^2}{n^2}=4
$$

对于主导项近似为 $cn\log n$ 的算法，相应增长倍数约为：

$$
\frac{2n\log_2(2n)}{n\log_2n}
=2\left(1+\frac{1}{\log_2n}\right)
$$

其增长倍数略大于 2，并随着 $n$ 增大逐渐接近 2。共同规模上的实测结果如下：

| 当前规模 $n$ | 冒泡排序 | 插入排序 | 归并排序 | 快速排序 |
|---:|---:|---:|---:|---:|
| 1024 | 4.296 | 4.617 | 2.314 | 2.212 |
| 2048 | 4.242 | 4.039 | 2.115 | 2.331 |
| 4096 | 4.158 | 4.041 | 2.163 | 2.152 |
| 8192 | 4.025 | 4.120 | 2.093 | 2.051 |

冒泡排序和插入排序的增长倍数总体接近 4；归并排序和快速排序总体在 2.0～2.3 左右，与理论趋势一致。扩展规模中，归并排序的翻倍增长倍数为 1.948～2.531，快速排序为 2.031～2.272。个别点偏离理论值，可能受解释器开销、内存分配、缓存和操作系统调度影响。

### 5.2 复杂度归一化验证

若算法符合给定的渐进复杂度，用运行时间除以对应的增长函数后，所得数值应在规模增大时大致稳定。本次实验得到：

- 冒泡排序的 $T(n)/n^2$ 从 26.03 ns 变化到 31.01 ns；
- 插入排序的 $T(n)/n^2$ 从 10.05 ns 变化到 12.18 ns；
- 归并排序在共同规模上的 $T(n)/(n\log_2n)$ 从 112.63 ns 变化到 107.93 ns；
- 快速排序在共同规模上的 $T(n)/(n\log_2n)$ 从 86.22 ns 变化到 84.94 ns。

四组归一化结果均处在相对稳定的范围内，进一步支持了理论复杂度分析。有限规模实验可以验证数据是否符合预测趋势，但不能单独构成对渐进复杂度的数学证明；复杂度结论仍以算法结构分析为依据。

## 6. 结果分析

当规模从 512 增大到 8192，即数据量扩大 16 倍时：

- 冒泡排序由 6.822 ms 增长到 2080.730 ms，增长约 305 倍；
- 插入排序由 2.634 ms 增长到 817.677 ms，增长约 311 倍；
- 归并排序由 0.519 ms 增长到 11.495 ms，增长约 22.1 倍；
- 快速排序由 0.397 ms 增长到 9.045 ms，增长约 22.8 倍。

$O(n^2)$ 的理论增长量级为 $16^2=256$ 倍；$O(n\log n)$ 的理论增长量级为

$$
\frac{8192\times13}{512\times9}\approx23.1
$$

实测结果受常数开销和运行环境影响，不会与理论值完全相同，但两类算法的增长趋势有明显区别。

在 $n=8192$ 时，快速排序只用 9.045 ms，冒泡排序需要 2080.730 ms，后者约为前者的 230 倍；插入排序也约为快速排序的 90 倍。归并排序和快速排序还能在约 0.26 秒和 0.21 秒内处理 131072 个元素，而二次复杂度算法若继续扩大到这一规模，预计耗时会急剧增加。

实验也反映出渐进复杂度只描述规模增长趋势，并不决定所有小规模输入上的绝对速度。常数项、输入有序程度、枢轴选择、内存访问和语言实现都会影响实际时间。例如插入排序的常数开销较小，而且在近乎有序的数据上可能表现很好；归并排序始终需要额外辅助数组；快速排序平均很快，但仍存在 $O(n^2)$ 的理论最坏情况。

## 7. 实验结论

理论分析和实测数据共同验证了以下结论：

1. 随机输入规模翻倍时，冒泡排序和插入排序的运行时间总体接近 4 倍，符合 $O(n^2)$ 的增长规律。
2. 归并排序和快速排序的运行时间通常只增加到约 2 倍多，符合 $O(n\log n)$ 的增长规律。
3. 数据规模较小时，不同算法之间的绝对时间差可能不明显；随着规模增大，$O(n\log n)$ 算法会迅速拉开差距。
4. 归并排序具有稳定且确定的 $O(n\log n)$ 时间，但需要 $O(n)$ 辅助空间；快速排序通常速度较快且主要原地工作，但最坏时间仍为 $O(n^2)$。

## 8. 运行方法

在当前目录执行：

```powershell
python .\sorting_benchmark.py --self-test-only
python .\sorting_benchmark.py
```

第二条命令会重新生成：

- `results/raw_timings.csv`：每一次运行的原始纳秒和毫秒数据；
- `results/summary.csv`：中位数、最小值、最大值、增长倍数和归一化值；
- `results/sorting_benchmark.png`：运行时间与翻倍增长率图。

算法、CSV 输出和自检只使用 Python 标准库。图表需要 `matplotlib`；如果没有安装，程序仍会完成计时并输出 CSV，只跳过图片生成。不同计算机和不同系统负载下的绝对时间会改变，增长趋势应基本一致。