插入排序

依次将每个待排序的记录插入到一个有序子文件的合适位置。

是稳定排序。

冒泡排序

只交换相邻的两个记录，不断“冒”出当前最小的记录。

是稳定排序。

优化的冒泡排序

检查每次冒泡过程中是否发生交换，如果没有，则表明整个数组已经排好序了，排序结束。

选择排序

每一趟在后面 $n - i$ 个待排记录中选取最小记录和第 $i$ 个记录互换。

不稳定排序！

希尔排序（Shell 排序）

直接插入排序的两个性质：

• 在待排序序列较短情形下效率高。
• 在整体有序的情形下时间代价低。

实现方法

注意：

• 分组：彼此相距为 $d_i$ 的记录才化为一组。