第8章排序技術(shù)深度為（）。

【解答】3

課后習(xí)題講解

⑸對(duì)n個(gè)待排序記錄序列進(jìn)行快速排

1.填空題序，所需要的最好時(shí)間是（），最壞

⑴排序的主要目的是為了以后對(duì)已時(shí)間是（）。

排序的數(shù)據(jù)元素進(jìn)行（）?！窘獯稹縊（nlog2n）,O（n2）

【解答】查找

（6）利用簡(jiǎn)單選擇排序?qū)個(gè)記錄進(jìn)行

【分析】對(duì)已排序的記錄序列進(jìn)行查

排序，最壞情況下，記錄交換的次數(shù)

找一般能提高查找效率。

為（）。

⑵對(duì)n個(gè)元素進(jìn)行起泡排序，在（）

【解答】n~l

情況下比較的次數(shù)最少，其比較次數(shù)

為（）。在（）情況下比較次數(shù)最（7）如果要將序列（50,16,23,68,94,

多，其比較次數(shù)為（）。70,73）建成堆，只需把16與（）

【解答】正序,n-1,反序，n（n-l）/2交換。

⑶對(duì)一組記錄（54,38,96,23,15,【解答】50

72,60,45,83）進(jìn)行直接插入排序,

⑻對(duì)于鍵值序列（12,13,11,18,60,

當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，

15,7,18,25,100）,用篩選法建

為尋找插入位置需比較（）次。

堆，必須從鍵值為（）的結(jié)點(diǎn)開始。

【解答】3

【解答】60

【分析】當(dāng)把第7個(gè)記錄60插入到有

【分析】60是該鍵值序列對(duì)應(yīng)的完全

序表時(shí)，該有序表中有2個(gè)記錄大于

二叉樹中最后一個(gè)分支結(jié)點(diǎn)。

60o

（4）對(duì)一組記錄（54,38,96,23,15,2.選擇題

72,60,45,83）進(jìn)行快速排序,在

⑴下述排序方法中，比較次數(shù)與待

遞歸調(diào)用中使用的棧所能達(dá)到的最大

排序記錄的初始狀態(tài)無關(guān)的是（）。

A插入排序和快速排序B歸并排序和

快速排序【解答】B,C,B

C選擇排序和歸并排序D插入排序和【分析】待排序序列中每個(gè)元素距其

歸并排序最終位置不遠(yuǎn)意味著該序列基本有

【解答】C序。

【分析】選擇排序在最好、最壞、平

（4）堆的形狀是一棵（）°

均情況下的時(shí)間性能均為0（n2）,歸

A二叉排序樹B滿二叉樹C完全二叉

并排序在最好、最壞、平均情況下

樹D判定樹

的時(shí)間性能均為0（nlog2n）。

【解答】C

⑵下列序列中，（）是執(zhí)行第一趟【分析】從邏輯結(jié)構(gòu)的角度來看，堆

快速排序的結(jié)果。實(shí)際上是一種完全二叉樹的結(jié)構(gòu)。

A[da,ax,eb,de,bb]ff[ha,gc]

⑸當(dāng)待排序序列基本有序或個(gè)數(shù)較

B[cd,eb,ax,da]ff[ha,gc,bb]

小的情況下，最佳的內(nèi)部排序方法是

C[gc,ax,eb,cd,bb]ff[da,ha]

（）,就平均時(shí)間而言，（）最佳。

D[ax,bb,cd,da]ff[eb,gc,ha]

A直接插入排序B起泡排序C簡(jiǎn)單

【解答】A

選擇排序0快速排序

【分析】此題需要按字典序比較，前

【解答】A,D

半?yún)^(qū)間中的所有元素都應(yīng)小于ff,后

半?yún)^(qū)間中的所有元素都應(yīng)大于ffo⑹設(shè)有5000個(gè)元素，希望用最快的

速度挑選出前10個(gè)最大的，采用（）

⑶對(duì)初始狀態(tài)為遞增有序的序列進(jìn)

方法最好。

行排序，最省時(shí)間的是（），最費(fèi)時(shí)

A快速排序B堆排序C希爾排序D歸

間的是（）。己知待排序序列中每個(gè)

并排序

元素距其最終位置不遠(yuǎn)，則采用（）

【解答】B

方法最節(jié)省時(shí)間。

【分析】堆排序不必將整個(gè)序列排序

A堆排序B插入排序C快速排序D

即可確定前若干個(gè)最大（或最小）元

直接選擇排序

素。

⑺設(shè)要將序列（Q,H,C,Y,P,A,M,排序序列中挑選元素，并將其依次放

S,R,D,F,X）中的關(guān)鍵碼按升序排入己排序序列的一端。交換排序是對(duì)

列，則（）是起泡排序一趟掃描的序列中元素進(jìn)行一系列比較，當(dāng)被比

結(jié)果，（）是增量為4的希爾排序一較的兩元素為逆序時(shí)，進(jìn)行交換；（）

趟掃描的結(jié)果，（）二路歸并排序一和（）是基于這類方法的兩種排序

趟掃描的結(jié)果，（）是以第一個(gè)元素方法，而（）是比（）效率更高的

為軸值的快速排序一趟掃描的結(jié)果，方法；（）法是基于選擇排序的一種

（）是堆排序初始建堆的結(jié)果。方法，是完全二叉樹結(jié)構(gòu)的一個(gè)重要

A(F,H,C,D,P,A,M,Q,R,S,Y,應(yīng)用。

X)A選擇排序B快速排序C插入排序

B(P,A,C,S,Q,D,F,X,R,II,M,D起泡排序E歸并排序F堆排序

Y)【解答】C,A,D,B,B,D,F

C(A,D,C,R,F,Q,M,S,Y,P,H,

（9）快速排序在（）情況下最不利于

X)

發(fā)揮其長(zhǎng)處。

D(H,C,Q,P,A,M,S,R,D,F,X,

A待排序的數(shù)據(jù)量太大B待排序的

Y)

數(shù)據(jù)中含有多個(gè)相同值

E(H,Q,C,Y,A,P,M,S,D,R,F,

C待排序的數(shù)據(jù)已基本有序D待排

X)

序的數(shù)據(jù)數(shù)量為奇數(shù)

【解答】D,B,E,A,C

【解答】C

【分析】此題需要按字典序比較，而

【分析】快速排序等改進(jìn)的排序方法

且需要掌握各種排序方法的執(zhí)行過

均適用于待排序數(shù)據(jù)量較大的情況，

程。

各種排序方法對(duì)待排序的數(shù)據(jù)中是否

⑻排序的方法有很多種，（）法從含有多個(gè)相同值，待排序的數(shù)據(jù)數(shù)量

未排序序列中依次取出元素，與已排為奇數(shù)或偶數(shù)都沒有影響。

序序列中的元素作比較，將其放入已

排序序列的正確位置上。（）法從未

速脖；螂吊

麻麻125?20Hl為秘幽瞅也5HI24]

野通晃[55]12[2031M第T點(diǎn)[5912e18K31

磔熊[5：5W1220[31刈螳裸[5，5]112]3?

眩蛾56J12IDMB1Oil[5(]H22]M?：

據(jù)陳56"2?。N31京瞳要569口20X31

能隔；二融融郵

腌蚓S5"Q631到怫M到I?59863124

瞄就澈[31202456912]；圖8-5慚整的過程

內(nèi)解[512]Bm31]M

#硼[M1012569]31；

行蛾[551210][6143!]

丈嬲[X9n5AM31;7.己知下列各種初始狀態(tài)(長(zhǎng)度為n)

甯翎果[II565]2014?!豺燃(569122)2131]

賺翳[95C1220X31;的元素，試問當(dāng)利用直接插入排序進(jìn)

,潴疆[o￡51220%儲(chǔ)

新冠疆56?12J02431;

......................................J行排序時(shí)，至少需要進(jìn)行多少次匕較

(耍求排序后的記錄由小到大順序排

5.對(duì)n=7,給出快速排序一個(gè)最好情

列)?

況和最壞情況的初始排列的實(shí)例。

⑴關(guān)鍵碼從小到大有序(keyl<

【解答】最好情況：4,7,5,6,3,1,

key2<…<keyn)°

2

⑵關(guān)鍵碼從大到小有序(keyl>

最壞情況：7,6,5,4,3,2,1

key2>???>keyn)。

6.判別下列序列是否為堆，如不是，⑶奇數(shù)關(guān)鍵碼順序有序，偶數(shù)關(guān)鍵

按照堆排序思想把它調(diào)整為堆，用圖碼順序有序(keyl<key3<…,key2

表示建堆的過程。key4…)。br/>(4)前半部分元素按

(1)(1,5,7,25,21,8,8,42)關(guān)鍵碼順序有序，后半部分元素按關(guān)

出(3,9,5,8,4,17,21,6)鍵碼順序有序，即：

【解答】序列⑴是堆，序列⑵不是堆,(keyl<key2<…<keym,keym+l<

調(diào)整為堆(假設(shè)為大根堆)的過程如keym+2<…

圖8-5所示。

【解答】依題意，最好情況下的匕較

次數(shù)即為最少比較次數(shù)。

⑴插入第i(2WiWn)個(gè)元素的比較

次數(shù)為1,因此總的比較次數(shù)為：法。

1+1+...+l=n-l【解答】本算法采用的存儲(chǔ)結(jié)構(gòu)是帶

⑵插入第i(2WiWn)個(gè)元素的比較頭結(jié)點(diǎn)的單鏈表。首先找到元素的插

次數(shù)為i,因此總的比較次數(shù)為：入位置，然后把元素從鏈表中原位置

2+3+...+n=(n-l)(n+2)/2刪除，再插入到相應(yīng)的位置處。具體

⑶比較次數(shù)最少的情況是所有記錄算法如下：

關(guān)鍵碼按升序排列，總的比較次數(shù)為:

后入排序算法StraightSort[

n-1

voidStraightSort(intr[],intn)

(

⑷在后半部分元素的關(guān)鍵碼均大于for(i=2;i<=n,i++)

(

前半部分元素的關(guān)鍵碼時(shí)需要的比較⑩項(xiàng)；

low=l,high=4-l;flag=l;

次數(shù)最少，總的比較次數(shù)為：while(low<-high&&flag)

(

n-lmid=(low+high)/2;

if(r[0]<r[mid])high=tnid-l,

dseif(r[0]>r(mid])low=mid+l,

8.算法設(shè)計(jì)elseflag=0,

)

for(j=i-l,j>=mid;j-)

市+舊叱

⑴直接插入排序中尋找插入位置的r[mid]=r[0];

)

操作能夠經(jīng)過折半查找來實(shí)現(xiàn)。據(jù)此

寫一個(gè)改進(jìn)的插入排序的算法。

⑶設(shè)待排序的記錄序列用單鏈表作

【解答】插入排序的基本思想是：每

存儲(chǔ)結(jié)構(gòu)，試寫出簡(jiǎn)單選擇排序算

趟從無序區(qū)中取出一個(gè)元素，再按鍵

法。

值大小插入到有序區(qū)中。對(duì)于有序區(qū)，

【解答】參見&2.2。

當(dāng)然能夠采用折半查找來確定插入位

置。具體算法如下：⑷對(duì)給定的序號(hào)j(1<j<n),要求

在無序記錄中找到按關(guān)鍵

mosimage)

碼從小到大排在第j位上的記錄，試

⑵設(shè)待排序的記錄序列用單鏈表作利用快速排序的劃分思想設(shè)計(jì)算法實(shí)

存儲(chǔ)結(jié)構(gòu)，試寫出直接插入排序算現(xiàn)上述查找。

【解答】本算法不要求將整個(gè)記錄進(jìn)查找第J小算法Search[

intSearch(intr[],intn,intj)

行排序，而只進(jìn)行查找第j個(gè)記錄。(

s=l；t=n,

k=Devo(r,s,t);

插入排序算法■StraightSort___________________________while(k!=j)

voidStraightSort(Node*first)處lode話參見第二章單if(k<j)k^Devoak+1,t);

(elsek=Devo(r,s,k-1);

pre=first,p=first->next,q=p->next;return幣];

while(p)}

(intDevo(intr[],intlow,inthigh)

while(q!=p)(

(i=low;j=high,x=r[low],

while(p->data<c->data)while(i<j)

{,(

pre=p;while(r[j]>=x&&i<j)1一;

p=p->next,if(KJ)Mi]F]；i++；)

)while(r[i]<x&&i<j)i++;

if(p!=q)(

u=q->rext;pre->next=q;)

q->next=p;q=u;r[i]=x；

)returni;

dseq=q->next,)

)

pre=fir$t,pMirst->next,

)（6）一個(gè)線性表中的元素為正整數(shù)或

)

負(fù)整數(shù)。設(shè)計(jì)兌1去將正整數(shù)和負(fù)整數(shù)

（5）寫出快速排序的非遞歸調(diào)用算法。分開，使線性表的前一半為負(fù)整數(shù)，

【解答】先調(diào)用劃分函數(shù)后一半為正整數(shù)。不要求對(duì)這些元素

Quickpass（劃分函數(shù)同教材），以確排序，但要求盡量減少比較次數(shù)。

定中間位置，然后再借助棧分別對(duì)中【解答】本題的基本思想是：先設(shè)置

間元素的左、右兩邊的區(qū)域進(jìn)行快速好上、下界和軸值，然后分別從線性

排序。表兩端查找正數(shù)和負(fù)數(shù)，找到后進(jìn)行

交換，直到上下界相遇。算法如下：

快速排序非遞歸算法Quicksort|試寫出這一算法。

voidQuicksort(intr[],intn)

【解答】采用二路歸并升序中一次歸

top=-l;”采用順序極并假定不會(huì)發(fā)生溢出

low=l,high=n;并的思想，設(shè)三個(gè)參數(shù)、j和k分

while(low<high||top!=-l)

別指向兩個(gè)待歸并的有個(gè)序列和最終

while(low<high)

有序序列的當(dāng)前記錄，初始時(shí)i、

『Quickpass(r,low,high);

S[++top]=i;high=i-l;分別指向兩個(gè)有序序歹!的第一個(gè)記

)

if(top!=-l){

i=S[-top],錄，即i=l,j=l,k指|U存放歸并結(jié)

low=i+l;

)果的位置，即k=l。然巨，比較i和j

)

)所指記錄的關(guān)鍵碼，取;國較小者作為

歸并結(jié)果存入k所指位置，直至兩個(gè)

(7)已知(kl,k2,…，kn)是堆，試

有序序列之一的所有記錄都取完，再

寫一算法將(kl,k2,…，kn,kn+1)

將另一個(gè)有序序列的剩余記錄順序送

調(diào)整為堆。

到歸并后的有序序列中。

【解答】增加一個(gè)元素應(yīng)從葉子向根

方向調(diào)整，假設(shè)調(diào)整為小根堆。插入法建堆算法InsertHeap

voidInsertHeap(intr[],intk)例口]~雙為堆，將r[l]~r[k+l]調(diào)整為堆

Devotj

總負(fù)整數(shù)分開算法x=r[k+l];

i=k+l;

voidDevot(intr[],intn)

while(i/2>0&&r[i/2]>x)

(

i=Uj=n；

while(i<j)

i=i/2;

(

}

while(r[j]>0&&i<j)j一;

.F

while(r[i]<0&&i<j)i++,

)

if(i<j){

tfi]'*--"{j]；餃換元素

i++；

j-；6.用直接插入排疔對(duì)下面四個(gè)序列

J

}進(jìn)行由小到大排序，元素比車:次數(shù)最

)

A94,32,40,90,80,46,21,59B

⑻給定n個(gè)記錄的有序序列A[n]和m

21,32,46,40,80,69,90,94

個(gè)記錄的有序序列B[ni],將它們歸并

C32,40,21,46,69,94,90,30D

為一個(gè)有序序列，存放在C[m+n]中，

90,69,80,46,21,32,94,40排序序列時(shí)，堆排序的時(shí)間復(fù)雜度

【解答】B0（n+klog2n）,若kWnlog2n,則得

到的時(shí)間復(fù)雜性是。（n）。

7.對(duì)數(shù)列(25,84,21,47,15,27,

對(duì)于上述序列得到其前4個(gè)最小元素,

68,35,20）進(jìn)行排序,元素序列的

使用堆排序?qū)崿F(xiàn)時(shí)，執(zhí)行的比較次數(shù)

變化情況如下:

如下：

(1)25,84,21,47,15,27,68,35,

初始建堆：比較20次，得到6;

20(2)20,15,21,25,47,27,68,

第一次調(diào)整：比較5次，得到7;

35,84

第二次調(diào)整：比較4次，得到9;

(3)15,20,21,25,35,27,47,68,

第三次調(diào)整：比較5次，得到1L

84(4)15,20,21,25,27,35,47,

68,849.荷蘭國旗問題。要求重新排列一個(gè)

則采用的排序方法是（）。由字符R,W,B（R代表紅色，W代表

A希爾排序B簡(jiǎn)單選擇排序C快速白色，B代表蘭色，這都是荷蘭國旗的

排序D歸并排序顏色）構(gòu)成的數(shù)組，使得所有的R都

【解答】C排在最前面，W排在其次，B排在最后。

為荷蘭國旗問題設(shè)計(jì)一個(gè)算法，其時(shí)

8.如果只想得到一個(gè)序列中第k個(gè)最

間性能是0（n）。

小元素之前的部分排序序列，最好采

【解答】設(shè)立三個(gè)參數(shù)i、j、k,其

用什么排序方法？為什么？對(duì)于序列

中i以前的元素全部為紅色；j表示當(dāng)

{57,40,38,11,13,34,48,75,25,

前元素；k以后的元素全部為藍(lán)色。這

6,19,9,7）,得到其第4個(gè)最小元

樣，就能夠根據(jù)j的顏色，把其交換

素之前的部分序列{6,7,9,11},使用

到序列的前部或后部。

所選擇的排序算法時(shí)，要執(zhí)行多少次

比較？

【解答】采用堆排序最合適，依題意

可知只需取得第k個(gè)最小元素之前的

具體算法如下:【解答】具體算法如下:

一次歸并算法?Union]_荷蘭國旗算法FlagA可ust|

voidUnion(intA[],intn,intB[],intn,intC[])enumColor(Red,White,Blue);

(voidFlagAdjust(Colora[],intn)

H,j=l;k=l;(

i=O;j=O;k=n-l,

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

while(j<=k)

(

switcha[j]

if(A[i]<-B[j])C[k-+]=A[i+f],(

else