您的位置: 网站首页 > 程序开发 > 数据结构 > 附录 习题答案 > 【第8章 排 序】

第8章 排 序

 

1选择题

ABCCB  DCCDC  BCCBB  CC

2填空题

13

224,(233815

3)堆排序,快速排序,归并排序,归并排序,快速排序,堆排序

4)希尔排序、选择排序、快速排序和堆排序

5)快速排序,基数排序

6)堆排序,快速排序

7)插入排序,选择排序

8n-1

3问答题

1)排序过程如下。

初始序列:  17 18 60 40 7 32 73 65 85

1趟排序:7 17 18 60 40 32 65 73 85

2趟排序:7 17 18 32 60 40 65 73 85

3趟排序:7 17 18 32 40 60 65 73 85

最终结果:  7 17 18 32 40 60 65 73 85

2)排序过程如下。

初始序列:  503 87 512 61 908 170 897 275 653 462

1趟排序:462 87 275 61 170 503 897 908 653 512

2趟排序:170 87 275 61 462 503 897 908 653 512

3趟排序:61 87 170 275 462 503 897 908 653 512

4趟排序:61 87 170 275 462 503 897 908 653 512

5趟排序:61 87 170 275 462 503 512 653 897 908

6趟排序:61 87 170 275 462 503 512 653 897 908

最终结果:  61 87 170 275 462 503 512 653 897 908

3)排序过程如下。

初始序列:          503,17,512,908,170,897,275,653,426,154,509,612,677,765,703,94

1次排序(d1=8):426,17,509,612,170,765,275,94,503,154,512,908,677,897,703,653

2次排序(d2=4):170,17,275,94,426,154,509,612,503,765,512,653,677,897,703,908

3次排序(d3=2):170,17,275,94,426,154,503,612,509,653,512,765,677,897,703,908

4次排序(d1=1):17,94,154,170,275,426,503,509,512,612,653,677,703,765,897,908

4)排序过程如下。

初始序列:  (70),83,100,65,10,32,7,9

1次排序:(70,83),100,65,10,32,7,9

2次排序:(70,83,100),65,10,32,7,9

3次排序:(65,70,83,100),10,32,7,9

4次排序:(10,65,70,83,100),32,7,9

5次排序:(10,32,65,70,83,100),7,9

6次排序:(7,10,32,65,70,83,100),9

7次排序:(7,9,10,32,65,70,83,100)

5)排序过程如下。

初始序列:  10 18 4 3 6 12 1 9 18 8

1趟排序:10 18 3 4 6 12 1 9 8 18

2趟排序:3 4 10 18 1 6 9 12 8 18

3趟排序:1 3 4 6 9 10 12 18 8 18

4趟排序:1 3 4 6 8 9 10 12 18 18

最终结果:  1 3 4 6 8 9 10 12 18 18

4上机操作题

1)利用奇偶转换排序使整个数组有序。

没有交换元素为止即结束排序。

实现本题奇偶转换排序的函数如下。

void oesort(int A[],int n)

{

int i,flag;

   do

    {

        flag=0;

        for(i=1;i<=n;i++)                               /*奇数扫描*/

        {

            if(A[i]>A[i+1])

              {

                flag=1;

                  t=A[i+1];A[i+1]=A[i];A[i]=t;

              }

              i++;

        }

        for(i=2;i<=n;i++)                               /*偶数扫描*/

        {

            if(A[i]>A[i+1])

              {

                flag=1;

                  t=A[i+1];A[i+1]=A[i];A[i]=t;

              }

              i++;

        }

     } while(flag!=0);

}

2)采用快速排序的一趟排序思想,算法描述如下:

Void split(int a[],int n)

{

    int i=0,j=n-1,x;

    while (i<j)

    {

        while(i<j&&a[j]>=0)

        j--;

        while(i<j&&a[i]<0)

        i++;

        if(i<j)

        {

            x=a[i];a[i]=a[j];a[j]=x;}

        }

    }

}

3)另设一个数组c[n],其中c[j]保存排序码值比r[j]的排序码值小的记录个数。算法如下:

Void Coumtsort(ReeType r[ ],int n)

{

    int I,j,x,*c;

    ReeType s;

    c=(int *)malloc(sizeof(int)*n);

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

        c[i]=0;

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

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

        if(r[i].key<r[j].key)

            c[j]++;

        else

    c[i]++;

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

    while(c[i]!=i)

    {

        x=c[i];s=r[i];

        c[i]=c[x];r[i]=r[x];

        c[x]=x;r[x]=s;

    }

    free(c);

}

4算法如下

Void HeapIns(RecType r[],int n,int x)

{

    int i;

    i=n/2-1;

    if(r[i].key<=x) 

    r[n].key=x;

    else

    {

        j=n;

        while(i>=0&&r[i].key>x)

        {

            r[j]=r[i];

            j=i;i=(i-1)/2;

        }

        r[j].key=x;

    }

}

5)该题实际上是实现计数排序的过程。对应的算法如下:

void CountSort(NodeType R[],int n)

{

    int i,j;

    for(i=0;i<n;i++)                                      /*置初值*/

         R[i].count=0;

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

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

             if(R[i].key<R[j].key)

                  R[i].count++;

             else

                  R[i].count=1;

}