插入排序

插入排序的基本思想：每一趟将一个待排序记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有排序记录全部插入为止。

例如，打扑克牌在抓牌时要保证抓过的牌有序排列，则每抓一张牌，就插入到合适的位置，直到抓完牌为止，即可得到一个有序序列。

可以选择不同的方法在已排好序的记录中寻找插入位置。根据查找方法的不同，有多种插入排序方法，这里只介绍以下 3 种：直接插入排序、折半插入排序和希尔排序。

直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录增 1 的有序表。

算法步骤：

1. 设待排序的记录存放在数组 $r[0..n-1]$，$r[0]$ 是一个有序序列；
2. 循环 $n-1$ 次，每次使用顺序查找法，查找 $r[i](i=1,\dots ,n-1)$ 在已排好序的序列 $r[0..i-1]$ 中的插入位置，然后将 $r[i]$ 插入表长为 $i$ 的有序序列 $r[0\dots i-1]$，直到将 $r[n-1]$ 插入表长为 $n-1$ 的有序序列 $r[0\dots n-2]$，最后得到一个表长为 $n$ 的有序序列。

在具体实现 $r[i]$ 向前面的有序序列插入时，有两种方法：

1. 将 $r[i]$ 与 $r[0],r[1],\dots ,r[i-1]$ 从前向后顺序比较；
2. 将 $r[i]$ 与 $r[i-1],r[i-2],\dots ,r[0]$ 从后向前顺序比较。

一般采用第 2 种方法。在自 $i-1$ 起往前查找插入位置的过程中，可以同时后移记录。

算法如下：

import { Item } from '../item.ts'

export function straightInsertionSort(unorderedList: Item[]) {
  for (let i = 1, { length } = unorderedList; i < length; i++) {
    const temp = unorderedList[i]
    let j = i - 1
    while (j >= 0 && temp.key < unorderedList[j].key) {
      unorderedList[j + 1] = unorderedList[j]
      j--
    }
    unorderedList[j + 1] = temp
  }
}

时间复杂度

排序的基本操作：比较两个关键字的大小和移动记录。

对于其中某一趟插入排序，算法内层的 while 循环次数取决于待插入记录的关键字与前 $i-1$ 个记录的关键字之间的关系。其中，在最好情况（正序：待排序序列中记录按关键字非递减有序排列）下，比较 1 次，无需移动记录位置；在最坏情况（逆序：待排序序列中记录按关键字非递增）下，比较 $i-1$ 次（依次与前面的 $i-1$ 个记录进行比较），移动 $i$ 次（前面的 $i-1$ 个记录依次向后移动，找到插入位置后，把待插入记录移到该位置）。

对于整个排序过程需执行 $n-1$ 次，最好情况下，总的比较次数达最小值 $n-1$，记录无需移动；最坏情况下，总的关键字比较次数 $KCN$ 和记录移动次数 $RMN$ 均达到最大值，分别为

$$\begin{array}{r}KCN=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}\approx \frac{n^2}{2}\\ RMN=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}\approx \frac{n^2}{2}\end{array}$$

若待排序序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下，直接插入排序关键字的比较次数和记录移动次数均约为 $\frac{n^2}{4}$。

因此，直接插入排序的时间复杂度为 $O(n^2)$。

空间复杂度

直接插入排序只需要一个记录的辅助空间，所以空间复杂度为 $O(1)$。

特点

• 稳定；
• 简单容易实现；
• 既适用于顺序存储，也适用于链式存储，在单链表上无需移动记录，只需修改对应指针即可；
• 更适合于初始记录基本有序（正序）的情况，当初始记录无序，$n$ 比较大时，时间复杂度较高，不宜采用。

折半插入排序

折半插入排序（Binary Insertion Sort）使用折半查找实现查找插入位置的操作。

算法步骤：

1. 设待排序的记录存放在数组 $r[0..n-1]$，$r[0]$ 是一个有序序列；
2. 循环 $n-1$ 次，每次使用折半查找法，查找 $r[i](i=1,\dots ,n-1)$ 在已排好序的序列 $r[0..i-1]$ 中的插入位置，然后将 $r[i]$ 插入表长为 $i$ 的有序序列 $r[0\dots i-1]$，直到将 $r[n-1]$ 插入表长为 $n-1$ 的有序序列 $r[0\dots n-2]$，最后得到一个表长为 $n$ 的有序序列。

算法如下：

import { Item } from '../item.ts'

export function binaryInsertionSort(unorderedList: Item[]) {
  for (let i = 1, { length } = unorderedList; i < length; i++) {
    const temp = unorderedList[i]
    let left = 0
    let right = i - 1
    while (left <= right) {
      const mid = Math.floor((left + right) / 2)
      if (temp.key < unorderedList[mid].key) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    for (let j = i - 1; j >= left; j--) {
      unorderedList[j + 1] = unorderedList[j]
    }
    unorderedList[left] = temp
  }
}

时间复杂度

从时间上比较，折半查找比顺序查找快，所以就平均性能而言，折半插入排序优于直接插入排序。

折半插入排序所需要的关键字比较次数与待排序序列的初始排列无关，仅依赖于记录的个数。无论初始序列情况如何，在插入第 $i$ 个记录时，需要经过 $\lfloor {\log }_{2}i\rfloor +1$ 次比较，才能确定它应插入的位置。所以当记录的初始排列为正序或接近正序时，直接插入排序比折半插入排序执行的关键字比较次数要少。

折半插入排序的记录移动次数与直接插入排序相同，依赖于记录的初始排列。

在平均情况下，折半插入排序仅减少了关键字比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度为 $O(n^2)$。

空间复杂度

折半插入排序所需辅助空间与直接插入排序相同，空间复杂度为 $O(1)$。

特点

• 稳定；
• 只能使用顺序存储结构；
• 适合初始记录无序、$n$ 比较大的情况。

希尔排序

希尔排序（Shell's Sort）又称缩小增量排序（Diminishing Increment Sort），因 D.L.Shell 于 1959 年提出而得名。

直接插入排序，当待排序记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从减少记录个数和序列基本有序两个方面对直接插入排序进行了改进。

算法步骤：

希尔排序实质上是采用分组插入的方法。先将整个待排序记录序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。这样当经过几次分组排序后，整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

希尔对记录的分组，不是简单地逐段分割，而是将相隔某个增量的记录分成一组。

1. 第一趟取增量 $d_1(d_1<n)$ 把全部记录分成 $d_1$ 个组，所有间隔为 $d_1$ 的记录分在同一组，在各个组中进行直接插入排序；
2. 第二趟取增量 $d_2(d_2<d_1)$，重复以上步骤；
3. 依次类推，直到所取的增量 $d_t=1(d_t<d_{t-1}<\dots <d_2<d_1)$，所有记录在同一组中进行直接插入排序为止。

预设好的增量序列保存在数组 $dt[0\dots t-1]$ 中，整个希尔排序算法需执行 $t$ 趟。从上述步骤描述中可知，我们之前所讲的直接插入排序可以看成是增量为 1 的希尔排序，所以可以通过改写该算法，得到一趟希尔排序算法 shellInsert()。在 shellInsert() 中，具体改写以下地方：

• 前后记录位置的增量为 $dk$。

算法如下：

import { Item } from '../item.ts'

function shellInsert(unorderedList: Item[], dk: number) {
  for (let i = dk; i < unorderedList.length; i++) {
    if (unorderedList[i].key < unorderedList[i - dk].key) {
      const temp = unorderedList[i]
      let j = i - dk
      for (; j >= 0 && temp.key < unorderedList[j].key; j -= dk) {
        unorderedList[j + dk] = unorderedList[j]
      }
      unorderedList[j + dk] = temp
    }
  }
}

export function shellSort(unorderedList: Item[], dt: number[], t: number) {
  // 按增量序列 dt[] 对顺序表 unorderedList[] 做 t 趟希尔排序。
  for (let i = 0; i < t; i++) {
    shellInsert(unorderedList, dt[i])
  }
}

时间复杂度

当增量大于 1 时，关键字较小的记录是跳跃式地移动，从而使得在进行最后一趟增量为 1 的插入排序中，序列已基本有序，只要做记录的少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。但要具体进行分析，则是一个复杂的问题，因为希尔排序的时间复杂度是所取增量序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得一种最好的增量序列，但大量的研究已得出一些局部的结论。如有人指出，当增量序列为 $dt[k]=2^{t-k+1}-1$ 时，希尔排序的时间复杂度为 $O(n^{\frac{3}{2}})$，其中 $t$ 为排序趟数，$1⩽k⩽t⩽\lfloor {\log }_2(n+1)\rfloor$。还有人在大量的实验基础上推出：当 $n$ 在某个特定范围内，希尔排序所需的比较和移动次数约为 $n^{1.3}$，当 $n\to \mathrm{\infty }$ 时，可减少到 $n({\log }_{2}n{)}^2$。

空间复杂度

希尔排序和前两种排序方法一样，空间复杂度为 $O(1)$。

特点

1. 记录跳跃式地移动导致排序是不稳定的；
2. 只能用于顺序结构；
3. 增量序列可以有各种取法，但应该使增量序列中的值没有除 1 之外的公因子，并且最后一个增量值必须等于 1；
4. 记录总的比较次数和移动次数都比直接插入排序要少，$n$ 越大时，效果越明显。所以适合初始记录无序、$n$ 比较大的情况。