算法与数据结构 C语言版 第二版 (陈守孔 孟佳娜 武秀川 著) 机械工业出版社 课后答案 第10章 排序

课后答案网 10 章 排序 一、 基础知识题 本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最佳归并树。 【解答】内排序和外排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为 内部排序 ；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为 外部排序 。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 稳定排序和不稳定排序 假 设待排序记录中有关键字 j（ i j），且在排序前的序列中 先于 过排序后， 相对次序保持不变（即领先于 则称这种排序方法是 稳定的 ，否则称之为 不稳定的 。 顺串 外部排序通 常 经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成 有序段， 这有序段又称 顺串 或 归并段 。 败者树 败者树为提高外部排序的效率而采用的，是由参加比赛的 个非叶（双亲）结点中存放的是两个子 结点中的败者数据 ,而让胜者去参加更高一级的比赛。另外 ,还需增加一个结点 ,即结点 0,存放比赛的全局获胜者。 最佳归并树 在外部排序的多路平衡归并的 了提高效率减少对外存的读写次数，按哈夫曼树构造的 k 叉树称 最佳归并树。这棵树中只有度为0和度为 用 m 表示 归并段个数，用 示度为 k 的个数，若(0，则不需增加虚段，否则应附加 k-(1 个虚段（即第一个 k 路归并使用 (1 个归并段）。 待排序的关键字序列为 (15， 21， 6， 30， 23， 6， 20， 17)， 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。(1) 直接插入排序 (2) 希尔排序 (增量为 5， 2， 1) (3) 起泡排序(4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序(7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】 (1) 直接插入排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟直接插入排序：【 15， 21】 第二趟直接 插入排序：【 6， 15， 21】 第三趟直接插入排序：【 6， 15， 21， 30】 第四趟直接插入排序：【 6， 15， 21， 23， 30】 第五趟直接插入排序：【 6， 6， 15， 21， 23， 30】 第六趟直接插入排序：【 6， 6， 15， 20， 21， 23， 30】 课后答案网 七趟直接插入排序：【 6， 6， 15， 17， 20， 21， 23， 30】 (2) 希尔排序 (增量为 5， 2， 1) 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟希尔排序： 6， 20， 6， 30， 23， 15， 21， 17 第二 趟希尔排序： 6， 15， 6， 17， 21， 20， 23， 30 第三趟希尔排序： 6， 6， 15， 17， 20， 21， 23， 30 (3) 起泡排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟起泡排序： 15， 6， 21， 23， 6， 20， 17， 30 第二趟起泡排序： 6， 15， 21， 6， 20， 17， 23， 30 第三趟起泡排序： 6， 15， 6， 20， 17， 21， 23， 30 第四趟起泡排序： 6， 6， 15， 17， 20， 21， 30， 23 第五趟起泡排序： 6， 6， 15， 17， 20， 21， 30， 23 (4) 快速排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟快速排序： 【 6， 6】 15【 30， 23， 21， 20， 17】 第二趟快速排序： 6， 6， 15【 17， 23， 21， 20】 30 第三趟快速排序： 6， 6， 15， 17【 23， 21， 20】 30 第四趟快速排序： 6， 6， 15， 17，【 20， 21】 23， 30 第五趟快速排序： 6， 6， 15， 17， 20， 21， 30， 23 (5) 直接选择排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 第一趟直接选择排序： 6， 21， 15， 30， 23， 6， 20， 17 第二趟直接选择排序： 6， 6， 15， 30， 23， 21， 20， 17 第三趟直接选择排序： 6， 6， 15， 30， 23， 21， 20， 17 第四趟直接选择排序： 6， 6， 15， 17， 23， 21， 20， 30 第五趟直接选择排序： 6， 6， 15， 17， 20， 21， 23， 30 第六趟直接选择排序： 6， 6， 15， 17， 20， 21， 23， 30 第七趟直接选择排序： 6， 6， 15， 17， 20， 21， 23， 30 (6) 锦标赛排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 6 6 6 15 6 6 17 15 21 6 课后答案网 0 23 6 20 17 6 15 6 15 30 6 17 15 21 30 23 6 20 17 课后答案网 5 15 23 15 30 23 17 15 21 30 23 20 17 锦标赛排序 的基本思想是：首先对 中选出 n/2 个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将（冠军）叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止， 如此循环直到输出全部有序序列。上面给出了排在前三个的记录，详细过程略。 (7) 堆排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 初始堆： 6， 17， 6， 21， 23， 15， 20， 30 课后答案网 一次调堆： 6， 17， 15， 21， 23， 30， 20，【 6】 第二次调堆： 15， 17， 20， 21， 23， 30，【 6， 6】 第三次调堆： 17， 21， 20， 30， 23，【 15， 6， 6】 第四次调堆： 20， 21， 23， 30，【 17， 15， 6， 6】 第五次调堆： 21， 30， 23，【 20， 17， 15， 6， 6】 第六次调堆： 23， 30，【 21， 20， 17， 15， 6， 6】 第七次调堆： 30，【 23， 21， 20， 17， 15， 6， 6】 堆排序结果 调堆：【 30， 23， 21， 20， 17， 15， 6， 6】 (8) 二路归并排序 初始关键字序列： 15， 21， 6， 30， 23， 6， 20， 17 二路归并排序结果 ： 15， 17， 20， 21， 23， 30， 6， 6 9) 基数排序 初始关键字序列： p 15 21 6 30 23 6 20 17 第一次分配得到 : B030 20 B0121 B1323 B3515 B566 6 B6717 B7一次收集得到 : p 30 20 21 23 15 6 6 17 第二次分配得到 B06 6 B0115 17 B1220 21 23 B5330 B3二次收集得到 p 6 6 15 17 20 21 23 30 基数排序结果 ： 6， 6， 15， 17， 20， 21， 23， 30 各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。 【解答】见下表： 排序方法 平均时间 最坏情况 辅助空间 稳定性 不稳定排序举例 直接插入排序 O(O(O(1) 稳定 折半插入排序 O(O(O(1) 稳定 二路插入排序 O(O(O(n) 稳定 表插入排序 O(O(O(1) 稳定 起泡排序 O(O(O(1) 稳定 课后答案网 接选择排序 O(O(O(1) 不稳定 2,2 ,1 希尔排序 O(O(O(1) 不稳定 3,2,2 ,1(d=2,d=1) 快速排序 O(O(O(不稳定 2,2 ,1 堆排序 O(O(O(1) 不稳定 2,1,1 (极大堆 ) 2O(O(O(n) 稳定 基数排序 O(d*(rd+n) O(d*(rd+n) O ( 稳定 执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 【解答】 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对 4， 3， 2， 1起泡排序就可否定本题结 论。 堆排序、快速排序和归并排序方法中： (1)若只从存储空间考虑，则应首先选取哪种排序，其次选取哪种排序，最后选取哪种排序？ (2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 【解答】 (1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序 设要求从大到小排序。问在什么情况下冒泡排 序算法关键字交换的次数为最多。 【解答】 对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序时 关键字交换的次数为最多。 速排序的最大递归深度是多少？最小递归深度是多少？ 【解答】 设待排序记录的个数为 n,则快速排序的最小递归深度为 1,最大递归深度 n。 们知道，对于 n 个元素组成的顺序表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问： (1) 当 n=7 时，在最好情况下需进行多少次比较？请说明理由。 (2) 当 n=7 时，给出一个最好情况的初始排序的实例。 (3) 当 n=7 时，在最坏情况下需进行多少次比较？请说明理由。 (4) 当 n=7 时，给出一个最坏情况的初始排序的实例。 【解答】 课后答案网 1) 在最好情况下 ,每次划分能得到两个长度相等的子文件。假设文件的长度n=2么第一遍划分得到两个长度均为 n/2 的子文件 ,第二遍划分得到 4 个长度均为 n/4的子文件 ,以此类推 ,总共进行 k=n+1)遍划分 ,各子文件的长度均为 1,排序完毕。当 n=7 时 ,k=3,在最好情况下 ,第一遍需比较 6次 ,第二遍分别对两个子文件（长度 均为 3,k=2）进行排序 ,各需 2 次 ,共 10 次即可。 (2) 在最好情况下快速排序的原始序列实例 ： 4,1,3,2,6,5,7。 (3) 在最坏情况下 ,若每次用来 划分的记录的关键字具有最大 (或最小 )值 ,那么只能得到左 (或右 )子文件 ,其长度比原长度少 1。因此 ,若原文件中的记录按关键字递减次序排列 ,而要求排序后按递增次序排列时 ,快速排序的效率与冒泡排序相同 ,其时间复杂度为 O(所以当 n=7 时 ,最坏情况下的比较次数为 21次。 (4) 在最坏情况下快速排序的初始序列实例 ： 7,6,5,4,3,2,1,要求按递增排序。 断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。 (1) 100， 90， 80， 60， 85， 75， 20， 25， 10， 70， 65， 50 (2) 100， 70， 50， 20， 90， 75， 60， 25， 10， 85， 65， 80 【解答】 (1) 是堆 (2) 不是堆。 调成大堆： 100,90,80,25,85,75,60,20,10,70,65,50 在多关键字排序时， 种方法的特点是什么？ 【解答】 最高位优先 （ ：先对最高位关键字 将序列分成若干子序列 ,每个子序列中的记录都具有相同的 然后 ,分别就每个子序列对关键字按 ,依次重复 ,直至最后对最低位关键字排序完成 ,将所有子序列依次连接在一起 ,成为一个有序子序列。 最低位优先（ ：先对最低位关键字 然后对高一级关键字 依次重复 ,直至对最高位关键字 行排序时 ,不必分成子序列 ,对每个关键字都是整个序列参加排序 ,但对 0Ai+1，则将两者交换；第二趟对所有偶数 i(2Ai+1，则将两者交换；第三趟对所有奇数 i(1 p) 课后答案网 q=p- r=p; 设 r 是指向关键字最小的结点的指针 q!=if(q-r=q; q=q- r!=p) r-p=p- 设单链表头结点指针为 L，结点数据为整型。试写出对链表 L 按“直接插入方法”排序的算法。 ) /本算法对单 链表 接插入方法”进行排序 p=L- /链表至少一个结点 ,p 初始指向链表中第二结点（若存在） L-(p!= q=p- /q 指向 p 的后继结点 s=L; s-& s-s=s- /向后找插入位置 p-s-s-p;/插入结点 p=q; /恢复 试设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。 a,n) 相邻两趟向相反方向起泡的冒泡排序算法 ; 冒泡的上下界 i+1)aiai+1; 有交换 ,修改标志 修改上界 i=i 气泡下沉 ,小元素上浮（向左） if(aia; 课后答案网 ; 修改下界 写出快速排序的非递归算法。 rn+1; n) 对 r1.行快速排序的非递归算法 sn+1；栈 ,容量足够大 r, 函数声明 ; s; sn; ) ss=stt=s if(s+s if() s+k+1; s 算法结束 r;s,t) i=s; j=t; rp=ri; x=ri i=rji+; if(k=r,ss, if( 一趟排序后分割成左右两部分 if() 左部子序列长度大于右部 ,左部进栈 课后答案网 s+s if() ss=k+1; 右部短的直接处理 右部处理完 ,需退栈 if() 右部子序列长度大于左部 ,右部进栈 s+k+1; s if() tt= 左部短的直接处理 左部处理完 ,需退栈 & ) 退栈 ss=stt=s of | ) 算法结束 r;s,t) 用“三者取中法” 进行快速排序的一次划分 i=s, j=t, s+t)/2; if(rirri;ri=rr if(rrjrj;rj=r if(ri) rrri;ri= ri;ri=rr 三者取中：最佳 2次比较 3 次赋值；最差 3次比较 10 次赋值 rp=ri; x=ri i=rji+; if(irj; i+;j+; if(rj=2) j+