8.2.1　直接插入排序

1.直接插入排序的基本思想

直接插入排序是一种比较简单的排序方法。它的基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段……依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第i个记录，则应该将这个记录插入到由前i－1个记录组成的有序段中，从而形成一个由i个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过n－1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。

例如，关键字序列T＝（13，6，3，31，9，27，5，11），插入排序的中间过程序列如图8－1所示。

图8－1 直接插入排序过程

注：方括号【】内的表示有序段。

2.直接插入排序算法

直接插入排序算法主要应用比较和移动两种操作，将第i个记录插入由前面i－1个记录构成的有序段中，步骤如下：

（1）将待插入记录a［i］保存在a［0］中，即a［0］＝a［i］；

（2）搜索插入位置：

算法8.1 插入排序

3.直接插入排序的算法复杂度

从上面的叙述可见，直接插入排序的算法简洁，容易实现，那么它的效率如何呢？

从空间来看，它只需要一个记录的辅助空间，从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。先分析一趟插入排序的情况。算法8.1中里层的for循环的次数取决于待插记录的关键字与前i－1个记录的关键字之间的关系。若L.r［i］.key＜L.r［1］.key，则内循环中，待插记录的关键字需与有序子序列L.r［1..i－1］中i－1个记录的关键字和监视哨中的关键字进行比较，并将L.r［1..i－1］中i－1个记录后移。则在整个排序过程（进行n－1趟插入排序）中，当待排序列中记录按关键字非递减有序排列（以下称为“正序”）时，所需进行关键字间比较的次数达最小值n－1（即），记录无须移动；反之，当待排序列中记录按关键字非递增有序排列（以下称为“逆序”）时，总的比较次数达最大值（n＋2）（n－1）／2（即），记录移动的次数也达最大值（n＋4）（n－1）／2（即（i＋1））。若待排序记录是随机的，即待排序列中的记录可能出现的各种排列的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数，约为n2／4。由此，直接插入排序的时间复杂度为O（n2），空间复杂度只占一个单元（r［0］）。

直接插入排序算法简单，容易实现，只需要一个记录大小的辅助空间用于存放待插入的记录（在C语言中，我们利用了数组中的0单元）和两个int型变量。当待排序记录较少时，排序速度较快，但是，当待排序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。插入排序是一种稳定的排序方法。