插入类排序法

2.8.2　插入类排序法

冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。本小节讨论另一类排序的方法，即插入类排序法。

1．简单插入排序法

所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

在线性表中，只包含第1个元素的子表显然可以看成是有序表。接下来的问题是，从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中。一般来说，假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下：

首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。

如图2-37所示给出了插入排序的示意图。图中画有方框的元素表示刚被插入到有序子表中。

图2-37　简单插入排序示意图

在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要进行n(n-1)/2次比较。

2．希尔排序法

希尔排序法（Shell Sort）属于插入类排序，但它对简单插入排序作了较大的改进。

希尔排序法的基本思想如下：

将整个无序序列分割成若干小的子序列分别进行插入排序。

子序列的分割方法如下：

将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成了。

增量序列一般取h_t=n/2^k（k=1，2，…，[log₂n]），其中n为待排序序列的长度。

如图2-38所示为希尔排序法的示意图。

图2-38　希尔排序法示意图

在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一次比较就有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。

希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为O（n^1.5）。