第十章  排序

一、名词解释

1.排序       2.内部排序     3.外部排序          4.堆         5.堆排序

二、填空

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。

3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。

4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。

5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。

6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。

    void straightsort(list r);

      {for(i=___________;i<=n;i++)

{r[0]=r[i];j=i-1;

         while(r[0].key<r[j].key){r[j+1]=________;j--;}

r[j+1]=_______;

}

}

7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。

8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。

    void bulbblesort(int n,list r) 

      {for(i=1;i<=________;i++)

         {_______________;

for(j=1;j<=_________;j++)

   if(r[j+1].key<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}

if(flag) return;

}

}

9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。

10.以下对r[h],r[h+1],……r[p]子序列进行一趟忆速排序。请分析算法，并在________上填充适当的语句。

    int quickpass(list r,int h,int p)

      {i=h;j=p;x=r[i];

        while(i<j)

          {while((r[j].key>=x.key)&&(i<j))________;

           if(i<j)

            {________;i++;

             while((r[i].key<=x.key)&&(i<j))________;

             if(i<j){________;j--;}

             }

           }

       r[i]=________;return(i);

  }

11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度是________。

12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。

  void select(list r,int n)

   {for(i=1;i<=________;i++)

     {k=i;

      for(j=i+1;j<=n;j++)if(r[j].key<r[k].key)________;

      if(______)swap(r[k],r[i]）;

     }

   }

13.直接选择排序是不稳定的，其时间复杂性为________。

14.树形选择排序要增加________个结点以保存前面比较的结果。另外，排序的结果还需要另外开辟________.

15.树形选择排序可用一棵树来表示这一排序过程，树中的n个叶子代表待排序记录的键值，叶子上面一层是________两两比较的结果，依次类推。________表示最后选择出来的最小关键字。在选择次最小键值时，只需将叶结点中最小键值改成________，重新进行比较。依次类推。

16.若树形选择排序的叶子数为n，除第一次需执行________次比较就选择出一个最小的键值外，以后的每次都只经过________次比较就选择出一个最小的键值。所以树形选择排序总的时间开销为________。

17.从一个无序序列建立一个堆的方法是：首先将要排序的所有键值分放到一棵________的各个结点中，然后从i=________的结点k_i开始，逐步把以k_n/2,k_n/2-1,k_n/2-2,……为根的子树排成堆，直到以k₁为根的树排成堆，就完成了建堆的过程。

18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。

19.以下将a_h,…,a_m和a_m+1,…,a_n两个有序序列（它们相应的关键字值满足K_h<=…<=K_m,K_m+1<=…<=K_n）合并成一个有序序列R_h，…,R_n（使其关键字值满足K_h<=…<=K_n）。请分析算法，并在________上填充适当的语句。

    void merge(list a,list R,int h,int m,int n)

      {i=h;k=h;j=m+1;

       while((i<=m)&&(j<=n))

         {if(a[i].key<=a[j].key){R[k]=________;________;}

          else{R[k]=________;________;}

          k++;

          }

       while(i<=________){R[k]=a[i];i++;k++;}

       while(j<=________){R[k]=a[j];j++;k++;}

       }

此算法的执行时间为________.

20．归并排序要求待排序列由若干个___________的子序列组成。

21．二路归并排序的时间复杂度是___________。

22．对于n个记录的集合进行归并排序，所需的附加空间消耗是___________。

23.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。

24．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序进行排序，最省时间的是___________算法，最费时间的是___________算法。

三、单项选择

1．  以下说法错误的是                                            （     ）

①直接插入排序的空间复杂度为O(1)。

②快速排序附加存储开销为O(log₂n)。

③堆排序的空间复杂度为O(n)。

④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。

2．  以下不稳定的排序方法是                                      （     ）

①直接插入排序        ②冒泡排序        ③直接选择排序    ④二路归并排序   

3．  以下稳定的排序方法是                                         （     ）

①快速排序            ②冒泡排序        ③直接选择排序    ④ 堆排序

4．  以下时间复杂性不是O(n²)的排序方法是                         （     ）

①直接插入排序       ②二路归并排序     ③冒泡排序        ④直接选择排序

5．  以下时间复杂性不是O(nlog₂n)的排序方法是                      （     ）

①堆排序            ② 直接插入排序     ③二路归并排序    ④快速排序       

6．  在文件局部有序或文件长度较小的情况下，最佳的排序方法是        （     ）

①直接插入排序      ② 冒泡排序        ③ 直接选择排序    ④归并排序

7．  对于大文件的排序要研究在外设上的排序技术，即                  （     ）

①快速排序法        ② 内排序法         ③外排序法       ④ 交叉排序法

8．排序的目的是为了以后对已排序的数据元数进行（     ）操作。

①打印输出           ②分类             ③ 合并            ④查找

9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（     ）

①n-1                ②log₂n           ③ 2log₂n          ④n²

10.快速排序在最坏的情况下的时间复杂度是                           （     ）

①O(log₂n)           ②O(nlog₂n)       ③ O(n²)           ④O(n³)

11.具有24个记录的序列，采用冒泡排序至少的比较次数是              （     ）

①1                  ②23              ③ 24             ④ 529

12．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：

25   84   21   47   15   27   68   35   20

15   20   21   25   47   27   68   35   84  

15   20   21   25   35   27   47   68   84

15   20   21   25   27   35   47   68   84

则采取的排序方法是                                               （     ）

①直接选择排序       ②冒泡排序         ③快速排序         ④二路归并排序

13．在排序过程中，健值比较的次数与初始序列的排列顺序无关的是     （     ）

①直接插入排序和快速排序              ②直接插入排序和归并排序

③直接选择排序和归并排序              ④快速排序和归并排序

14．（   ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。

①归并排序          ② 插入排序          ③快速排序         ④选择排序

15（    ）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。

①归并排序           ②插入排序         ③ 快速排序         ④选择排序

16．（    ）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

①归并排序           ②插入排序         ③快速排序         ④选择排序

17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（    ）方法能够最快地找出其中最大的正整数。

①快速排序           ②插入排序         ③ 选择排序        ④ 归并排序

18一般情况下，以下四种排序方法中，平均查找长度最小的是                  （     ）

①归并排序           ②快速排序          ③选择排序         ④插入排序

19．以下四种排序方法中，要求附加的内存容量最大的是                       （     ）

①插入排序           ②选择排序          ③快速排序         ④归并排序

20已知一个链表中有3000个结点，每个结点存放一个整数，（     ）可用于解决这3000个整数的排序问题且不需要对算法作大的变动。

①直接插入排序法                        ②简单选择排序方法

③快速排序方法                           ④堆排序方法

21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（    ）次比较。

①33               ②45                ③70                  ④91

22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法

①正确                ②错误

23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（    ）方法。

①归并排序            ②直接插入排序

③直接选择排序        ④快速排序。

四、简答及应用

1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。

2．举例说明本章介绍的各排序方法中那些是不稳定的？

3．相对于树形选择排序，直接选择排序和堆排序有何优点？

4．试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。

5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。

（1）（3，10，12，22，36，18，28，40）；

（2）（5，8，11，15，23，20，32，7）。

6．对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。

7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。

五、算法设计

1．  设计一个用链表表示的直接选择排序算法。

2．  写出非递归调用的快速排序算法。

3．  插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序方法。

4．  一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。

5．  已知（k₁,k₂……，k_n）是堆，试写一个算法将（k₁,k₂,……，k_n,k_n+1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k _n+1后应从叶子向根的方向调整）。

6．  设计一个用链表表示的直接插入排序算法。

 

                                   第十章  排序参考答案

二、填空

1．稳定、不稳定　　　　　　　　　　　　　　 2.内部、外部

3．插入排序、交换排序、选择排序、归并排序　 4.键值比较、记录移动、附加空间

5．直接、折半、表、希尔　　　　　　　　　　 6.2、r[j]、r[0]

7.O（n²）、O（1）                            8.n-1、flag=1、n-i

9.O(n²)                                      10.j--、r[i]=r[j]、j++、r[j]=r[i]、x

11.O(nlog2n)、O(n²)                           12.n-1、k=j、k!=I

13.O(n²)                                     14.n-1、存储区

15.叶子、树根、＋∝　　　　　　　　　　　　　16.n-1、log₂n、O(nlog₂n)

17.完全二叉树、n/2                           18.O(1)、O(nlog₂n)

19.a[ii]、ii++、a[j]、j++、m、n、O(n-h+1)       20.有序

21．O(log₂n)                                 22.O(n²)

23.冒泡排序、快速排序　　　　　　　　　　　　24.插入排序、快速排序

三、单项选择

1. ③     2. ③     3. ②    4. ②     5. ②     6. ②

7. ③     8. ④     9. ①   10. ③    11. ②    12. ③

13. ③   14. ④    15. ④   16. ③    17. ③    18. ②

19. ④   20. ④    21. ④   22. ②    23. ③

四、简答及应用

1．①直接插入排序

序号　　1　　2　　3　　4　　5　　6　　7　　8　　9　　10　　11　　12

　 关键字　83   40　 63   13   84   35   96   57   39    79    61    15

i = 2   40   83   [63   13   84   35   96   57   39    79    61    15]

i = 3   40   63   83   [13   84   35   96   57   39    79    61    15]

i = 4   13   40   63   83   [84   35   96   57   39    79    61    15]

i = 5   13   40   63   83   84   [35   96   57   39    79    61    15]

i = 6   13   35   40   63   83   84   [96   57   39    79    61    15]

i = 7   13   35   40   63   83   84   96   [57   39    79    61    15]

i = 8   13   35   40   57   63   83   84   96   [39    79    61    15]

i = 9   13   35   39   40   57   63   83   84   96    [79    61    15]

i = 10  13   35   39   40   57   63   79   83   84    96    [61    15]

i = 11  13   35   39   40   57   61   63   79   83    84    96    [15]

i = 12  13   15   35   39   40   57   61   63   79    83    84    96

　②直接选择排序

序号　　1　　2　　3　　4　　5　　6　　7　　8　　9　　10　　11　　12

　 关键字　83   40　 63   13   84   35   96   57   39    79    61    15

i = 1   13   [40   63   83   84   35   96   57   39    79    61    15]

i = 2   13   15   [63   83   84   35   96   57   39    79    61    40]

i = 3   13   15   35   [83   84   63   96   57   39    79    61    40]

i = 4   13   15   35   39   [84   63   96   57   83    79    61    40]

i = 5   13   15   35   39   40   [63   96   57   83    79    61    84]

i = 6   13   15   35   39   40   57   [96   63   83    79    61    84]

i = 7   13   15   35   39   40   57   61   [63   83    79    96    84]

i = 8   13   15   35   39   40   57   61   63   [83    79    96    84]

i = 9   13   15   35   39   40   57   61   63   79    [83    96    84]

i = 10  13   15   35   39   40   57   61   63   79    83    [96    84]

i = 11  13   15   35   39   40   57   61   63   79    83    84    [96]

　③快速排序

　 关键字　　　83   40　 63   13   84   35   96   57   39    79    61    15

第一趟排序后  [15   40   63   13   61   35   79   57   39]    83   [96    84]

第二趟排序后  [13]   15  [63   40   61   35   79   57   39]    83 　 84   [96]

第三趟排序后   13   15  [39   40   61   35   57]   63  [79]    83    84    96

第四趟排序后   13   15  [35]   39  [61   40   57]   63   79    83    84    96

第五趟排序后   13   15   35   39  [57   40]   61   63   79    83    84    96

第六趟排序后   13   15   35   39  40   [57]   61   63   79    83    84    96

第七趟排序后   13   15   35   39  40    57   61   63   79    83    84    96

④堆排序

关键字：　83　40　63　13　84　35　96　57　39　79　61　15

排序成功的序列：96　84　83　79　63　61　57　40　39　35　15　13

　　　　　排序过程如图简答题8－1.1、8－1.2、8－1.3所示。

⑤归并排序

　 关键字　　　83   40　 63   13   84   35   96   57   39    79    61    15

第一趟排序后   [40  83]   [13  63]  [35   84]  [57  96]   [39   79]   [15    61]

第二趟排序后   [13   40   63   83]  [35  57   84   96]   [15   39 　 61    79]

第三趟排序后   [13   35   40   57   63   83   84   96]  [15    39    61    79]

第四趟排序后   13   15    35   39   40   57   61   63   79    83    84    96

 

2．稳定排序有直接插入、冒泡排序、归并排序。

　不稳定排序有快速排序、直接选择排序、堆排序。举例如下：

①快速排序

初始状态　　40　　65　　38　　49　　97　　65　　13　　60

 排序后 　　13　　38　　40　　49　　60　　65　　65　　97

（65表示记录初始位置在65记录位置之后）

②堆排序

初始状态　　65　　38　　75　　97　　80　　13　　27　　65

 排序后 　　13　　27　　38　　65　　65　　75　　80　　97

③直接排序

初始状态　　40　　65　　38　　49　　97　　65　　13　　60

 排序后 　　13　　38　　40　　49　　60　　65　　65　　97

 

3．直接选择相对于树形选择排序的优点：算法易懂，容易实现，基本上不需要附加空间。而树形排序需要附加n – 1附加空间。

直接选择排序相对于树形选择排序的缺点：直接选择排序每一趟都不保留比较结果比较次数较多，而树形排序则能利用大部分上一次的比较结果，因此时间性能比直接选择排序优越。

堆排序相对于树形排序的优点：堆排序除建第一个堆费时外，其余元素进行堆比较次数小于等于h（h表示n元素构成的完全二叉树的深度），而树形排序每次比较都是h次。因此，堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。

4．直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表：

 

 

	平均时间	最坏情况	辅助空间
直接插入	O(n2)	O(n2)	O(n1)
直接选择	O(n2)	O(n2)	O(1)
快速排序	O(nlg2n)	O(n2)	O(nlog2n)
堆排序	O(nlog2n)	O(nlog2)	O(1)
归并排序	O(nlog2n)	O(nlog2n)	O(n)

 

 

 从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下，时间性能不如堆排序和归并排序。　而后两者相比的结果是，当n较大时，归并排序所需时间优于堆排序，但它所需辅助空间最多。

注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于n较大的情况，有适用于n较小的情况，还有的与关键字的分布和初始位置有关……因此，在实际使用时，需要根据不同情况适当选用排序方法，甚至可将多种方法结合使用。

5．分析：先按序列画出对应的完全二叉树，再看其是否满足堆的定义。按这一思路，画出的完全二叉树见图简答8-5.1.

显然序列⑴是堆，而序列⑵不是堆，值为7的元素应该上调，调整过程见图简答题8-5.2.

6.第一趟：　　 [46,  58,  15,  45,  90,  18,  10,  62]

              [46,  58,  15,  45,  90,  18,  10,  62] .

一次交换之后　[10,  58,  15,  45,  90,  18,  46,  62]

二次交换之后　[10,  46,  15,  45,  90,  18,  58,  62]

三次交换之后　[10,  18,  15,  45,  90,  46,  58,  62]

　[10,  18,  15,  45,  90,  46,  58,  62]

　　　　　　　[10,  18,  15,  45,  90,  46,  58,  62]

四次交换之后　[10,  18,  15,  45,  46,  90,  58,  62]

 

以上“－”表示当前经比较不交换位置的元素。“　”表示当前经比较交换位置的元素。

　　第一趟：　[10  18  15  45]  46  [90  58  62]

    第二趟：　10  [18  15  45]  46  [62  58]  90

    第三趟：　10  [15] 18  45]  46  [58]  62  90

    结果：　　10  15　 18  45   46  58  62  90

7．

⑴插入排序的每趟的结果

　　　初始值健值序列　[12]  5  9  20  6  31  24

          i=2         [5  12]  9  20  6  31  24

          i=3         [5  9  12]  20  6  31  24

          i=4         [5  9  12  20]  6  31  24

          i=5         [5  6  9  12  20]  31  24

          i=6         [5  6  9  12  20  31]  24

          i=7         [5  6  9  12  20  24  31]

 

 

⑵冒泡排序的每趟的结果：

　　　初始键值序列　　[12  5  9  20  6  31  24]

        第一趟之后　　[5  9  12  6  20  24]  31

        第二趟之后　　[5  9  6  12  20]  24  31

        第三趟之后　　[5  6  9  12]  20  24  31

        第四趟之后　　 5  6  9  12  20  24  31

 

五、算法设计

1.分析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当前的有序表区的最后。

Void selesort ( lklist L )             

    {  q=L;                     

      while ( q-> next !=NULL )

         {  pl = q -> next ;

            minp =pl;            

            while ( pl -> next != NULL )

               { if ( pl -> next -> data < minp -> data )

                 minp = pl -> next ;

                 pl = pl -> next ;     

                }

             if ( minp != q -> next) 

{ r1 = minp -> next ;

  minp -> next = r1 -> next ;      

  r2 = q -> next ;

  q -> next = r2 -> next ;

  r1 -> next = q -> next ;

  q -> next = r1 ;      

  r2 -> next = minp -> next ;

  minp -> next = r2 ;   

 }

q = q > next ;            

                 }

}

2.分析：先调用划分函数 quickpass () ,以确定中间元素的位置，然后再借助栈分别对中间元素左、右两边的区域进行快速排序。

　Void qksort ( list A )                 

    { InitStack ( S ) ;                 

　　　j = 1 ; h = n ;                  

      while ( ( j < h ) ‖( !empty ( S ) ) )

      { while ( j < h )

          { quickpass ( A,j,h,i ) ;      

            push ( S,j,h,i ) ;            

            h = i – 1 ;              

          }

       if ( !empty ( S ) )

            { pop ( S,j,h,i ) ;         

              j = i + 1 ;            

            }

       }

     }   

3．分析：插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区，当然可以用二分查找来确定插入位置。

　　Void straightsort ( list A )     

          {  for ( i =2 ; i <= n ; i + + )

{  low = 1 ; high =  i – 1 ;  

   A[0] . key = A[i] . key ;

  While ( low <= high )

     { mid = ( low + high ) /2 ;

       switch

         { case : A[0] . key <= A[mid] . key : high = mid – 1 ;

          case : A[0] . key > A[mid] . key : low = mid + 1 ;  

          }

        for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ;          

A[ mid ] = A[ i ] ;

}

              }

         }

   4．分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上、下界相遇。

Void example ( datatype A [n] )

  {  i = 1, j = n ;                                     

    while ( i < j )

        { while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ;           

          while ( (i < j ) && ( A[ j ] > 0 )) j - - ;          

          if ( i < j)

           { temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ;   

             i++ ; j - -;

           }

        }

   }

5．分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1] , a[ 2 ],…,a[ k]为堆，增加一个无素a[ k + 1 ],把数组a[ 1 ],a[ 2 ], …,a[ k + 1 ]调整为堆。第二个算法heep 从1开始调用算法sift将整个数组调整为堆。

 Void sift (datatype A[ n ] , int  K)             

     {  x = A[ K+1] ;

        i = K +1 ;

while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;}

A[i] = x ;

         }

Void heap ( datatype A[ n ] ) ; 

  { for ( k = 1 ; k <= n-1; k++ ) sift ( A,k ) ; }

6．分析：本算法采用的存储结构是带头结点的双循环链表。首先找元素插入位置，然后把元素从原链表中删除，插入到相应的位置处。请注意双链表上插入和删除操作的步骤。

Void sort ( dlklist H )                   

 { pre = H -> next ;

   while ( p != H )

     {p = pre -> next ;                 

      q = p -> next ;                   

      while((pre!=H)&&(p->data<pre ->data))pre=pre–prior;

 if ( pre ! =p -> prior )

   { p-> prior->next = p -> next ;      

    p-> next->prior = p -> prior;

    p->next = pre ->next ;           

    pre -> next -> prior = p ;

    p ->prior= pre ; pre ->next = p ;

   }

  p=q;

 }

     }