數(shù)據(jù)結(jié)構(gòu)排序自測(cè)卷答案

第9章排序自測(cè)卷答案姓名班級(jí)

題號(hào)一二三四五總分

題分241836814100

得分

一、填空題（每空1分，共24分）

1.大多數(shù)排序算法都有兩個(gè)基本的操作：比較（兩個(gè)關(guān)鍵字的大?。┖鸵苿?dòng)（紀(jì)錄或轉(zhuǎn)變指向紀(jì)錄的指

針）?

2.在對(duì)一組紀(jì)錄（54,38,96,23,15,72,6（）,45,83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)紀(jì)錄60插入到有

序表時(shí)，為查找插入位置至少需比較二_次。（可商定為，從后向前比較）

3.在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序（到尾部）；若初始數(shù)據(jù)基本反序，則選

用選擇排序。

4.在堆排序和快速排序中，若初始紀(jì)錄接近正序或反序，則選用堆排序；若初始紀(jì)錄基本無序，則最好選

用快速排序。

5.對(duì)于n個(gè)紀(jì)錄的集合進(jìn)行冒泡排序，在最壞的狀況下所需要的時(shí)間是，若對(duì)其進(jìn)行快速排序，在

最壞的狀況下所需要的時(shí)間是，

6.對(duì)于n個(gè)紀(jì)錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是O（nlo敢n）,所需要的附加空間是

7.【計(jì)研題2000】對(duì)于n個(gè)紀(jì)錄的表進(jìn)行2路歸并排序，整個(gè)歸并排序需進(jìn)行l(wèi)og2n趟（遍），共計(jì)移

動(dòng)nlog2n次紀(jì)錄。

（即移動(dòng)到新表中的總次數(shù)！共log2n趟，每趟都要移動(dòng)n個(gè)元素）

8.設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母序的升序重新排列，貝!I：

冒泡排序一趟掃描的結(jié)果是H,C,Q,P.A.M,S,R.D,DX,丫：

初始步長(zhǎng)為4的希爾（shell）排序一趟的結(jié)果是P,A,C,S,Q,D,F,X.R,H,M,丫；

二路歸并排序一趟掃描的結(jié)果是H,Q,C,Y,A,P,M,S,SR,F,X；

快速排序一趟掃描的結(jié)果是F,H,C,D,P,A,M,Q,R,S,Y,X；

堆排序初始建堆的結(jié)果是A.D,C*R.F,Q*M.S,Y,P,H,X。

9.在堆排序、快速排序和歸并排序中，

若只從存儲(chǔ)空間考慮，則應(yīng)首先選取堆排序方法,其次選取快速排序方法,最終選取歸并排序方法;

若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取歸并排序方法:

若只從平均狀況下最快考慮，則應(yīng)選取快速排序方法:

若只從最壞狀況下最快并且要節(jié)約內(nèi)存考慮，則應(yīng)選取攜排座方法。

二、單項(xiàng)選擇題（每小題1分，共18分）

（C）1.將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較次。

A.8B.9C.10D.25

(C)2.排序方法中，從未排序序列中依次取出元素與己排序序列(初始時(shí)為空)中的元素進(jìn)行比較，將

其放入已排序序列的正確位置上的方法，稱為

A.希爾排序B.冒泡排序C.插入排序D.選擇排序

(D)3.排序方法中，從未排序序列中選擇元素，并將其依次插入已排序序列(初始時(shí)為空)的一端的方

法，稱為

A.希爾排序B.歸并排序C.插入排序D.選擇排序

(C)4.對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種狀況下比較的次數(shù)最多。

A.從小到大排列好的B.從大到小排列好的C.元素?zé)o序D.元素基本有序

(D)5.對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的狀況下比較的次數(shù)為

A.n+1B.nC.n-1D.n(n-l)/2

(前3個(gè)答案都太小了)

(C)6.快速排序在下列哪種狀況下最易發(fā)揮其特長(zhǎng)。

A.被排序的數(shù)據(jù)中含有多個(gè)相同排序碼B.被排序的數(shù)據(jù)已基本有序

C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊

(B)7.【計(jì)研題2001】對(duì)有n個(gè)紀(jì)錄的表作快速排序，在最壞狀況下，算法的時(shí)間簡(jiǎn)單度是

A.O(n)B.O(n2)C.O(nlog2n)D.O(nJ)

(C)8.若一組紀(jì)錄的排序碼為(46,79,56,38,40,84),則采用快速排序的方法，以第一個(gè)紀(jì)錄為基準(zhǔn)得

到的一次劃分結(jié)果為

A.38,40,46,56,79,84B.40,38,46,79,56,84

C.40,38,46,56,79,84D.40,38,46,84,56,79

(A&D)9.【計(jì)研題2001】在最好狀況下，下列排序算法中排序算法所需比較關(guān)鍵字次數(shù)最少。

A.冒泡B.歸并C.快速D.直接插入

(僅n—1次！)

(C)10.【計(jì)研題200。置換選擇排序的功能是。(置換選擇排序=簡(jiǎn)潔選擇排序？)

A.選出最大的元素B.產(chǎn)生初始?xì)w并段C.產(chǎn)生有序文件D.置換某個(gè)紀(jì)錄

(A)11.將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至少需要比較次。

A.4B.5C.6D.7

(D)12.下列關(guān)鍵字序列中，是堆。

A.16,72,31,23,94,53B,94,23,31,72,16,53C.16,53,23,94,31,72D.16,23,53,31,94,72

(B)13.堆是一種排序。

A.插入B.選擇C.交換D.歸并

(C)14.堆的外形是一棵

A.二叉排序樹B.滿二叉樹C.完全二叉樹D.平衡二叉樹

(B)15.若一組紀(jì)錄的排序碼為(46,79,56,38,40,84),則采用堆排序的方法建立的初始堆為

A.79,46,56,38,40,84B,84,79,56,38,40,46

C.84,79,56,46,40,38D.84,56,79,40,46,38

(B)16,下述幾種排序方法中，平均查找長(zhǎng)度(ASL)最小的是

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

(C)17.下述幾種排序方法中，要求內(nèi)存最大的是

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

(B)18.目前以比較為基礎(chǔ)的內(nèi)部排序方法中，其比較次數(shù)與待排序的紀(jì)錄的初始排列狀態(tài)無關(guān)的是

A.插入排序B.二分插入排序C,快速排序D.冒泡排序

三、簡(jiǎn)答題(每小題4分，共36分)

1.【全國(guó)專升本題】已知序列基本有序，問對(duì)此序列最快的排序方法是多少，此時(shí)平均簡(jiǎn)單度是多少？

答：插入排序和冒泡應(yīng)是最快的。由于只有比較動(dòng)作，無需移動(dòng)元素。此時(shí)平均時(shí)間簡(jiǎn)單度為O(n)

2.設(shè)有10()0個(gè)無序的元素，盼望用最快的速度選擇出其中前1()個(gè)最大的元素，最好采納哪種排序方法？

答：用堆排序或錦標(biāo)賽排序最合適，由于不必等全部元素排完就能得到所需結(jié)果，時(shí)間效率為O("lOg2〃)：若

用冒泡排序則需時(shí)n!/(n-10)!

3.用某種排序方法對(duì)線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí)，元素序列的變化狀況如下：

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,問采納的是什么排序方法？

答：用的是快速排序方法。留意每一趟要振蕩完全部元素才算一個(gè)中間結(jié)果。

4.對(duì)于整數(shù)序列100,99,98,-3,2,1,假如將它完全倒過來，分別用冒泡排序和快速排序法，它們的比較

次數(shù)和交換次數(shù)各是多少？

答:冒泡排序的比較和交換次數(shù)將最大，都是l+2+...+n-l=n(n-l)/2=50X99=4545次

快速排序則看按什么數(shù)據(jù)來分子表。

假如按100來分，則很慘，也會(huì)是n(n-l)/2!

若按中間數(shù)據(jù)50或51來分表，貝！1：

第1輪能確定1個(gè)元素，即在1個(gè)子表中比較和交換了n-l個(gè)元素；n-(2'-1)

第2輪能再確定2個(gè)元素，即在2個(gè)子表中比較和交換了n-3個(gè)元素；n-(22-1)

第3輪能再確定4個(gè)元素，即在4個(gè)子表中比較和交換了n—7個(gè)元素；n-(23-1)

第4輪能再確定8個(gè)元素，即在8個(gè)子表中比較和交換了n-15個(gè)元素；n-(2<1)

第6輪能再確定32個(gè)元素，即在32個(gè)子表中比較和交換了n-65個(gè)元素；n-(26-1)

第7輪則能全部確定，(由于27=128),在100個(gè)子表中比較和交換了n-(100-1)個(gè)元素；

比較和交換總次數(shù)為：7n-(21一l+22-l+23—1.......+26—1+100-1)=7n+7-(l+2+4+.........+64+100)=7n

-(8+16+32+164)=700-220=480次

若從中間選擇初始元素，貝!JASL=(n+1)login—(2*+22+23+........+2m)=nlog2n+log2n-(21+22+23+.......+n)

QO（nlogzn）

5.【全國(guó)專升本試題】【嚴(yán)題集10.15④】設(shè)有n個(gè)值不同的元素存于挨次結(jié)構(gòu)中，試問能否用比2n-3少的比較

次數(shù)選出這n個(gè)元素中的最大值和最小值？若能請(qǐng)說明如何實(shí)現(xiàn)（不需寫算法在最壞狀況下至少需進(jìn)行多少

次比較。（或問：對(duì)含有n個(gè)互不相同元素的集合，同時(shí)找最大元和最小元至少需進(jìn)行多少次比較？）

答：若用冒泡排序法，求最大值需n-1次比較；其次趟改為從n-1開頭求最小值，需n-2次比較，合計(jì)2n-3次。

明顯本題意圖是放棄冒泡排序，查找其他方法。

法1：一個(gè)簡(jiǎn)潔的方法是，在一趟比較時(shí)，將頭兩個(gè)元素分別作為最大和最小值的暫存內(nèi)容，將其余n-2個(gè)元

素與其相比，詳細(xì)可設(shè)計(jì)為：

第1步：al<a2?用來設(shè)立max和min標(biāo)志;無論Y/N都只比較1次；1次；

第2步：a3>a2?YES則直接替換a2,NO則再比較al,1?2次；

第3步：a4>a2?YES則直接替換a2,NO則再比較al,1?2次；

第n-1步：an>a2?YES則直接替換a2,NO則再比較al,1?2次；

合計(jì)：（n-2）X（1~2）+l=（n-l）~（2n-3）^2n-3最好狀況至少需要n-1次比較，最壞狀況需2n-3次。

法2:借用快速排序第一趟思想：以al為支點(diǎn)，將序列分成兩個(gè)子表。這一趟需要n-1次比較；

然后，在左邊的子表中求最小值，冒泡一趟需要y-1次；

在右邊的子表中求最大值，冒泡一趟需要z-1次；

合計(jì)需要（n-l）+（y-l）+（z-l）=n+y+z-3由于y+z+l=n,所以總次數(shù)=2n—4W2n—3!!!!!!!!!!!

但最壞狀況下仍為為2n-3次，即一趟完畢后仍為單子表的狀況。怎么辦？有無更好的方法？

法3；能否用錦標(biāo)賽排序思路？求最大值等于求冠軍，需要n-l次比較；但接著求最小值，等于在n/2個(gè)葉子

中比較即可。

編程也不簡(jiǎn)單：可設(shè)計(jì)為，

第一趟：n個(gè)數(shù)據(jù)兩兩比較（共n/2次），小者放偶數(shù)位，大者放奇數(shù)位；

其次趟：對(duì)奇數(shù)位元素連續(xù)兩兩比較（n/4次）；對(duì)偶數(shù)位元素也兩兩比較（n/4次）；合計(jì)n/2次；

第三趟：對(duì)奇數(shù)位元素連續(xù)兩兩比較（n/23次）；對(duì)偶數(shù)位元素也兩兩比較（n/23次）；合計(jì)n/22次；

第四趟：對(duì)奇數(shù)位元素連續(xù)兩兩比較（n/24次）；對(duì)偶數(shù)位元素也兩兩比較（n/2』次）；合計(jì)n/23次；

第log2n趟：對(duì)奇數(shù)位元素連續(xù)兩兩比較（出21。3次=1）；對(duì)偶數(shù)位元素也兩兩比較（1次）；合計(jì)2次;

全部比較次數(shù)為：2+4+8+.......+n/2次W2n-3（n>l）

用二進(jìn)制性質(zhì)即可證明？由于2。+24…2k-2+2k-i〈2k,BP2'+—2k-2+2k-'<2k—1<2k—1+2k—2

（n=2k,當(dāng)k=l,即n=2時(shí)為極端狀況，1=1;n=3時(shí)，1.5<3

k=2時(shí)，即n=4時(shí)，2<5

6.【成教考題】將兩個(gè)長(zhǎng)度為n的有序表歸并為一個(gè)長(zhǎng)度為2n的有序表，最小需要比較n次，最多需要比較

2n-l次，請(qǐng)說明這兩種狀況發(fā)生時(shí)，兩個(gè)被歸并的表有何特征？

答：最少的比較次數(shù)是這樣一種狀況：若A表全部元素都小于（或大于）B表元素，則A1比較完B1?Bn之后,

直接拼接即可。

最多比較次數(shù)的狀況應(yīng)是A、B兩表相互交叉，此時(shí)需要穿插重排。則A表的每個(gè)元素都要與B表元素相比，

A1與B1相比，能確定其中一個(gè)元素的位置；剩下一個(gè)還要與另一表中下一元素再比較一次，

即：在表A或表B的n個(gè)元素中，除了最終一個(gè)元素外，每個(gè)元素都要比較2次！最壞狀況總共為2n-l次。

7.1嚴(yán)題集10.11②】試問：按錦標(biāo)賽排序的思想，決出8名運(yùn)動(dòng)員之間的名次排列，至少需編排多少場(chǎng)次的

競(jìng)賽（應(yīng)考慮最壞的狀況）？

劉答：不能簡(jiǎn)潔地用（n-l）+（n-2）log2n來計(jì)算競(jìng)賽場(chǎng)次。要特殊留意，隨著n/2的葉子結(jié)點(diǎn)被調(diào)整完畢之后，樹的

深度會(huì)逐層削減！

分別n=8和n=7的狀況推導(dǎo)并歸納，得到如下計(jì)算公式：

競(jìng)賽場(chǎng)次=（n-1）+n/2（k-l）+（n/22）（k-2）+…+n/2g）,其中k=|jog2n」

當(dāng)n=8時(shí)，k=3,競(jìng)賽場(chǎng)次=7+8/2（2）+8/4=17場(chǎng)（這是最壞狀況，即每次都先從葉子調(diào)整起）

8.1嚴(yán)題集10.19④】假設(shè)某大旅店共有5000個(gè)床位，每天需要依據(jù)住宿旅客的文件制造一份花名冊(cè)，該名

冊(cè)要求按?。ㄊ校┑拇涡蚺帕?，每一省（市）按縣（區(qū)）排列，又同一縣（區(qū)）的旅客按姓氏排列。請(qǐng)你為

旅店的管理人員設(shè)計(jì)一個(gè)制作這份花名冊(cè)的方法。

（提示）這是一個(gè)多關(guān)鍵字的排序問題。請(qǐng)思索對(duì)這個(gè)文件進(jìn)行排序用哪一種方法更合適，是MSD法還是LSD

法？

答：采納哪種排序方法，關(guān)鍵要看紀(jì)錄的結(jié)構(gòu)是如何定義的，假如旅客填表如下：

?。ㄊ校┛h（區(qū)）姓名床位號(hào)

則按題意要求，應(yīng)采納MSD法，否則無法滿意。

但若“姓名”項(xiàng)在前，則必需用LSD才符合題意要求。

9.【全國(guó)專升本題】【嚴(yán)題集10.6④】奇偶交換排序如下所述：第一趟對(duì)全部奇數(shù)1,將a[/|和a[”7]進(jìn)行比

較；其次趟對(duì)全部的偶數(shù)，將a[2]和a[?+l]進(jìn)行比較，若a[/|>a[￡+l],則兩者交換；第三趟對(duì)奇數(shù)，第四

趟對(duì)偶數(shù)2;……依次類推直至整個(gè)序列有序?yàn)橹埂?/p>

（1）試問這種排序方法的結(jié)束條件是什么？是否為穩(wěn)定排序？

（2）分析當(dāng)時(shí)始序列為正序或逆序兩種狀況下，奇偶交換排序過程中所需進(jìn)行的關(guān)鍵字比較的次數(shù)。

（3）分析此種排序方法的平均簡(jiǎn)單度及最壞簡(jiǎn)單度。

答：（1）這種算法其實(shí)是兩兩比較，第一趟很像錦標(biāo)賽的“初賽”，將勝者（大數(shù)）置于偶數(shù)單元；

其次趟對(duì)偶數(shù)單元操作，即第一組大者與其次組小者戰(zhàn)，大者后移。結(jié)果相當(dāng)于冒泡排序的一趟；

所以結(jié)束條件應(yīng)為偶數(shù)趟無交換。

結(jié)束條件是：若n為偶數(shù)時(shí)，奇數(shù)循環(huán)時(shí)i>n-l，偶數(shù)循環(huán)時(shí)i>n，

若n為奇數(shù)時(shí)，奇數(shù)循環(huán)時(shí)i>n偶數(shù)循環(huán)時(shí)i>n+l

好像不穩(wěn)定？由于交換沒有依次進(jìn)行。

四、【全國(guó)專升本類似題】【類嚴(yán)題集104①】以關(guān)鍵字序列（256,301，751，129,937,863,742,

694,076,438）為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說明這

些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？

①直接插入排序②希爾排序③冒泡排序④快速排序

⑤直接選擇排序⑥堆排序⑦歸并排序⑧基數(shù)排序（8分）

解：先回答第2問：①⑤⑦⑧皆易于在鏈表上實(shí)現(xiàn)。

①直接插入排序的中間過程如下：②希爾排序的中間過程如下:

第一趟：(256,301),751.129,937,863.742,694,076.438

第二超：(256,301,751),129,937,863,742,694,(X76,438(2)希爾H序(取d=l5,3,H)

第三越;(129.256,301.751),937,863,742,?>4,076.438第一楞：256,301,694,076.438,863,742.751,129.937

第四趟：(129.256.301,751,937),863,742.694,076,438第二靖：076,301,129,256,438,694,742,751,863.937

第五趟：(129.256,301,751,863.937),742.076,438笫三越：076,129,256,301,438,694,742,751,863,937

第六趟：(129,256,301,742,751,863,937).694,076.438

第七趟：(129,256.301.陽4,742,751,863,937),076,438

第八趟：(076,129,256,301.694.742,751,863,937),438

第九趟：(076,129,256,301,438,694.742,751.K63.937)

③冒泡排序的中間過程如下：④快速排序的中間過程如下：

256,301,751,129,937,863,742,694,076.438256,301,751,129.937.R63.742,694,076.438

第一楞：256,301,129.751,863,742.694,076,438,937第一?。?076,129),256.(751.937.863,742,694.301,439)

第二越：256,129,301,751.742,6?M,076,438,863,937第二趟：076.129,256,(438,301.694.742).751,(863,937)

第三趟：129.256.301,742,604,076.4翔,751,863.937

后?!:076,129.256,301,438.(694,742),751,(863.937)

第四趟：129.256.301.694.076,438.742.751.86^,937

第四趟：076,129,256.301.438.694,742,751,(863.937)

第五趟：129.256,301,076,438,694.742.751.863,937

第五趟：076,129,256,301.438,694,742,751.863,937

第六趟：129,256,076.301,438,694,742,751.863,937

第七超：129,076.256.301,438.694,742.751.863.937

第八焙：076,129,256.301,438,694,742,751.863,937

第九超:076,129.256.301.438.694,742.751.863.937

⑤直接選擇排序的中間過程如下:⑥堆排序（大根堆）的中間過程如下:

256,301,751,129,937,863,742,694,076,438

第一趟：(256,301),751,129,937,863.742,694.076.438

第一趟：(937,694.863.256.43?.751.742.129,076,301)

第二趟：(256,3()1.751).129,937.863.742.6(M.076.438

第二超：(863.6W,751.256,438,301.742,129,076).937

第三造：(129.256,301,751),W7.863.742.694,076.438

第三糖：(751.694,742,256,438.301,076,129),S63.937

第四梢：(129,256,301.751.937).863.742.694.076.438

第四趙：(742,694,301,256.438.129,076).751.863.937

第幾趟：(129,256.301.751.863.937),742,694.076.438

第五iS:(694,438.301,256,076.129),742,751.863.937

笫六度：(129.256.301,742.751.863.937).694.076.438

第六趟：(438,256,301,129,076).742,751,863.937

第七超：(129.256.501,694,742,751.863.937).076.438

第七朝：(301,256,076.129).438.694,742,751,863.937

第八趟：(076.129.256,301,694.742,751,863.<07>,438

第八遇：(256.129.076).301.438.694,742.751,863,937

第九趟：(076,129.256,301,438,694,742,751.863,937)

第九趟：076,129.256,301,438,694,742.751,863,!?7

⑦歸并排序排序的中間過程如下：

256.301,751,129,937,863,742,694,076,438

第一趟：1256],[301].[751],[129],[937],[863],[742],[694],[076],[438]

第二趟：！256,3011.：129.751],|863,937].[矽4.742].[86,438]

第三趟：[129.256,刈，751].[矽4.742,863,937J.[076,438]

笫四越：[076.129.256.301,438,694,742,751,863,937]

⑧基數(shù)排序的中間過程如下：

256,301.751,129.937,863,742.694,076,438

第趟：301,751.742.863,694.256,076,W7.43R,129

第二趟：301.129,937,438,742.751,256,863.076,694

第二趟：(H6,129,256,301.438,694,742,751,863.937

五、算法設(shè)計(jì)題(4選2,每題7分，共14分)

1.【嚴(yán)題集10.25③】試編寫教科書節(jié)中所述鏈表插入排序的算法。

10.25

voidSLInsert_Sort(SLList&L)〃靜態(tài)鏈表的插入排序算法

(

L.r[0],key=O;L.r[O].next=1;

L.r[1].next=0;〃建初始循環(huán)鏈表

for(i=2;i<=L.length;i++)//逐個(gè)插入

(

p=O;x=L.rli].key;

while(L.r[L.r[p].next].key<x&&L.r[p].next)

p=L.r[pJ.next;

q=L.r[p].next;

L.r[p].next=i;

L.r[i].next=q;

}//for

p=L.r[0].next;

for(i=l;i〈L.length;i++)〃重排紀(jì)錄的位置

(

while(p<i)p=L.r[p].next;

q=L.r[p].next;

if(p!=i)

(

L.rlp]<->L.r[i];

L.r[i].next=p;

)

p=q;

}//for

}//SLInsert_Sort

2.【嚴(yán)題集10.30@］按下述原則編寫快排的非遞歸算法：

(1)一趟排序之后，先對(duì)長(zhǎng)度較短的子序列進(jìn)行排序，且將另一子序列的上、下界入棧保存;

(2)若待排紀(jì)錄數(shù)W3,則不再進(jìn)行分割，而是直接進(jìn)行比較排序。

10.30

typedefstruct{

intlow;

inthigh;

}boundary;〃子序列的上下界類型

voidQSort_NotRecurve(intSQList&L)〃快速排序的非遞歸算法

(

low=l;high=L.length;

InitStack(S);//S的元素為boundary類型

while(low〈high&&!StackEmpty(S))〃留意排序結(jié)束的條件

(

if(high-low>2)〃假如當(dāng)前子序列長(zhǎng)度大于3且尚未排好序

(

pivot二Partition(L,low,high);〃進(jìn)行一趟戈ij分

if(high-pivot>pivot-low)

(

Push(S,{pivot+1,high});〃把長(zhǎng)的子序列邊界入棧

high=pivot?l;〃短的子序列留待下次排序

}

else

(

Push(S,{low,pivot-1));

low=pivot+l;

)

}//if

elseif(low<high&&high」ow<3)〃假如當(dāng)前子序歹I」長(zhǎng)度小于3且尚未排好序

(

Easy_Sort(L,low,high);〃直接進(jìn)行比較排序

low二high;〃當(dāng)前子序列標(biāo)志為已排好序

else//假如當(dāng)前子序列已排好序但棧中還有未排序的子序列

(

Pop(S,a);〃從棧中取出一個(gè)子序列

low=a.low;

high=a.high;

)

}//while

}//QSort_NotRecurve

intPartition(SQList&L,intlow,inthigh)//一趟劃分的算法，與書上相同

(