直接插入排序

1、第十章第十章 优化排序优化排序直接插入排序第第10章章 优化排序优化排序插入排序插入排序 插入排序的基本思想是：在一个已排好序的记录子集的基础上，每插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。将所有待排记录全部插入为止。 打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。入到合适位置，直到抓完牌为止，即可得到一个有

2、序序列。 第第10章章 优化排序优化排序直接插入排序直接插入排序 直接插入排序是一种最基本的插入排序方法。其基本操作是将第直接插入排序是一种最基本的插入排序方法。其基本操作是将第i个记录插入到前面个记录插入到前面i-1个已排好序的记录中，具体过程为：个已排好序的记录中，具体过程为： 将第将第i个记录的关键字个记录的关键字Ki顺次与其前面记录的关键字顺次与其前面记录的关键字Ki-1，Ki-2，, K1进行比较，将所有关键字大于进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于一个关键字小于或者等于Ki的记录的记录Kj，此时

3、，此时Kj后面必为空位置，将第后面必为空位置，将第i个记录插入空位置即个记录插入空位置即可。完整的直接插入排序是从可。完整的直接插入排序是从i=2开始的，也就是说，将第开始的，也就是说，将第1个记录视为已排好序的单元素个记录视为已排好序的单元素子集合，然后将第子集合，然后将第2个记录插入到单元素子集合中。个记录插入到单元素子集合中。i从从2循环到循环到n，即可实现完整的直接插，即可实现完整的直接插入排序。入排序。第第10章章 优化排序优化排序例例 设有一组关键字序列设有一组关键字序列43，21，89，15， ，28，这里，这里n=6，即有，即有6个记录。请将其按由小到大的顺序排序。个记录。请将

4、其按由小到大的顺序排序。 894343282115)28(6288943432115)43(5284389432115)15(4284315894321)89(3284315894321)21(2284315892143()654 32 1 0iiiiirrrrrrr初始关键字43第第10章章 优化排序优化排序 假设待排序记录存放在假设待排序记录存放在r1.n之中，为了提高效率，我们附设一个之中，为了提高效率，我们附设一个监视哨监视哨r0，使得，使得r0始终存放待插入的记录。监视哨的作用有两个：一始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是

5、防止越界，是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界，具体算法描述如下：具体算法描述如下： 第第10章章 优化排序优化排序void InsertSort(RecordType r,int n) int i,j; for(i=2;in;i+) /执行了执行了n-2次次 if (ri.keyri-1.key) r0=ri; j=i-1; /将带插入记录存放到监视哨中将带插入记录存放到监视哨中 while(r0.keyrj.key) /寻找插入位置寻找插入位置 rj+1=rj; j=j-1; /记录后移记录后移 rj+1=r0 /将待插入记录插入正确位置将待插入记录插入正确位置

6、第第10章章 优化排序优化排序该算法的要点是该算法的要点是： 使用监视哨使用监视哨r0临时保存待插入的记录；临时保存待插入的记录； 从后往前查找应插入的位置；从后往前查找应插入的位置； 查找与移动在同一循环中完成。查找与移动在同一循环中完成。第第10章章 优化排序优化排序 直接插入排序算法简便，比较适用于待排序记录数目较少且基本有直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好，序的情况。当待排记录数目较大时，直接插入排序的性能就不好， 为此为此我们可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，我们可以对直接插入排

7、序做进一步的改进。在直接插入排序法的基础上，从减少从减少“比较关键字比较关键字”和和“移动记录移动记录”两种操作的次数着手来进行改进。两种操作的次数着手来进行改进。 第第10章章 优化排序优化排序从空间分析来看，它只需要一个记录的辅助空间，空间复杂度为从空间分析来看，它只需要一个记录的辅助空间，空间复杂度为O（1）。）。从时间分析来看，外循环从时间分析来看，外循环for执行了执行了n-1次，每次循环的基本操作为次，每次循环的基本操作为:比较比较两个关键字的大小和移动记录。两个关键字的大小和移动记录。当原始记录的序列越接近有序，算法的执行效率就越高。当原始记录的序列越接近有序，算法的执行效率就越高。第第10章章 优化排序优化排序 在算法中，由于待插入元素的比较是从后向前进行的，当遇到关键在算法中，由于待插入元素的比较是从后向前进行的，当遇到关键字小于或等于要插入记录的关键字就停止操