第8章排序技術(shù)課后習(xí)題講解1.填空題⑴排序的重要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行（）。

【解答】查找

【分析】對(duì)已排序的記錄序列進(jìn)行查找通常能提高查找效率。⑵對(duì)n個(gè)元素進(jìn)行起泡排序,在（）情況下比較的次數(shù)最少,其比較次數(shù)為（）。在（）情況下比較次數(shù)最多,其比較次數(shù)為（）。

【解答】正序,n-1,反序,n(n-1)/2⑶對(duì)一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行直接插入排序,當(dāng)把第7個(gè)記錄60插入到有序表時(shí),為尋找插入位置需比較（）次。

【解答】3

【分析】當(dāng)把第7個(gè)記錄60插入到有序表時(shí),該有序表中有2個(gè)記錄大于60。⑷對(duì)一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行快速排序,在遞歸調(diào)用中使用的棧所能達(dá)成的最大深度為（）。

【解答】3⑸對(duì)n個(gè)待排序記錄序列進(jìn)行快速排序,所需要的最佳時(shí)間是（）,最壞時(shí)間是（）。

【解答】O(nlog2n),O(n2)⑹運(yùn)用簡(jiǎn)樸選擇排序?qū)個(gè)記錄進(jìn)行排序,最壞情況下,記錄互換的次數(shù)為（）。

【解答】n-1⑺假如要將序列（50,16,23,68,94,70,73）建成堆,只需把16與（）互換。

【解答】50⑻對(duì)于鍵值序列（12,13,11,18,60,15,7,18,25,100）,用篩選法建堆,必須從鍵值為（）的結(jié)點(diǎn)開(kāi)始。

【解答】60

【分析】60是該鍵值序列相應(yīng)的完全二叉樹(shù)中最后一個(gè)分支結(jié)點(diǎn)。2.選擇題⑴下述排序方法中,比較次數(shù)與待排序記錄的初始狀態(tài)無(wú)關(guān)的是（）。

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

C選擇排序和歸并排序D插入排序和歸并排序

【解答】C

【分析】選擇排序在最佳、最壞、平均情況下的時(shí)間性能均為O(n2),歸并排序在最佳、最壞、平均情況下的時(shí)間性能均為O(nlog2n)。⑵下列序列中,（）是執(zhí)行第一趟快速排序的結(jié)果。

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

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

【解答】A

【分析】此題需要按字典序比較,前半?yún)^(qū)間中的所有元素都應(yīng)小于ff,后半?yún)^(qū)間中的所有元素都應(yīng)大于ff。⑶對(duì)初始狀態(tài)為遞增有序的序列進(jìn)行排序,最省時(shí)間的是（）,最費(fèi)時(shí)間的是（）。已知待排序序列中每個(gè)元素距其最終位置不遠(yuǎn),則采用（）方法最節(jié)省時(shí)間。

A堆排序B插入排序C快速排序D直接選擇排序

【解答】B,C,B

【分析】待排序序列中每個(gè)元素距其最終位置不遠(yuǎn)意味著該序列基本有序。⑷堆的形狀是一棵（）。

A二叉排序樹(shù)B滿二叉樹(shù)C完全二叉樹(shù)D鑒定樹(shù)

【解答】C

【分析】從邏輯結(jié)構(gòu)的角度來(lái)看,堆事實(shí)上是一種完全二叉樹(shù)的結(jié)構(gòu)。⑸當(dāng)待排序序列基本有序或個(gè)數(shù)較小的情況下,最佳的內(nèi)部排序方法是（）,就平均時(shí)間而言,（）最佳。

A直接插入排序B起泡排序C簡(jiǎn)樸選擇排序D快速排序

【解答】A,D⑹設(shè)有5000個(gè)元素,希望用最快的速度挑選出前10個(gè)最大的,采用（）方法最佳。

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

【解答】B

【分析】堆排序不必將整個(gè)序列排序即可擬定前若干個(gè)最大（或最小）元素。⑺設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按升序排列,則（）是起泡排序一趟掃描的結(jié)果,（）是增量為4的希爾排序一趟掃描的結(jié)果,（）二路歸并排序一趟掃描的結(jié)果,（）是以第一個(gè)元素為軸值的快速排序一趟掃描的結(jié)果,（）是堆排序初始建堆的結(jié)果。

A（F,H,C,D,P,A,M,Q,R,S,Y,X）

B（P,A,C,S,Q,D,F,X,R,H,M,Y）

C（A,D,C,R,F,Q,M,S,Y,P,H,X）

D（H,C,Q,P,A,M,S,R,D,F,X,Y）

E（H,Q,C,Y,A,P,M,S,D,R,F,X）

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

【分析】此題需要按字典序比較,并且需要掌握各種排序方法的執(zhí)行過(guò)程。⑻排序的方法有很多種,（）法從未排序序列中依次取出元素,與已排序序列中的元素作比較,將其放入已排序序列的對(duì)的位置上。（）法從未排序序列中挑選元素,并將其依次放入已排序序列的一端?；Q排序是對(duì)序列中元素進(jìn)行一系列比較,當(dāng)被比較的兩元素為逆序時(shí),進(jìn)行互換；（）和（）是基于這類(lèi)方法的兩種排序方法,而（）是比（）效率更高的方法；（）法是基于選擇排序的一種方法,是完全二叉樹(shù)結(jié)構(gòu)的一個(gè)重要應(yīng)用。

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

D起泡排序E歸并排序F堆排序

【解答】C,A,D,B,B,D,F⑼快速排序在（）情況下最不利于發(fā)揮其長(zhǎng)處。

A待排序的數(shù)據(jù)量太大B待排序的數(shù)據(jù)中具有多個(gè)相同值

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

【解答】C

【分析】快速排序等改善的排序方法均合用于待排序數(shù)據(jù)量較大的情況,各種排序方法對(duì)待排序的數(shù)據(jù)中是否具有多個(gè)相同值,待排序的數(shù)據(jù)數(shù)量為奇數(shù)或偶數(shù)都沒(méi)有影響。⑽（）方法是從未排序序列中挑選元素,并將其放入已排序序列的一端。

A歸并排序B插入排序C快速排序D選擇排序

【解答】D3.判斷題⑴假如某種排序算法是不穩(wěn)定的,則該排序方法沒(méi)有實(shí)際應(yīng)用價(jià)值。

【解答】錯(cuò)。一種排序算法適合于某種特定的數(shù)據(jù)環(huán)境,有時(shí)對(duì)排序的穩(wěn)定性沒(méi)有規(guī)定。⑵當(dāng)待排序的元素很大時(shí),為了互換元素的位置,移動(dòng)元素要占用較多的時(shí)間,這是影響時(shí)間復(fù)雜性的重要因素。

【解答】對(duì)。此時(shí)著重考慮元素的移動(dòng)次數(shù)。⑶對(duì)n個(gè)記錄的集合進(jìn)行快速排序,所需要的附加空間是Ο(n)。

【解答】錯(cuò)。最壞情況下是Ο(n)。⑷堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。

【解答】錯(cuò)。堆排序最佳、最壞及平均時(shí)間均為Ο(nlog2n),是待排序的記錄個(gè)數(shù)n的函數(shù)。一般來(lái)說(shuō),待排序的記錄個(gè)數(shù)越多,排序所消耗的時(shí)間也就越多。⑸設(shè)有鍵值序列（k1,k2,…,kn）,當(dāng)i>n/2時(shí),任何一個(gè)子序列（ki,ki+1,…,kn）一定是堆。

【解答】對(duì)。當(dāng)i>n/2時(shí),ki,ki+1,…,kn均是葉子結(jié)點(diǎn),所以一定是堆。4．已知數(shù)據(jù)序列為(12,5,9,20,6,31,24),對(duì)該數(shù)據(jù)序列進(jìn)行排序,寫(xiě)出插入排序、起泡排序、快速排序、簡(jiǎn)樸選擇排序、堆排序以及二路歸并排序每趟的結(jié)果。

【解答】用上述排序方法的每趟結(jié)果如下：5.對(duì)n=7,給出快速排序一個(gè)最佳情況和最壞情況的初始排列的實(shí)例。

【解答】最佳情況:4,7,5,6,3,1,2

最壞情況:7,6,5,4,3,2,16．判別下列序列是否為堆,如不是,按照堆排序思想把它調(diào)整為堆,用圖表達(dá)建堆的過(guò)程。

⑴（1,5,7,25,21,8,8,42）

⑵（3,9,5,8,4,17,21,6）

【解答】序列⑴是堆,序列⑵不是堆,調(diào)整為堆（假設(shè)為大根堆）的過(guò)程如圖8-5所示。7.已知下列各種初始狀態(tài)（長(zhǎng)度為n）的元素,試問(wèn)當(dāng)運(yùn)用直接插入排序進(jìn)行排序時(shí),至少需要進(jìn)行多少次比較（規(guī)定排序后的記錄由小到大順序排列）？

⑴關(guān)鍵碼從小到大有序（key1<key2<…<keyn）。

⑵關(guān)鍵碼從大到小有序（key1>key2>…>keyn）。

⑶奇數(shù)關(guān)鍵碼順序有序,偶數(shù)關(guān)鍵碼順序有序（key1<key3<…,key2key4…）。br/>⑷前半部分元素按關(guān)鍵碼順序有序,后半部分元素按關(guān)鍵碼順序有序,即:

（key1<key2<…<keym,keym+1<keym+2<…【解答】依題意,最佳情況下的比較次數(shù)即為最少比較次數(shù)。

⑴插入第i（2≤i≤n）個(gè)元素的比較次數(shù)為1,因此總的比較次數(shù)為:

1+1+……+1=n-1

⑵插入第i（2≤i≤n）個(gè)元素的比較次數(shù)為i,因此總的比較次數(shù)為:

2+3+……+n=(n-1)(n+2)/2

⑶比較次數(shù)最少的情況是所有記錄關(guān)鍵碼按升序排列,總的比較次數(shù)為:

n-1

⑷在后半部分元素的關(guān)鍵碼均大于前半部分元素的關(guān)鍵碼時(shí)需要的比較次數(shù)最少,總的比較次數(shù)為:

n-18.算法設(shè)計(jì)⑴直接插入排序中尋找插入位置的操作可以通過(guò)折半查找來(lái)實(shí)現(xiàn)。據(jù)此寫(xiě)一個(gè)改善的插入排序的算法。

【解答】插入排序的基本思想是：每趟從無(wú)序區(qū)中取出一個(gè)元素,再按鍵值大小插入到有序區(qū)中。對(duì)于有序區(qū),當(dāng)然可以采用折半查找來(lái)擬定插入位置。具體算法如下：mosimage}⑵設(shè)待排序的記錄序列用單鏈表作存儲(chǔ)結(jié)構(gòu),試寫(xiě)出直接插入排序算法。

【解答】本算法采用的存儲(chǔ)結(jié)構(gòu)是帶頭結(jié)點(diǎn)的單鏈表。一方面找到元素的插入位置,然后把元素從鏈表中原位置刪除,再插入到相應(yīng)的位置處。具體算法如下:⑶設(shè)待排序的記錄序列用單鏈表作存儲(chǔ)結(jié)構(gòu),試寫(xiě)出簡(jiǎn)樸選擇排序算法。

【解答】參見(jiàn)8.2.2。⑷對(duì)給定的序號(hào)j（1＜j＜n）,規(guī)定在無(wú)序記錄A[1]~A[n]中找到按關(guān)鍵碼從小到大排在第j位上的記錄,試運(yùn)用快速排序的劃分思想設(shè)計(jì)算法實(shí)現(xiàn)上述查找。

【解答】本算法不規(guī)定將整個(gè)記錄進(jìn)行排序,而只進(jìn)行查找第j個(gè)記錄。⑸寫(xiě)出快速排序的非遞歸調(diào)用算法。

【解答】先調(diào)用劃分函數(shù)Quickpass（劃分函數(shù)同教材）,以擬定中間位置,然后再借助棧分別對(duì)中間元素的左、右兩邊的區(qū)域進(jìn)行快速排序。⑹一個(gè)線性表中的元素為正整數(shù)或負(fù)整數(shù)。設(shè)計(jì)算法將正整數(shù)和負(fù)整數(shù)分開(kāi),使線性表的前一半為負(fù)整數(shù),后一半為正整數(shù)。不規(guī)定對(duì)這些元素排序,但規(guī)定盡量減少比較次數(shù)。

【解答】本題的基本思想是:先設(shè)立好上、下界和軸值,然后分別從線性表兩端查找正數(shù)和負(fù)數(shù),找到后進(jìn)行互換,直到上下界相遇。算法如下:⑺已知（k1,k2,…,kn）是堆,試寫(xiě)一算法將（k1,k2,…,kn,kn+1）調(diào)整為堆。

【解答】增長(zhǎng)一個(gè)元素應(yīng)從葉子向根方向調(diào)整,假設(shè)調(diào)整為小根堆。⑻給定n個(gè)記錄的有序序列A[n]和m個(gè)記錄的有序序列B[m],將它們歸并為一個(gè)有序序列,存放在C[m+n]中,試寫(xiě)出這一算法。

【解答】采用二路歸并排序中一次歸并的思想,設(shè)三個(gè)參數(shù)i、j和k分別指向兩個(gè)待歸并的有序序列和最終有序序列的當(dāng)前記錄,初始時(shí)i、j分別指向兩個(gè)有序序列的第一個(gè)記錄,即i=1,j=1,k指向存放歸并結(jié)果的位置,即k=1。然后,比較i和j所指記錄的關(guān)鍵碼,取出較小者作為歸并結(jié)果存入k所指位置,直至兩個(gè)有序序列之一的所有記錄都取完,再將另一個(gè)有序序列的剩余記錄順序送到歸并后的有序序列中。6.用直接插入排序?qū)ο旅嫠膫€(gè)序列進(jìn)行由小到大排序,元素比較次數(shù)最少的是（）。

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

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

【解答】B7.對(duì)數(shù)列（25,84,21,47,15,27,68,35,20）進(jìn)行排序,元素序列的變化情況如下:

⑴25,84,21,47,15,27,68,35,20⑵20,15,21,25,47,27,68,35,84

⑶15,20,21,25,35,27,47,68,84⑷15,20,21,25,27,35,47,68,84

則采用的排序方法是（）。

A希爾排序B簡(jiǎn)樸選擇排序C快速排序D歸并排序

【解答】C8.假如只想得到一個(gè)序列中第k個(gè)最小元素之前的部分排序序列，最佳采用什么排序方法？為什么？對(duì)于序列{57,40,38,11,13,34,48,75,25,6,19,9,7}，得到其第4個(gè)最小元素之前的部分序列{6,7,9,11}，使用所選擇的排序算法時(shí)，要執(zhí)行多少次比較？

【解答】采用堆排序最合適，依題意可知只需取得第k個(gè)最小元素之前的排序序列時(shí)，堆排序的時(shí)間復(fù)雜度Ο(n+klog2n)，若k≤nlog2n，則得到的時(shí)間復(fù)雜性是Ο(n)。

對(duì)于上述序列得到其前4個(gè)最小元素，使用堆排序?qū)崿F(xiàn)時(shí)，執(zhí)行的比較次數(shù)如下:

初始建堆:比較20次，得到6；

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

第二次調(diào)