第7章  排序

一、选择题

1．某内排序方法的稳定性是指(  D  )。

A．该排序算法不允许有相同的关键字记录     B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法        D．以上都不对

2．下面给出的四种排序法中(   D )排序法是不稳定性排序法。

    A. 插入           B. 冒泡              C. 二路归并        D. 堆

3．下列排序算法中，其中（   D ）是稳定的。

A. 堆排序，冒泡排序              B. 快速排序，堆排序  

  C. 直接选择排序，归并排序       D. 归并排序，冒泡排序

4．稳定的排序方法是（ B   ） 

A．直接插入排序和快速排序       B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序   D．树形选择排序和shell排序

5．下列排序方法中，哪一个是稳定的排序方法？（  B　） 

A．直接选择排序      B．二分法插入排序      C．希尔排序        D．快速排序

6．若要求尽可能快地对序列进行稳定的排序，则应选（B）。

 A．快速排序  B．归并排序  C．冒泡排序

7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（   CE ）就是不稳定的排序方法。

A．起泡排序    B．归并排序    C．Shell排序    D．直接插入排序    E．简单选择排序

8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（A   ）排序为宜。

A．直接插入  B．直接选择  C．堆  D．快速  E．基数 

9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（  C  ）。

  A. 快速排序        B. 堆排序        C. 归并排序         D. 直接插入排序

10．下面的排序算法中，不稳定的是（ CDF   ）

A.起泡排序  B.折半插入排序   C.简单选择排序    D.希尔排序     E.基数排序  F.堆排序。

11．下列内部排序算法中： 

A．快速排序   B.直接插入排序  C. 二路归并排序  D. 简单选择排序  E. 起泡排序   F. 堆排序

（1） 其比较次数与序列初态无关的算法是（ DC   ）    （2）不稳定的排序算法是（  ADF  ）

（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k 归并排序

       E．以上答案都不对   

59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 CADBG

（1）--（5）:   A．选择排序    B．快速排序     C．插入排序     D．起泡排序

E．归并排序    F．shell排序    G．堆排序       H．基数排序

二、填空题

1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较____和记录的___移动__。

2. 外排序的基本操作过程是__生成有序归并段_____和_归并______。

3. 属于不稳定排序的有_希尔排序、简单选择排序、快速排序、堆排序_________。

4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是__冒泡___算法，最费时间的是___快速___算法。

5. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_简单选择排序____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是__直接插入排序___。

6．直接插入排序用监视哨的作用是__免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效_____。

7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为__ n(n-1)/2_____。

8. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______3____趟，写出第一趟结束后，数组中数据的排列次序_ (10,7,-9,0,47,23,1,8,98,36)________。

9．从平均时间性能而言，____快速______排序最佳。

10．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_ (4,1,3,2,6,5,7)____。

11．快速排序在_每次划分能得到两个等长的子序列____的情况下最易发挥其长处。

12．在数据表有序时，快速排序算法的时间复杂度是__ O(n2)__。

13．堆排序的算法时间复杂度为：_ O(nlog2n)____。

三、应用题

1． 在堆排序、快速排序和合并排序中：

(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

(1)堆排序，快速排序，归并排序(2)归并排序 (3)快速排序 (4)堆排序

2. 快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？ 

平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排序、堆排序、希尔排序。

3．算法模拟

设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。

(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(3) 直接插入排序算法和直接选择排序算法的稳定性如何？

(1)直接插入排序

第一趟 (3)[8,3],2,5,9,1,6

第二趟 (2)[8,3,2],5,9,1,6

第三趟 (5)[8,5,3,2],9,1,6

第四趟 (9)[9,8,5,3,2],1,6

第五趟 (1)[9,8,5,3,2,1],6

第六趟 (6)[9,8,6,5,3,2,1]

 (2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）

第一趟 (9)[9],3,2,5,8,1,6

第二趟 (8)[9,8],2,5,3,1,6

第三趟 (6)[9,8,6],5,3,1,2

第四趟 (5)[9,8,6,5],3,1,2

第五趟 (3)[9,8,6,5,3],1,2

第六趟 (2)[9,8,6,5,3,2],1

(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。

4．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

初始序列：[28],07,39,10,65,14,61,17,50,21

21移动：21,07,39,10,65,14,61,17,50,[]

39移动：21,07,[],10,65,14,61,17,50,39

17移动：21,07,17,10,65,14,61,[],50,39

65移动：21,07,17,10,[],14,61,65,50,39

14移动：21,07,17,10,14,[28],61,65,50,39

5．已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。

建立堆结构：__ :97,87,26,61,70,12,3,45___________

交换与调整：

（1）87 70 26 61 45 12 3 97;

（2）______ 70,61,26,3,45,12,87,97______________;

（3）61 45 26 3 12 70 87 97;

（4）_______ 45,12,26,3,61,70,87,97_____________;

（5）26 12 3 45 61 70 87 97;

（6）_______ 12,3,26,45,61,70,87,97_____________;

（7）3 12 26 45 61 70 87 97;

6．全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？

堆排序

在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有的有序子序列中，但要比较n-1次。选次大元素要再比较n-2次,其时间复杂度是O(n2)。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大（或最小，视大堆或小堆而定）元素，然后，调堆又选出次大（小）元素。凡要求在n个元素中选出k(k