第8章排序介紹

1、第8章排序1選擇題（ 1）從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（）。A 歸并排序B 冒泡排序C 插入排序D 選擇排序答案：C（ 2）從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（）。A 歸并排序B 冒泡排序C 插入排序D 選擇排序答案：D（ 3）對(duì)n 個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在下列（）情況下比較的次數(shù)最多。A 從小到大排列好的C 元素?zé)o序B 從大到小排列好的D元素基本有序答案：B解釋：對(duì)關(guān)鍵字進(jìn)行冒泡排序，關(guān)鍵字逆序時(shí)比較次數(shù)最多。（ 4）對(duì) n 個(gè)不同的排序碼進(jìn)行冒泡排序

2、，在元素?zé)o序的情況下比較的次數(shù)最多為（）。A n+1B nC n-1D n(n-1)/2答案：D解釋：比較次數(shù)最多時(shí)，第一次比較n-1次，第二次比較n-2次,最后一次比較1次，即(n-1)+(n-2)+,+1= n(n-1)/2（ 5）快速排序在下列（。）情況下最易發(fā)揮其長(zhǎng)處。A 被排序的數(shù)據(jù)中含有多個(gè)相同排序碼B被排序的數(shù)據(jù)已基本有序C被排序的數(shù)據(jù)完全無(wú)序D被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案： C解釋： B 選項(xiàng)是快速排序的最壞情況。（ 6）對(duì) n 個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（）。A O(n)B O(n 2)C O(nlog 2 n)D O(n 3 )答案：

3、 B解釋：快速排序的平均時(shí)間復(fù)雜度為O(nlog 2n) ，但在最壞情況下，即關(guān)鍵字基本排好序的情況下，時(shí)間復(fù)雜度為O(n 2 )。（ 7）若一組記錄的排序碼為（46, 79， 56 ， 38 ， 40 ， 84 ），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A 38 ， 40， 46， 56 ， 79， 84B40，38，46，79， 56，84C40 ，38，46， 56，79，84D40，38，46，84， 56，79答案： C（ 8）下列關(guān)鍵字序列中，（）是堆。A 16 ， 72， 31， 23 ， 94， 53B94，23，31，72， 16，53C 16 ，

4、 53， 23 ， 94， 31， 72D16，23，53，31， 94，72答案：D解釋：D 選項(xiàng)為小根堆（ 9）堆是一種（）排序。A 插入B 選擇C交換D 歸并答案：B（ 10 ）堆的形狀是一棵（）。A 二叉排序樹(shù)B 滿二叉樹(shù)C完全二叉樹(shù)D 平衡二叉樹(shù)答案：C（ 11）若一組記錄的排序碼為（46 ， 79 ， 56 ， 38 ， 40 ， 84 ），則利用堆排序的方法建立的初始堆為（）。A 79 ， 46， 56， 38 ， 40， 84 C 84 ， 79， 56 ， 46， 40， 38B84，79，56，38， 40，46 D84，56，79，40， 46，38答案：B（ 12 ）下

5、述幾種排序方法中，要求內(nèi)存最大的是（）。A 希爾排序B 快速排序C 歸并排序D 堆排序答案：C解釋：堆排序、希爾排序的空間復(fù)雜度為歸并排序的空間復(fù)雜度為O(n) 。O(1) ，快速排序的空間復(fù)雜度為O(log2 n) ，（ 13 ）下述幾種排序方法中，（）是穩(wěn)定的排序方法。A 希爾排序B 快速排序C 歸并排序D 堆排序答案：C解釋：不穩(wěn)定排序有希爾排序、簡(jiǎn)單選擇排序、快速排序、堆排序；穩(wěn)定排序有直接插入排序、折半插入排序、冒泡排序、歸并排序、基數(shù)排序。（ 14 ）數(shù)據(jù)表中有10000 個(gè)元素，如果僅要求求出其中最大的10 個(gè)元素，則采用()算法最節(jié)省時(shí)間。A 冒泡排序B 快速排序C 簡(jiǎn)單選擇排

6、序D 堆排序答案： D（ 15 ）下列排序算法中，（）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A 希爾排序B 快速排序C 冒泡排序D 堆排序答案：A解釋：快速排序的每趟排序能將作為樞軸的元素放到最終位置；冒泡排序的每趟排序能將最大或最小的元素放到最終位置；堆排序的每趟排序能將最大或最小的元素放到最終位置。2應(yīng)用題（ 1）設(shè)待排序的關(guān)鍵字序列為 12 ， 2， 16 ， 30 ， 28 ， 10 ， 16* ， 20 ， 6， 18 ，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。 直接插入排序折半插入排序希爾排序（增量選取5， 3， 1）冒泡排序快速排序簡(jiǎn)單選擇排序堆

7、排序二路歸并排序答案：直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折半插入排序排序過(guò)程同希爾排序（增量選取5， 3， 1）102166181216*203028（增量選取5）621210181616*203028（增量選取3）2610121616*18202830 （增量選取1）冒泡排序2

8、1216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830 快速排序12621012283016*2016186261012283016*201618 28261012181616*20 2830 1826101216*161820283016*26101216* 1618202830左子序列遞歸深度為1 ，右子序列遞歸深度為3 簡(jiǎn)單選擇排序212163

9、0281016*20618261630281016*201218261030281616*201218261012281616*203018261012162816*2030182610121616182030282610121616*182028302610121616*18202830 二路歸并排序2 1216 3010 2816*20616* 20 286 182 10 12 16 16* 20 28 306 182610121616*18202830（ 2）給出如下關(guān)鍵字序列 321 ， 156 ， 57 ， 46 ，

10、28 ， 7， 331 ， 33 ， 34 ， 63 ，試按鏈?zhǔn)交鶖?shù)排序方法，列出每一趟分配和收集的過(guò)程。答案：按最低位優(yōu)先法 321 156 57 46 28 7 331 33 34 63分配 0 1 2 3 4 5 6 7 8 9321333415657 2833163467收集 321 331 33 63 34 156 46 57 7 28（ 3）對(duì)輸入文件（ 101 ， 51 ， 19， 61 ， 3， 71 ， 31， 17， 19 ， 100， 55 ， 20， 9， 30 ， 50 ，6， 90 ）；當(dāng) k=6 時(shí)，使用置換- 選擇算法，寫出建立的初始敗者樹(shù)及生成的初始?xì)w并段。答

11、案：初始敗者樹(shù)134025731161511111初始?xì)w并段：R1:3,19,31,51,61,71,100,101R2:9,17,19,20,30,50,55,90R 3:63算法設(shè)計(jì)題（ 1）試以單鏈表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。算法描述 ：voidLinkedListSelectSort(LinkedList head)/ 本算法一趟找出一個(gè)關(guān)鍵字最小的結(jié)點(diǎn)，其數(shù)據(jù)和當(dāng)前結(jié)點(diǎn)進(jìn)行交換; 若要交換指針，則須記下/ 當(dāng)前結(jié)點(diǎn)和最小結(jié)點(diǎn)的前驅(qū)指針p=head->next;while(p!=null)q=p->next; r=p;/while (q!=null)if(q->

12、;data<r->data) r=q;q:=q->next;設(shè) r 是指向關(guān)鍵字最小的結(jié)點(diǎn)的指針if(r!=p=p->next;p) r->data<->p->data;（ 2）有n 個(gè)記錄存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向鏈表中，現(xiàn)用雙向冒泡排序法對(duì)其按上升序進(jìn)行排序，請(qǐng)寫出這種排序的算法。（注：雙向冒泡排序即相鄰兩趟排序向相反方向冒泡）。 算法描述：typedefstructnode ElemType data;structnode *prior,*next;node， *DLinkedList;voidTwoWayBubbleSort(DLinkedLi

13、st la)/ 對(duì)存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向鏈表la中的元素進(jìn)行雙向起泡排序。 intexchange=1; /設(shè)標(biāo)記DLinkedList p,temp,tail;head=la/雙向鏈表頭，算法過(guò)程中是向下起泡的開(kāi)始結(jié)點(diǎn)tail=null;/雙向鏈表尾，算法過(guò)程中是向上起泡的開(kāi)始結(jié)點(diǎn)while(exchange)p=head->next;/p是工作指針，指向當(dāng)前結(jié)點(diǎn)exchange=0;/假定本趟無(wú)交換while(p->next!=tail) /向下（右）起泡，一趟有一最大元素沉底if(p->data>p->next->data) /交換兩結(jié)點(diǎn)指針，涉及6 條

14、鏈temp=p->next; exchange=1;/有交換p->next=temp->next;temp->next->prior=p /先將結(jié)點(diǎn)從鏈表上摘下將插到p 結(jié)點(diǎn)前temp->prior=p->prior; p->prior=temp;elsep=p->next; /無(wú)交換，指針后移tail=p; /準(zhǔn)備向上起泡p=tail->prior;while(exchange && p->prior!=head)/ 向上（左）起泡，一趟有一最小元素冒出if(p->data<p->prior-

15、>data)/temp=p->prior; exchange=1;/p->prior=temp->prior;temp->prior->next=p交換兩結(jié)點(diǎn)指針，涉及6 條鏈有交換；/ 先將 temp 結(jié)點(diǎn)從鏈表上摘下temp->prior=p;p->next->prior=temp;temp->next=p->next; p->next=temp;elsep=p->prior; /無(wú)交換，指針前移head=p;/準(zhǔn)備向下起泡/while(exchange)/ 將 temp 插到p 結(jié)點(diǎn)后（右） /算法結(jié)束（ 3）

16、設(shè)有順序放置的 n 個(gè)桶，每個(gè)桶中裝有一粒礫石，每粒礫石的顏色是紅，白，藍(lán)之一。要求重新安排這些礫石，使得所有紅色礫石在前，所有白色礫石居中，所有藍(lán)色礫石居后，重新安排時(shí)對(duì)每粒礫石的顏色只能看一次，并且只允許交換操作來(lái)調(diào)整礫石的位置。題目分析利用快速排序思想解決。由于要求“對(duì)每粒礫石的顏色只能看一次”，設(shè)3個(gè)指針i ， j和 k ，分別指向紅色、白色礫石的后一位置和待處理的當(dāng)前元素。從k=n開(kāi)始，從右向左搜索，若該元素是蘭色，則元素不動(dòng)，指針左移（即k-1）；若當(dāng)前元素是紅色礫石，分i>=j（這時(shí)尚沒(méi)有白色礫石）和i<j兩種情況。前一情況執(zhí)行第i 個(gè)元素和第k 個(gè)元素交換，之后i+

17、1 ；后一情況，i所指的元素已處理過(guò)（白色）， j 所指的元素尚未處理，應(yīng)先將i和 j 所指元素交換，再將 i 和 k 所指元素交換。對(duì)當(dāng)前元素是白色礫石的情況，也可類似處理。為方便處理，將三種礫石的顏色用整數(shù)1、2 和 3 表示。算法描述 ：void QkSort(rectype r,int n) /r 為含有n 個(gè)元素的線性表，元素是具有紅、白和蘭色的礫石，用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，/ 本算法對(duì)其排序，使所有紅色礫石在前，白色居中，蘭色在最后。int i=1,j=1,k=n,temp;while (k!=j)while (rk.key=3) k-;/當(dāng)前元素是蘭色礫石，指針左移if (rk.ke

18、y=1)/當(dāng)前元素是紅色礫石if (i>=j)temp=rk;rk=ri;ri=temp; i+;/ 左側(cè)只有紅色礫石，交換rk和rielsetemp=rj;rj=ri;ri=temp; j+;/ 左側(cè)已有紅色和白色礫石，先交換白色礫石到位temp=rk;rk=ri;ri=temp; i+;/白色礫石（i所指）和待定礫石（j所指）/再交換rk和ri，使紅色礫石入位。if (rk.key=2)if (i<=j) temp=rk;rk=rj;rj=temp; j+;/左側(cè)已有白色礫石，交換else temp=rk;rk=ri;ri=temp; j=i+1;rk和rj/i、 j分別指向紅

19、、白色礫石的后一位置/whileif (rk=2) j+;/*處理最后一粒礫石else if (rk=1) temp=rj;rj=ri;ri=temp; i+; j+; /最后紅、白、蘭色礫石的個(gè)數(shù)分別為: i-1;j-i;n-j+1/結(jié)束QkSor算法 算法討論為白色，rk.n交換rj與 ri若將j （上面指向白色）看作工作指針，將r1.j-1為蘭色。從j=1開(kāi)始查看，若rj為白色，則j=j+1，且 j=j+1，i=i+1；若 rj為蘭色，則交換rj與作為紅色，；若rjrk;k=k-1rj.k-1 為紅色，則。算法進(jìn)行到 j>k 為止。算法片段如下： int i=1,j=1,k=n;

20、while (j<=k)if(rj=1) /當(dāng)前元素是紅色temp=ri; ri=rj; rj=temp; i+;j+; elseif(rj=2) j+; /當(dāng)前元素是白色else/(rj=3當(dāng)前元素是蘭色temp=rj; rj=rk; rk=temp; k-; 對(duì)比兩種算法，可以看出，正確選擇變量（指針）的重要性。（ 4）編寫算法，對(duì) n 個(gè)關(guān)鍵字取整數(shù)值的記錄序列進(jìn)行整理，以使所有關(guān)鍵字為負(fù)值的記錄排在關(guān)鍵字為非負(fù)值的記錄之前，要求： 采用順序存儲(chǔ)結(jié)構(gòu)，至多使用一個(gè)記錄的輔助存儲(chǔ)空間；算法的時(shí)間復(fù)雜度為O(n) 。 算法描述void process (int An)low = 0;h

21、igh = n-1;while ( low<high )while (low<high && Alow<0)low+;while (low<high && Ahigh>0)high+;if (low<high)x=Alow;Alow=Ahigh;Ahigh=x;low+;high-;return;（ 5）借助于快速排序的算法思想，在一組無(wú)序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組rl.n中。若查找成功，則輸出該記錄在r 數(shù)組中的位置及其值，否則顯示“not find ”信息。請(qǐng)簡(jiǎn)要說(shuō)明算法思想并編寫算法。

22、 題目分析 把待查記錄看作樞軸，先由后向前依次比較，若小于樞軸，則從前向后，直到查找成功返回其位置或失敗返回0 為止。 算法描述int index (RecType R,int l,h,datatype key)int i=l,j=h;while (i<j) while (i<=j && Rj.key>key) j-;if (Rj.key=key) return j;while (i<=j && Ri.key<key) i+;if (Ri.key=key) return i;cout<<“Not find”; return 0;/index（ 6）有一種簡(jiǎn)單的排序算法，叫做計(jì)數(shù)排序。這種排序算法對(duì)一個(gè)待排序的表進(jìn)行排序