第二节 插入排序

1、排序思想

假设待排序的记录存放在数组R[1..n]中，初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

2、实例分析

【例】给定一组关键字(46，39，17，23，28，55，18，46)，要求按直接插入排序算法给出每一趟排序结果。

3、算法描述

void InsertSort(Seqlist R，int n)

{　//对顺序表R做直接插入排序

　int i，j；

　for(i=2；i<=n；i++)

　if(R[i].key<R[i-1].key) 　　　　　　　　　//若R[i].key< R[i]，移动

　　{R[0]=R[i]；　　　　　　　　　　　 //当前记录复制为哨兵

　　 for(j=i-1；R[0].Key<R[j].key；j--)　　 //找插入位置

　　　　R[j+1]=R[j]； 　　　　　　　　//记录后移

　　R[j+1]=R[0]；　　　　　　　　　　 //R[i]插入到正确位置

　｝

｝

4、算法分析

（1）哨兵的作用

算法中引进的附加记录R[0]称为哨兵(Sentinel)， 哨兵有两个作用：

① 进入查找(插入位置)循环之前，它保存了R[i]的副本，不致于因记录后移而丢失R[i]的内容；

② 它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")，使得测试查找循环条件的时间大约减少了一半。

（2）算法的时间性能分析

对于具有n个记录的文件，要进行n-1趟排序。

各种状态下的时间复杂度：

（3）算法的空间复杂度分析

算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。

（4）直接插入排序是稳定的排序方法。

1、排序思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

2、实例分析

初始关键字序列为(36，25，48，27，65，25，43，58，76，32)。其增量序列的取值依次为5，3，l，排序过程如图所示。

3、算法描述

void ShellInsert(Seqlist R，int dk，int n)

{　//希尔排序中的一趟插入排序，dk为当前增量

　 int i，j；

　 for(i=dk+1；i<=n；i++)　　　　　　　　　 //将R[dk+1…n]分别插入有序区

　　if（R[i].key<R[i-dk].key）

　　　{ R[0]=R[i]；　　　　　　　　　　　 //暂存在R[0]中

　　　j=i-dk；

　　　while(j>0&&R[0].key<R[j].key)

　　　　{ R[j+dk]=R[j]；　　　　　　　　 //记录后移，查找插入位置

　　　　　j=j-dk；　　　　　　　　　　 //查找前一记录

　　　　}

　　　R[j+dk]=R[0]; 　　　　　　　　　　//插入R[i]到正确位置

　　}

}

void shellsort(seqList R，int d[]，int t，int n)

{　//按增量序列d[0…t-1]对顺序表R作希尔排序

　int k；

　for(k=0；k<t；k++)

　ShellInsert(R，d[k]，n)；

}

4、算法分析

（1）增量序列的选择

① 最后一个增量必须为1；

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

（2）Shell排序的时间性能优于直接插入排序，实验表明，当n较大时，比较和移动的次数约在n^l.25到1.6n^1.25之间。

（3）算法的空间复杂度分析

算法空间复杂度为O（1）。是一个就地排序。

（4）稳定性

希尔排序是不稳定的。