9-1什么是内排序?什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的? 【解答】 9-2设待排序的关键码序列为{12,2,16,30,2810,16*,20,6,18},试分别写出使用以下排序 方法每趟排序后的结果。并说明做了多少次关键码比较。 1)直接插入排序 (2)希尔排序(增量为5,2,1)(3)起泡排序 (4)快速排序 (5)直接选择排序 (6)锦标赛排序 (7)堆排序 (8)二路归并排序 (9)基数排序 【解答】 9-3在起泡排序过程中,什么情况下关键码会朝向与排序相反的方向移动,试举例说明。在 快速排序过程中有这种现象吗? 【解答】 如果在待排序序列的后面的若干关键码比前面的关键码小,则在起泡排序的过程中,关 键码可能向与最终它应移向的位置相反的方向移动。例如, 队40、3361%7如9向相反方向移动 如19向相反方向移动 919如9向最终方向移动 679574038111334 19如13向相反方向移动 67915740381319344875如13向最终方向移动 67911135740、3819344875如34向相反方向移动 679111319 4038344875 679111319345740384875 679 9-4试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把关键码最大的对象放 到序列的最后,第二趟把关键码最小的对象放到序列的最前面。如此反复进行。 【解答】 ∥奇数趟对表 Vector从前向后,比较相邻的关键码,遇到逆序即交换,直到把参加比较关键码序犭 ∥中最大的关键码移到序列尾部。偶数趟从后向前,比较相邻的关键码,遇到逆序即交换,直到把 ∥参加比较关键码序列中最小的关键码移到序列前端。 while(i<CurrentS)( ∥起泡排序趟数不超过n-1 ∥假定元素未交换 for(j=CurrentSie-i;j>=i;j--) ∥逆向起泡 if( Vector[-1>ector)4 ∥发生逆序 Swap( Vector[-1], vector U]); ∥交换,最小关键码放在ecor{i处 ∥做“发生了交换”标志 if( exchange ==0)break; m当 exchange为0则停止排序 for(=i;j<=CurrentSie-i1: j++) ∥正向起泡 Swap( vector[ Vector[+1); ∥交换,最大关键码放在cor[n-处 ∥做“发生了交换”标志
9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】 9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序 方法每趟排序后的结果。并说明做了多少次关键码比较。 (1) 直接插入排序 (2) 希尔排序(增量为 5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】 9-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关 键码可能向与最终它应移向的位置相反的方向移动。例如， 57 40 38 11 13 34 48 75 6 19 9 7 如 9 向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如 19 向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如 9 向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如 13 向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如 13 向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如 34 向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75 6 7 9 11 13 19 34 9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放 到序列的最后，第二趟把关键码最小的对象放到序列的最前面。如此反复进行。 【解答】 template <class Type> void dataList<Type> :: shake_Sort ( ) { //奇数趟对表 Vector 从前向后, 比较相邻的关键码, 遇到逆序即交换, 直到把参加比较关键码序列 //中最大的关键码移到序列尾部。偶数趟从后向前, 比较相邻的关键码, 遇到逆序即交换, 直到把 //参加比较关键码序列中最小的关键码移到序列前端。 int i = 1, j; int exchange; while ( i < CurrentSize ) { //起泡排序趟数不超过 n-1 exchange = 0; //假定元素未交换 for ( j = CurrentSize-i; j >= i; j-- ) //逆向起泡 if ( Vector[j-1] > Vector[j] ) { //发生逆序 Swap ( Vector[j-1], Vector[j] ); //交换, 最小关键码放在 Vector[i-1]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; ////当 exchange 为 0 则停止排序 for ( j = i; j <= CurrentSize-i-1; j++ ) //正向起泡 if ( Vector[j] > Vector[j+1] ) { //发生逆序 Swap ( Vector[j], Vector[j+1] ); //交换, 最大关键码放在 Vector[n-i]处 exchange = 1; //做“发生了交换”标志 }
if( exchange ==0)break; m当 exchange为0则停止排序 ++ 9-5如果待排序的关键码序列已经按非递减次序有序排列,试证明函数 QuickSort()的计算时 间将下降到On2)。 9-6在实现快速排序的非递归算法时,可根据基准对象,将待排序关键码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序,试证明在此做法下,快速排序所需要的栈的 深度为Olog2n)。 9-7在实现快速排序算法时,可先检查位于两端及中点的关键码,取三者之中的数值不是最 大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法,并证明对于已 排序的关键码序列,该算法的计算时间为 O(nlog2n) 9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈?为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中,通过一趟划分,可以把一个待排序区间分 为两个子区间,然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时, 保存另一个子区间的上界和下界,待该区间处理完成后再从栈中取出另一子区间的边界,对 其进行处理。这个功能利用队列也可以实现,只不过是处理子区间的顺序有所变动而已 9-9试设计一个算法使得在O(n)的时间内重排数组将所有取负值的关键码排在所有取正 值(非负值)的关键码之前。 【解答】 9-10奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描,第二趟 对序列中的所有偶数项i扫描。若A[>A[计+1],则交换它们。第三趟有对所有的奇数项, 第四趟对所有的偶数项 如此反复,直到整个序列全部排好序为止 (1)这种排序方法结束的条件是什么? (2)写出奇偶交换排序的算法 ,(3)当待排序关键码序列的初始排列是从小到大有序,或从大到小有序时,在奇偶交换 序过程中的关键码比较次数是多少 【解答】 9-11请编写一个算法,在基于单链表表示的待排序关键码序列上进行简单选择排序 【解答】 9-12若参加锦标赛排序的关键码有11个,为了完成排序,至少需要多少次关键码比较? 【解答】 9-13试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数,对n个参加排序的对 象,构造胜者树。设n是2的幂。 【解答】 跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆
if ( exchange == 0 ) break; ////当 exchange 为 0 则停止排序 i++; } } 9-5 如果待排序的关键码序列已经按非递减次序有序排列，试证明函数 QuickSort( )的计算时 间将下降到 O(n 2 )。 9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序关键码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的 深度为 O(log2n)。 9-7 在实现快速排序算法时，可先检查位于两端及中点的关键码，取三者之中的数值不是最 大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已 排序的关键码序列，该算法的计算时间为 O(nlog2n)。 9-8 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分 为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时， 保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对 其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。 9-9 试设计一个算法, 使得在 O(n)的时间内重排数组, 将所有取负值的关键码排在所有取正 值(非负值)的关键码之前。 【解答】 9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项 i 扫描，第二趟 对序列中的所有偶数项 i 扫描。若 A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项， 第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。 (1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。 (3) 当待排序关键码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换 排序过程中的关键码比较次数是多少？ 【解答】 9-11 请编写一个算法，在基于单链表表示的待排序关键码序列上进行简单选择排序。 【解答】 9-12 若参加锦标赛排序的关键码有 11 个，为了完成排序，至少需要多少次关键码比较？ 【解答】 9-13 试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数，对 n 个参加排序的对 象，构造胜者树。设 n 是 2 的幂。 【解答】 9-14 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆
的变化 )按字母顺序排序:Tim,Dot,Eva,Rom,Kim,gug,Amn,Jm,Kay,Ron,Jam (2)按数值递增顺序排序:26,33,35,29,19,12,22 (3)同样7个数字,换一个初始排列,再按数值的递增顺序排序:12,19,3326,29,35, 【解答】 9-15如果只想在一个有n个元素的任意序列中得到其中最小的第k(k<<m)个元素之前的部 分排序序列,那么最好采用什么排序方法?为什么?例如有这样一个序列:{503,017,512 908,170,897,275,653,612154,509,612*,677,765,094},要得到其第4个元素之前的部分 有序序列:{017,094,154,170},用所选择的算法实现时,要执行多少次比较? 【解答】 一般来讲,当n比较大且要选的数据k<<n时,采用堆排序方法中的筛选(调整)算法最 好。但当n比较小时,采用锦标赛排序方法更好。 例如,对于序列{57,40,38,11,13,34,4875,6,19,9,7},选最小的数据6,需形成初 始堆,进行18次数据比较:选次小数据7时,需进行4次数据比较:再选数据9时,需进 行6次数据比较;选数据11时,需进行4次数据比较 38 11133448形成初始堆 7540195738 但如果选用锦标赛排序,对于有n个数据的序列,选最小数据需进行n-1次数据比较 以后每选一个数据,进行数据比较的次数,均需Log2n次。例如,同样12个数据,第 次选最小的数据6,需进行次数据比较,以后选7、9、11时,都是Log212」=3次数据 比较。 9-16希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。 【解答】 (1)希尔排序{512275275*061}增量为2 275*061512275}增量为1 {061275*275512} (2)直接选择排序{275275*512061}i=1 061275*512275}i=2 061275*512275}i=3 {061275*275512} (3)快速排序{512275275*} 275*275512} (4)堆排序 275275*061170}已经是最大堆,交换275与170 5}对前3个调整 275*170061275}前3个最大堆,交换275*与06 061170275*275}对前2个调整 170061275*275}前2个最大堆,交换170与061
的变化。 (1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22 (3) 同样 7 个数字，换一个初始排列，再按数值的递增 顺序排序：12, 19, 33, 26, 29, 35, 22 【解答】 9-15 如果只想在一个有 n 个元素的任意序列中得到其中最小的第 k (k<<n) 个元素之前的部 分排序序列, 那么最好采用什么排序方法? 为什么? 例如有这样一个序列: {503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612*, 677, 765, 094}, 要得到其第 4 个元素之前的部分 有序序列: {017, 094, 154, 170}, 用所选择的算法实现时, 要执行多少次比较? 【解答】 一般来讲，当 n 比较大且要选的数据 k << n 时, 采用堆排序方法中的筛选(调整)算法最 好。但当 n 比较小时，采用锦标赛排序方法更好。 例如，对于序列{ 57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7 }，选最小的数据 6，需形成初 始堆，进行 18 次数据比较；选次小数据 7 时，需进行 4 次数据比较；再选数据 9 时，需进 行 6 次数据比较；选数据 11 时，需进行 4 次数据比较。 但如果选用锦标赛排序，对于有 n 个数据的序列，选最小数据需进行 n -1 次数据比较， 以后每选一个数据，进行数据比较的次数，均需 log2n 次。例如，同样 12 个数据，第一 次选最小的数据 6，需进行 11 次数据比较，以后选 7、9、11 时，都是 log212 = 3 次数据 比较。 9-16 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。 【解答】 (1) 希尔排序 { 512 275 275* 061 } 增量为 2 { 275* 061 512 275 } 增量为 1 { 061 275* 275 512 } (2) 直接选择排序 { 275 275* 512 061 } i = 1 { 061 275* 512 275 } i = 2 { 061 275* 512 275 } i = 3 { 061 275* 275 512 } (3) 快速排序 { 512 275 275* } { 275* 275 512 } (4) 堆排序 { 275 275* 061 170 } 已经是最大堆，交换 275 与 170 { 170 275* 061 275 } 对前 3 个调整 { 275* 170 061 275 } 前 3 个最大堆，交换 275*与 061 { 061 170 275* 275 } 对前 2 个调整 { 170 061 275* 275 } 前 2 个最大堆，交换 170 与 061 { 061 170 275* 275 }
9-17设有n个待排序元素存放在一个不带表头结点的单链表中,每个链表结点只存放一个 元素,头指针为r。试设计一个算法,对其进行二路归并排序,要求不移动结点中的元素,只 改各链结点中的指针,排序后r仍指示结果链表的第一个结点。(提示:先对待排序的单链表 进行一次扫描,将它划分为若干有序的子链表其表头指针存放在一个指针队列中。当队列 不空时重复执行,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头 指针存放到队列中。如果队列中退出一个有序子链表后变成空队列,则算法结束。这个有序 子链表即为所求。) 【解答】 (1)两路归并算法 procedure merge( ha, hb: pointer; var hc: pointer ) var pa, pb, pc: pointer; if hat data<=hb↑data then begin hc =ha; pa: =hat next; pb: =hb; end else begin he: =hb; pb: =hbt. next; pa =ha; end; pc:=hc; while(pa nil )and( pb o nil)do then be pct next: =pa; pc: =pa; pa =pat. next; pct, next: =pb; pc =pb; pb: =pbt.next if pa o nil then pcf. next (2)归并排序主程序 pointer ) vars, t: pointer; var Q: Queue ifr=nil then return: SetEmpty (0); S =r; Enqueue( @,r); while s< nil do begin t:=s↑next while(to nil)and(st. data<=tf. data)do begin s t' =tf ifto nil then T; EnQueue( @, s ); end while not IsEmpty( o)d if IsEmpty( @) then break DEQueue( 0);
9-17 设有 n 个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个 元素, 头指针为 r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只 改各链结点中的指针, 排序后 r 仍指示结果链表的第一个结点。（提示：先对待排序的单链表 进行一次扫描, 将它划分为若干有序的子链表, 其表头指针存放在一个指针队列中。当队列 不空时重复执行, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头 指针存放到队列中。如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序 子链表即为所求。) 【解答】 (1) 两路归并算法 procedure merge ( ha, hb : pointer; var hc : pointer ); var pa, pb, pc : pointer; begin if ha↑ .data <= hb↑ .data then begin hc := ha; pa := ha↑ .next; pb := hb; end else begin hc := hb; pb := hb↑ .next; pa := ha; end; pc := hc; while ( pa <> nil ) and ( pb <> nil ) do if pa↑ .data <= pb↑ .data then begin pc↑ .next := pa; pc := pa; pa := pa↑ .next; end else begin pc↑ .next := pb; pc := pb; pb := pb↑ .next; end; if pa <> nil then pc↑ .next := pa else pc↑ .next := pb; end; (2) 归并排序主程序 procedure mergesort( var r : pointer ); var s, t : pointer; var Q : Queue; begin if r = nil then return; SetEmpty ( Q ); s:= r; Enqueue( Q, r); while s <> nil do begin t := s↑ .next; while ( t <> nil ) and ( s↑ .data <= t↑ .data ) do begin s:= t; t := t↑ .next; end; if t <> nil then begin s↑ .next := nil; s:= t; EnQueue( Q, s); end; end; while not IsEmpty( Q ) do begin r := DlQueue( Q ); if IsEmpty( Q ) then break; s := DlQueue( Q );
merge( r, S, 1); EnQueue( 0, 1); end end; 9-18若设待排序关键码序列有n个关键码,n是一个完全平方数。将它们划分为块,每 块有个关键码。这些块分属于两个有序表。下面给出一种O(1)空间的非递归归并算法 stepl:在两个待归并的有序表中从右向左总共选出个具有最大值的关键码 step2:若设在 stepl选出的第2个有序表中的关键码有s个,则从第1个有序表选出的 关键码有-s个。将第2个有序表选出的s个关键码与第1个有序表选出的关键码左边的 同样数目的关键码对调 step3:交换具有最大√个关键码的块与最左块(除非最左块就是具有最大√个关键码 的块)。对最右块进行排序 step4:除去具有最大n个关键码的块以外,对其它的块根据其最后的关键码按非递减 顺序排序 step5:设置3个指针,分别位于第1块、第2块和第3块的起始位置,执行多次 substep, 直到3个指针都走到第块为止。此时前-1块已经排好序。 subStep所做的工作是比较第2个指针与第3个指针所指关键码,将值小的与第 1个指针所指关键码对调,相应指针前进1个关键码位置 step6:对最后第G块中最大的√个关键码进行排序 (1)设有16个关键码,分别存放于两个有序表{10,12,14,16,18,20,2,25}和11,13,15 17,19,21,23,24}中,试根据上面的描述,写出排序的全过程,并说明它具有时间复杂度On) 和空间复杂度O(1) (2)编写相应的算法。要求两个待排序有序表的长度可以不同,但每一个表的长度都是 √n的倍数。 (3)假设两个有序表分别为(x,…;xm)和(xm+1,…;x),编写一个算法归并这两个有序 表,得到(x1,…,xn)。设S=n 9-19试编写一个算法,将对象序列(x,x2…,x)循环右移p个位置,0≤p≤no要求该算法 的时间复杂度为On)而空间复杂度为O(1)。 【解答】 9-20在什么条件下,MSD基数排序比LSD基数排序效率更高? 【解答】 9-21在已排好序的序列中,一个对象所处的位置取决于具有更小关键码的对象的个数。基 于这个思想,可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域 count, 用于存放在已排好序的序列中该对象前面的对象数目,最后依com域的值,将序列重新排 列,就可完成排序。试编写一个算法,实现计数排序。并说明对于一个有n个对象的序列, 为确定所有对象的 count值,最多需要做mn-1)/2次关键码比较。 【解答】 3661428← 待排序的表 始状态 第1趟排序结果 第2趟排序结果 第3趟排序结果
merge( r, s, t ); EnQueue( Q, t ); end end; 9-18 若设待排序关键码序列有 n 个关键码，n 是一个完全平方数。将它们划分为 n 块，每 块有 n 个关键码。这些块分属于两个有序表。下面给出一种 O(1)空间的非递归归并算法： step1: 在两个待归并的有序表中从右向左总共选出 n 个具有最大值的关键码； step2: 若设在 step1 选出的第 2 个有序表中的关键码有 s 个，则从第 1 个有序表选出的 关键码有 n - s 个。将第 2 个有序表选出的 s 个关键码与第 1 个有序表选出的关键码左边的 同样数目的关键码对调； step3: 交换具有最大 n 个关键码的块与最左块(除非最左块就是具有最大 n 个关键码 的块)。对最右块进行排序； step4: 除去具有最大 n 个关键码的块以外，对其它的块根据其最后的关键码按非递减 顺序排序； step5: 设置 3 个指针，分别位于第 1 块、第 2 块和第 3 块的起始位置，执行多次 substep， 直到 3 个指针都走到第 n 块为止。此时前 n −1 块已经排好序。 subStep 所做的工作是比较第 2 个指针与第 3 个指针所指关键码，将值小的与第 1 个指针所指关键码对调，相应指针前进 1 个关键码位置。 step6: 对最后第 n 块中最大的 n 个关键码进行排序。 (1) 设有 16 个关键码，分别存放于两个有序表{10, 12, 14, 16, 18, 20, 22, 25}和{11, 13, 15, 17, 19, 21, 23, 24}中，试根据上面的描述，写出排序的全过程，并说明它具有时间复杂度 O(n) 和空间复杂度 O(1)。 (2) 编写相应的算法。要求两个待排序有序表的长度可以不同，但每一个表的长度都是 n 的倍数。 (3) 假设两个有序表分别为(x1, …, xm)和(xm+1, …, xn)，编写一个算法归并这两个有序 表，得到(x1, …, xn)。设 s = n 。 9-19 试编写一个算法，将对象序列(x1, x2, …, xn)循环右移 p 个位置，0 p n。要求该算法 的时间复杂度为 O(n)而空间复杂度为 O(1)。 【解答】 9-20 在什么条件下，MSD 基数排序比 LSD 基数排序效率更高？ 【解答】 9-21 在已排好序的序列中，一个对象所处的位置取决于具有更小关键码的对象的个数。基 于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域 count， 用于存放在已排好序的序列中该对象前面的对象数目，最后依 count 域的值，将序列重新排 列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有 n 个对象的序列， 为确定所有对象的 count 值，最多需要做 n(n-1)/2 次关键码比较。 【解答】 0 0 0 0 初始状态 2 1 0 0 第 1 趟排序结果 3 0 0 第 2 趟排序结果 0 1 第 3 趟排序结果 35 66 14 28 14 28 35 66 待排序的表