关于此实验
观察冒泡排序、插入排序和归并排序如何将相同输入转换为升序。你可以在比较时暂停，逐步查看每次写入，也可以沿着完整轨迹向后移动。分别统计值比较次数和主数组写入次数，有助于区分算法的工作量与动画播放时长。
学习目标
- 追踪三种比较排序算法中的比较和写入
- 比较算法在乱序、已排序和逆序输入上的性能
- 区分最坏情况下的二次增长与 n log n 增长
使用方法
- 1固定乱序输入和数组长度。运行完冒泡排序，并记录比较次数和写入次数。
- 2使用相同输入重新运行插入排序，然后运行归并排序。比较最终计数。
- 3尝试已排序的输入，观察冒泡排序的提前退出以及插入排序较少的比较次数。
- 4使用“Previous”和轨迹滑块查看合并过程。临时缓冲区可以保存那些在原主数组位置上已不可见的值。
模型
假设
- 输入包含从 1 到 n 的不重复整数。打乱数据时使用固定种子，因此每种算法接收的数据都相同。
- 比较是对数据值进行测试，而不是测试索引或循环边界。写入是指向主数组赋值，包括未发生变化的插入键。
- 归并排序复制到临时缓冲区的操作不计入写入次数。额外内存使用量也不计入显示的操作总数。
- 播放速度是为教学目的设置的，并非实际运行时间性能基准。
在课堂上试试这个实验
- Q1在此实现中，对于已经排好序的输入，为什么冒泡排序只需进行 n − 1 次比较？
- Q2数组长度相同时，对于逆序输入，哪种算法的比较次数更少？
- Q3为什么动画帧数不能可靠地衡量算法速度？
常见问题
为什么在插入排序或归并排序过程中，值会短暂地重复显示？
覆盖主数组时，某个值可能暂存在临时键或归并缓冲区中。可视化会在每次写入时显示主数组的内容；操作完成后，重复现象就会消失。
归并排序总是写入次数更少吗？
不是。归并排序的比较次数增长较为高效，但会反复将归并结果写回。操作次数取决于输入数据，以及具体统计哪些赋值操作。