8.2 插入类排序

 

8.2  插入类排序

图8-3  插入排序示意图

插入排序的基本思路是：每一趟将一个待排序的记录，按其关键字值的大小插入到已经排序的部分文件中的适当位置上，直到全部插入完成。插入排序（Insertion Sort）是将插入的数据放在适当的位置，如图8-3所示。

本节介绍两种插入排序方法，即简单插入排序和希尔排序。

8.2.1  简单插入排序

简单插入排序是一种最简单的排序方法，其过程是依次将每个记录插入到一个有序的序列中去。

假设记录存放在R[0..n-1]中，R[0..i-1]是已排好序的记录；R[i..n-1]是未排序的记录。插入排序将R[i]插入到R[0..i-1]中，使R[0..i]成为有序的。插入R[i]的过程就是完成排序中的一趟。随着有序区的不断扩大，使R[0..n-1]全部有序。

简单插入排序算法如下：

void InsertSort(LineList R[ ],int n)

{

    int i,j;

    LineList tmp;

    for(i=1;i<n;i++)

    {  

        tmp=R[i];

        j=i-1;

        while(j>=0 && tmp.key<R[j].key  /*元素后移，以便腾出一个位置插入tmp*/

        {  

            R[j+1]=R[j];

            j--;

        }

        R[j+1]=tmp;                     /*在j+1位置处插入tmp*/

    }

}

例如，一组待排序记录的关键字为13，38，22，97，76，65，38，58，而且该组中的前2个记录已按关键字递增构成一个有序序列{13,38}，现要将第3 个记录（即关键字为22对应的记录）插入到有序序列中，以得到新的含有3个记录的有序序列。显然，首先需要查找到22的正确插入位置，再进行插入。此时可以将第3个记录对应的关键字22与有序序列表{13,38}中从最后一个记录对应的关键字逐个比较，即从开始从右向左检索。因为22<38，可将R₃₈后移一个位置，又由于22>13，此时就可以确定R₂₂应在R₁₃和R₃₈之间，由于R₃₈已后移一个空间，正好腾出一个位置，此时就可将R₂₂插入，从而得到一个新的有序序列，其对应的关键字序列为{13,22,38}，此时称进行了一次直接插入排序过程。后面的记录可用同样的方法插入，从而得到整个直接插入排序的过程。

先将第1个记录作为一个有序序列，然后从第2个记录起逐个插入到该有序序列中，使得插入后仍然是有序序列，依此类推，直到排序结束。

显然，若记录的个数为n，则需进行n-1次直接插入排序过程。

由此可以得到前面所给例子的简单插入排序过程，如图8-4所示。

采用这种排序方法时，要在R[0..i-1]的有序表中插入一个新元素，关键字的比较次数最少是1次（留在原处），最多是i次（插到最前面）；元素的移动次数等于关键字比较次数加2。其总的比较次数和移动次数为：最少比较n-1次，最多比较次；最少移动2(n-1)次（tmp=R[i]和R[j+1]=tmp语句各算1次），最多移动次。

因此，算法的执行时间在最坏的情况下是O(n²)。

简单插入排序是稳定的。因为当i>j，而且R[i].key和R[j].key相等时，本算法将R[i]插在R[j]的后面，使R[i]和R[j]的相对位置保持不变。

图8-4  简单插入排序过程

8.2.2  希尔排序

希尔（Shell）排序又称为缩小增量排序方法，其基本思路是：将记录按下标的一定增量d分组，对每组记录采用直接插入排序的方法进行排序，随着增量逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序。

【例8-2】 已知有10个待排序的记录，它们的关键字序列为{75,87,68,92,88,61,77,96,

80,72}，给出用希尔排序法进行排序的过程。

解：希尔排序过程如图8-5所示。

图8-5  希尔排序过程

希尔排序算法如下：

void ShellSort(LineList R[],int n)

{

int i,j,gap;

LineList tmp;

gap=n/2;                              /*增量置初值*/

while(gap>0)

{

    for(i=gap;i<n;i++)                  /*对所有相隔gap位置的元素组进行排序*/

    {  

        tmp=R[i];  

        j=i-gap;

        while(j>=0 && tmp.key<R[j].key)/*对相隔gap位置的元素组进行排序*/

        {  

            R[j+gap]=R[j];

            j=j-gap;                    /*移到本组中的前一个元素*/

        }

        R[j+gap]=tmp;  

        j=j-gap;

    }

    gap=gap/2;                          /*减小增量*/

}

}

为了实现例8-2的功能，设计如下主函数：

void main()

{

    LineList R[MaxSize];

    KeyType a[ ]={75,87,68,92,88,61,77,96,80,72};

    int n=10,i;

    for (i=0;i<n;i++)

        R[i].key=a[i];

    printf("排序前:");

    for (i=0;i<n;i++)

        printf("%3d",R[i].key);

    printf("\n");

    ShellSort(R,n);                     /*递归调用希尔排序算法*/

    printf("排序后:");

    for (i=0;i<n;i++)

        printf("%3d",R[i].key);

    printf("\n");

}

本程序的执行结果：

排序前:75 87 68 92 88 61 77 96 80 72

排序后:61 68 72 75 77 80 87 88 92 96

希尔排序算法的时间复杂度是O(nlog₂n)。