第10章 排序

第十章 排序 一、单项选择题

1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。

A. (24 28 36) 48 (52 68 75 99) B. (28 36 24) 48 (75 99 68 52) C. (36 68 99) 48 (75 24 28 52) D. (28 36 24) 48 (99 75 68 52)

2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。 A. 希尔排序 B. 二分插入排序 C. 合并排序 D. 冒泡排序

3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。 A. 快速排序是稳定的排序方法 B. 堆排序是不稳定的排序方法 C. 希尔排序是稳定的排序方法 D. 冒泡排序是不稳定的排序方法 4. 下列排序方法中，____方法是不稳定的。

A. 冒泡排序 B. 希尔排序 C. 冒泡排序 D. 直接插入排序

5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。 A.快速排序 B. 希尔排序 C. 冒泡排序 D. 堆排序 6. 快速排序方法在最好情况下的时间复杂度为______。

A. O(n) B. O(n2) C. O(nlog2n) D.(log2n)

7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。 A. 堆排序 B.冒泡排序 C. 直接选择排序 D. 快速排序

8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。

A. 快速排序 B.插入排序 C. 冒泡排序 D. 堆排序

9. 在表R中排序前已按键值递增顺序排序，则_____方法的比较次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 选择排序 10. 已知表A中每个元素距其最终位置不远，采用______方法最节省时间。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序 11. 在下列排序方法中，字比较的次数与记录的初始排列次序无关的是______。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 12. 快速排序方法在_____情况下最不利于发挥其长处。

A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数

13. 一组记录的关键字经一趟二路归并排序后得到含有５个长度为２的有序表：[25,48],[16,35],[79,82], [23,40],[36,72]，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为______。

A. 16,25,35,48,23,40,79,82,36,72 B. 16,25,35,48,79,82,23,36,40,72 C. 16,25,48,35,79,82,23,36,40,72 D. 16,25,35,48,79,23,36,40,72,82

14. 一组记录的关键码为(46,74,18,53,14,20,40,38,86,65)，利用堆排序的方法建立的初始堆为____。

A. (14,18,38,46,65,40,20,53,86,74) B. (14,38,18,46,65,20,40,53,86,74) C. (14,18,20,38,40,46,53,65,74,86)

D. (14,86,20,38,40,46,53,65,74,18) 单项选择题参考答案

1. B 2. C 3. B 4. B 5. A 6. C 7. C 8. B 9. A 10. B 11. D 12. C 13. A 14. B 二、多项选择题

1. 高度为h 的堆中，最多有______个元素，最少有____个元素，最小的元素可能在_____位置。

A. 2h-1 B. 2h-1 C. 双亲结点 D. 叶子结点

2. 对于有n个元素的的数据进行排序，直接插入排序方法是从_____个元素开始，插入到前边适当位置的排序方法。快速排序方法首先将第_____个元素移动到排序后的位置上。 A. 1 B. 2 C. n-1 D. n

3. 对于有n个元素的数据进行排序，直接选择排序方法首先将选择的元素放在第____个元素的位置上；堆排序首先从堆的根选择出最大（或最小）的元素移到位置____; 归并排序方法首先将n个元素分成______组，再进行两两归并。 A. 1 B. 2 C. n-1 D. n 4. 以下排序法中，辅助空间为O(1)的有_______、_______.

A. 冒泡排序 B. 快速排序 C. 堆排序 D. 归并排序 5. 若数据元素的个数n较小，应采用____和______排序方法。

A. 直接插入排序 B. 堆排序 C. 直接选择排序 D. 归并排序 6. 若数据元素个数n较大，应采用______和______排序方法。

A. 直接插入排序 B. 堆排序 C. 直接选择排序 D. 归并排序 多项选择题参考答案：

1.A B D 2. B A 3. A D D 4. A C 5. A C 6. B D 三、填空题

1. 在直接插入和直接选择排序中，若初始数据基本有序，则选用____，若初始数据基本反序，则选用_____。

解：直接插入排序 直接选择排序

2. 在对一组记录(50,40,95,20,15,70,60,45,80)进行直接选择排序时，第４次交换和选择后，未排序记录（即无序表）为_______。 解：(50,70,60,95,80)

3. 在对一组记录(50, 40,95,20,15,70,60,45,80)进行堆排序时，根据初始记录构成初始堆后，最后４条记录为)________。 解：(50,60,40,20)

４. 在对一组记录(50, 40,95,20,15,70,60,45,80)进行冒泡排序时，第一趟需进行相信记录的交换的次数为_______，在整个排序过程中共需进行_______趟才可完成。 解：６ ７ 四、简答题

1.当R[low..high]中的关键字均相同时，Partition返回的值是什么？此时快速排序的运行时间是多少？能否修改Partition，使得划分结果是平衡的（即划分后左、右子区间的长度大致相等地）？

解：当R[low..high]中的关键字均相同时，Partition返回的值是low。此时快速排序的运行时间是O(n2).不能修改Partition，以使划分结果是平衡的。

2. 若文件初态是反序的，则直接插入、直接选择和冒泡排序哪一个更好？

解：若文件初态是反序的，则直接选择排序更好。因为反序时冒泡排序的比较和交换次数最

多，而直接插入和直接选择排序的比较次数差不多，但直接插入时无素的移动次数较多。 ３．若文件初态是反序的，且要求排序稳定，则在直接插入、直接选择、冒泡和快速排序中应选哪种方法？

解：若文件初态是反序的，且排序是稳定的，则以上几种排序方法中直接插入排序更好，因为当文件刘反序时，快速排序和冒泡排序都处于最坏的情况，其时间复杂度为O(n2),且排序不是稳定的；虽然直接选择排序的交换次数较少，但它不稳定，所以直接插入排序更好。 ４. 有序数组是堆吗？

解：有序数组满足堆的定义，所以有序数组是堆。

5. 高度为h的堆中，最多有多少个元素？最少有多少个元素？在大根堆中，关键字最小的元素可能存放在堆的哪些地方？

解：高度为h的堆中，最多有2h-1个元素（为满二叉树），最少有２h-1个元素。在大根堆中，关键字最小的元素可能存放在堆的最下层或次下层。 6. 判别下列序列是否为堆（小根堆或大根堆），若不是，则将其调整为堆： (1) 100 86 48 76 33 39 42 57 66 21 (2) 12 70 33 65 24 56 48 92 86 33

(3) 103 97 56 38 66 23 42 12 30 52 06 20 (4) 5 56 20 23 40 38 29 61 35 76 28 100 解：(1) (3)是大根堆， (2) (3)不是堆

(2) 调整为小根堆：12 24 33 65 33 56 48 92 86 70

(3) 调整为小根堆：5 23 20 35 28 38 29 61 56 76 40 100 7. 将两个长度为n的有序表归并为一个长度为２n的有序表，最少需比较n次，最多需比较2n-1，请说明这两种情况发生时，两个被归并的表有何特征？

解：若将两个长度为n的有序表归并为一个长度为２n的有序表需比较n次，则两个被归并的表应满足：其中一个表的所有元素均小于（或大于）另一个表中的任意元素，若将两个长度为n的有序表归并为一个长度为２n的有序表需比较2n-1次，则两个被归并的表应满足：其中一个表的所有元素不得均小于（或大于）另一个表中的两个或两个以上的元素。

8. 针对关键字是非负整数，快速排序、归并排序、堆排序和基数排序哪一个排序最快？若要求辅助空间为O(1)，则应选谁？若要求排序是稳定的，且关键字为实数，则应选谁？ 解：若关键字是非负整数，一般情况下在快速排序、归并排序、堆排序和基数排序中快速排序最快。若要求辅助空间为o(1)，则应选堆排序，若要求排序是稳定的，且关键字为实数，则应选择归并排序。 四、算法设计题

1. 将哨兵在R[n]中，被排序的记录放在R[0..n-1]中，编写直接插入排序算法。 解：直接插入排序算法如下： void InsertSort (SegList R) {

int i, j;

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

if (R[i].key

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

} while （R[n].key -1）;

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

} }

2. 以单链表作为存储结构实现直接插入排序算法。

解：先用*head和第一个结点构成一个有序表，用p镄针扫描余下的结点，将*p的key域值与有序表中的结点进行比较，找到合适的位置，将*p插入在*prev和*q之间。算法如下：

typedef strruct node { HeyType key; struct node *next; } Lnode;

void InsertList (Lnode *&head) {

Lnode *p, *q, *prev, *temp; if (head->next==NULL) return; p=head->next;

if (p->next==NULL) RETURN;

head->next->next=NULL; p=p->next;

while (p!=NULL) { q=head->next; pre=head;

while (q1=NULL &&Q->KEYKEY) { prev=q; q=q->next; }

temp=p->next; p->next=q; prev->next=p; p=temp; } }

3. 下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange来记录每趟扫描中进行交换有最后一个元素的位置，冯以它作为下一趟排序循环终止的控制值。请依照它写一个自下往上扫描的冒泡排序算法。

void BubbleSort9int a[], int n) {

int lastexchange , j, i=n-1; while (i>0){

lastExchange=0; for (j=0; i

交换A[j]和A[j+1];

lastExchange=j; }

i=lastExchange; }

}

解：自下往上扫描的冒泡排序算法如下： void Bubblesort(int A[], int n) {

int lastExchange, j, i=n-1, temp; while(i>0) {

lastExchange=0; for (i=n-1;j>i; j--)

if (A[j]

temp=A[j]; A[j]=A[j-1]; A[j-1]=temp; lastExchange=j; }

i=lastExchange; } }

4. 设向量A[0..n-1]中存有n个互不相同的整数，且每个元素的值均在０到n-1之间。试写一埋单复杂度为O(n)的算法将向量A排序，结果可输出到另一个向量b[0..n-1]。

解：算法如下：

void Sort (int A[], int B[], int n ) {

int i;

for (i=0;i

B[i]=0;

for (i-0; i

B[A[i]]=A[i];

}