插入排序

• 基本思想：将带排序表看作左右两个部分，左边为有序区，右边为无序区，排序的过程即将右边无序区中的元素逐个插入到左边的有序区，构成一个新的有序区

直接插入排序

算法步骤

1. 设待排序的记录存储在数组r[1……n]中，将第一个记录r[1]视作左边的有序序列，r[2……n]视作右边的无序序列
2. 依次将右边的无序序列中的第一个元素插入到有序序列中

复杂度

1. 时间复杂度：
   1. 最好情况：本身有序->\(O(n)\)
   2. 最坏情况：本身逆序->\(O(n^2)\)
2. 空间复杂度：\(O(1)\)
3. 稳定性：稳定排序

最后一趟排序时，可能出现所有的元素都不在其最终位置上的情况

希尔排序

• 基本思想：将待排序列分为若干组，在每组内进行直接插入排序，使得整个序列基本有序，然后再对整个序列进行直接插入排序
• 分组的方式：间隔方法分组
  • 设置步长\(d\)，下标相差\(d\)的为一组
  • 取值：\(d_1 = n / 2, d_2 = d_1 / 2……\)

算法步骤

1. 记录待排序列r[1……n]，增量序列d[1……n]
2. 依次按照所取得增量对每一组进行直接插入排序

复杂度

1. 时间复杂度：
   1. 最好情况：\(O(n\log{n})\)
   2. 最坏情况：\(O(n^2)\)
2. 空间复杂度：\(O(1)\)
3. 稳定性：不稳定排序（分组中排序可能导致该不稳定性）