第6章內(nèi)部排序

第6章內(nèi)部排序1

6.1概述

6.2插入排序

6.3交換排序

6.4選擇排序

6.5歸并排序6.6基數(shù)排序6.7小結(jié)（直接插入排序、希爾排序）（起泡排序、快速排序）（直接選擇排序、堆排序）6.1概述21.什么是排序？將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時(shí)間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性———若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B

的先后次序保持不變，則稱(chēng)此排序算法是穩(wěn)定的。

——便于查找！6.1概述3若待排序記錄都在內(nèi)存中，稱(chēng)為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱(chēng)為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。

5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？大多數(shù)排序算法都有兩個(gè)基本的操作：（1）比較兩個(gè)關(guān)鍵字的大?。?）將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置（1）順序存儲(chǔ)（2）靜態(tài)鏈表（3）地址4.什么叫內(nèi)部排序？什么叫外部排序？6.1概述4注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)Typedefstruct{

//定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)

KeyTypekey;

//關(guān)鍵字

InfoTypeotherinfo;

//其它數(shù)據(jù)項(xiàng)}RecordType;Typedefstruct{

//定義順序表的結(jié)構(gòu)

RecordTyper[MAXSIZE+1];

//存儲(chǔ)順序表的向量

//r[0]一般作哨兵或緩沖區(qū)

intlength;

//順序表的長(zhǎng)度}SqList;#defineMAXSIZE20//設(shè)記錄不超過(guò)20個(gè)typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）6.順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類(lèi)型6.2插入排序5插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：

（1）直接插入排序（2）折半插入排序（3）表插入排序

（4）希爾排序

每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。6.2.1直接插入排序6直接插入排序是最簡(jiǎn)單的排序方法新元素插入到哪里？在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后順移。6.2.1直接插入排序7例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列?！?3】,6,3,31,9,27,5,11第一趟直接插入排序【6,13】,3,31,9,27,5,11第二趟直接插入排序【3,6,13】,31,9,27,5,11第三趟直接插入排序【3,6,13，31】,9,27,5,11第四趟直接插入排序【3,6,9,13，31】,27,5,11第五趟直接插入排序【3,6,9,13，27,31】,5,11第六趟直接插入排序【3,5,6,9,13，27,31】,11第七趟直接插入排序【3,5,6,9,11，13，27,31】

例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請(qǐng)寫(xiě)出直接插入排序的具體實(shí)現(xiàn)過(guò)程。8i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組V[7]中，將V[0]作為緩沖或暫存單元（Temp）。則程序執(zhí)行過(guò)程為：254925*初態(tài)：16252108時(shí)間效率：

O(n2)——因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動(dòng)元素的次數(shù)?？臻g效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：穩(wěn)定——因?yàn)?5*排序后仍然在25的后面。2149164925*直接插入排序算法9voidInsertsort(){inti,j;for(i=2;i<=N;i++){ p[0]=p[i]; j=i-1; while(p[0]<p[j]) { p[j+1]=p[j]; j--; } p[j+1]=p[0];}}ijjj6.2.3希爾（shell）排序（又稱(chēng)縮小增量排序）10基本思想先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。技巧

子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。11380123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697r[i]4913382749*6555970476算法分析：開(kāi)始時(shí)dk

的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，dk

值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。6.3交換排序12

兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有：

（1）冒泡排序

（2）快速排序交換排序的基本思想是：6.3.1冒泡排序13基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。21，25，49，

25*，16，0821，25，

25，49，

25*,49，

16，

49，

08

，49第1趟冒泡排序結(jié)果21，25，

25*,

16，

08

，49冒泡排序的算法14voidbsort(inta[],intn){inttemp,i,j;intflag;//交換標(biāo)志

for(j=1;j<=n-1;j++)//最多做n-1趟排序

{flag=0;//本趟排序開(kāi)始前，交換標(biāo)志應(yīng)為0for(i=1;i<=n-j;i++)//對(duì)當(dāng)前無(wú)序區(qū)掃描

if(a[i]>a[i+1]){//交換記錄

temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;//發(fā)生了交換，故將交換標(biāo)志置為真

}if(flag==0)break;//本趟排序未發(fā)生交換，提前終止算法

}}6.3.2快速排序15

從待排序列中任取一個(gè)元素(例如取第一個(gè))作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了?；舅枷耄豪?：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出快速排序的算法步驟。(設(shè)以首元素為樞軸中心)21，25，49，25*，16，08ij08，25，49，25*，16，□ij08，□，49，25*，16，25ji08，16，49，25*，□，25ji08，16，□，25*，49，25ji08，16，□，25*，49，25ji08<21,所以交換，i++25>21,所以交換，j--16<21,所以交換，i++49>21,所以交換，j--第1趟快速排序結(jié)果{08，16}，21，{25*，49，25}第1趟快速排序結(jié)果{08，16}，21，{25*，49，25}，分別對(duì){08，16}和{25*，49，25}進(jìn)行快速排序?qū)08，16}

進(jìn)行快速排序

08，16ij08，16ij08<16,不需要交換，j--∴{08，16}快速排序結(jié)果08，{16}對(duì){25*，49，25}進(jìn)行快速排序

25*，49，25ij25*，49，25ij25*=25,不需要交換，j--∴{25*，49，25}快速排序結(jié)果25*，{49，25}25*，49，25ij25*<49,不需要交換，j--第2趟快速排序結(jié)果

08，{16}，21，25*，{49，25}快速排序算法18pivotkey=r[i].key;//取支點(diǎn)的關(guān)鍵碼存入pivotkey變量while(i<j){

//從表的兩端交替地向中間掃描

while(i<j&&r[j].key>=pivotkey)--j; r[i]=r[j];//將比支點(diǎn)小的記錄交換到低端；

while(i<j&&r[i].key<=pivotkey)++i; r[j]=r[i];//將比支點(diǎn)大的記錄交換到高端；}r[i]=r[0];//支點(diǎn)記錄到位；

returni;//返回支點(diǎn)記錄所在位置。}//PartitionintPartition(SqList&L,inti,intj){//一趟快排

r[0]=r[i];//以子表的首記錄作為支點(diǎn)記錄，放入r[0]單元一趟快速排序算法（針對(duì)一個(gè)子表的操作）①每一趟的子表的形成是采用從兩頭向中間交替式逼近法；②由于每趟中對(duì)各子表的操作都相似，主程序可采用遞歸算法。快速排序算法19voidQSort(SqList&L,inti,intj){

if(i<j){

pivot=Partition(L,i,j);

QSort(L,i,pivot-1);

QSort(L,pivot+1,j);}}整個(gè)快速排序的遞歸算法：//長(zhǎng)度>1//對(duì)順序表L中的子序列r[i…j]

作快速排序//一趟快排，將r[]一分為二//在左子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為1//在右子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為1//QSort6.4選擇排序20選擇排序有多種具體實(shí)現(xiàn)算法

（1）簡(jiǎn)單選擇排序

（2）堆排序選擇排序的基本思想是：每一趟在后面n-i個(gè)待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。6.4.1簡(jiǎn)單選擇排序21思路簡(jiǎn)單：每經(jīng)過(guò)一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互換即可。首先，在n個(gè)記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個(gè)記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序?yàn)橹埂?.4.1簡(jiǎn)單選擇排序22例：關(guān)鍵字序列T=（21，25，49，25*，16，08），請(qǐng)給出簡(jiǎn)單選擇排序的具體實(shí)現(xiàn)過(guò)程。原始序列：

21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,

49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49最小值08

與r[1]交換位置簡(jiǎn)單選擇排序的算法23SELECTSORT(){inti,j,k;for(i=1;i<n;i++){k=i;for(j=i+1;j<=n;j++)if(p[j]<p[k])k=j;if(k!=i){temp=p[i];p[i]=p[k];p[k]=temp;}}}//在r[i…n]中選擇key最小的記錄//與第i個(gè)記錄交換6.4.2堆排序241.什么是堆？堆的定義：設(shè)有n個(gè)元素的序列k1，k2，…，kn，當(dāng)且僅當(dāng)滿(mǎn)足下述關(guān)系之一時(shí)，稱(chēng)之為堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

k2i+1或者i=1,2,…n/2解釋?zhuān)喝绻対M(mǎn)足以上條件的元素序列（k1，k2，…，kn）順次排成一棵完全二叉樹(shù)，則此樹(shù)的特點(diǎn)是：樹(shù)中所有根結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹(shù)的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?。2.怎樣建堆？3.怎樣堆排序？6.4.2堆排序25082546495867234561（大根堆）918566765867234561557例：有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判斷它們是否“堆”？√（小根堆）√（小頂堆）（最小堆）（大頂堆）（最大堆）2.怎樣建堆？26步驟：從最后一個(gè)非終端結(jié)點(diǎn)開(kāi)始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。212525*491608123456例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)建大根堆。解：為便于理解，先將原始序列畫(huà)成完全二叉樹(shù)的形式完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)編號(hào)必為n/2

??！注：終端結(jié)點(diǎn)（即葉子）沒(méi)有任何子女，無(wú)需單獨(dú)調(diào)整。21i=3:

49大于08，不必調(diào)整；i=2:

25大于25*和16，也不必調(diào)整；i=1:

21小于25和49，要調(diào)整！49而且21還應(yīng)當(dāng)向下比較?。?.怎樣進(jìn)行堆排序？27關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列重新調(diào)整為堆？方法：將當(dāng)前頂點(diǎn)與堆尾記錄交換，然后仿建堆動(dòng)作，從上至下新調(diào)整，如此反復(fù)直至排序結(jié)束。例：對(duì)剛才建好的大根堆進(jìn)行排序28刪除49交換1號(hào)與6號(hào)記錄492525*211608123456初始最大堆2525*1621136542084929刪除25交換1號(hào)與5號(hào)記錄從1號(hào)到5號(hào)重新調(diào)整為最大堆082525*2116491234561625*08252149136542082525*08從1號(hào)到4號(hào)重新調(diào)整為最大堆25*16082125491234566.5歸并排序30歸并排序的基本思想是：將兩個(gè)（或以上）的有序表組成新的有序表。更實(shí)際的意義：可以把一個(gè)長(zhǎng)度為n的無(wú)序序列看成是n個(gè)長(zhǎng)度為1的有序子序列，首先做兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的子序列；再做兩兩歸并，…，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序序列。310816212525*374954627293len=1616375408212525*49627293len=8212525*4908627293len=4163754212525*4962930872163754212525*9362720837165449len=1len=2例：關(guān)鍵字序列T=（21，25，49，25*，93，62，72，08，37，16，54），請(qǐng)給出歸并排序的具體實(shí)現(xiàn)過(guò)程。6.6基數(shù)排序32要討論的問(wèn)題：1.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？2.單邏輯關(guān)鍵字怎樣“按位值”排序？基數(shù)排序的基本思想是：借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序。即：用關(guān)鍵字不同的位值進(jìn)行排序。1.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？33例1：對(duì)一副撲克牌該如何排序？

若規(guī)定花色和面值的順序關(guān)系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A多關(guān)鍵字排序的實(shí)現(xiàn)方法通常有兩種：最高位優(yōu)先法MSD

(MostSignificantDigitfirst)最低位優(yōu)先法LSD

(LeastSignificantDigitfirst)1.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？34例：對(duì)一副撲克牌該如何排序？答：若規(guī)定花色為第一關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），則使用MSD和LSD方法都可以達(dá)到排序目的。MSD方法的思路：先設(shè)立4個(gè)花色“箱”，將全部牌按花色分別歸入4個(gè)箱內(nèi)（每個(gè)箱中有13張牌）；然后對(duì)每個(gè)箱中的牌按面值進(jìn)行排序。LSD方法的思路：先按面值分成13堆（每堆4張牌），然后對(duì)每堆中的牌按花色進(jìn)行排序。2.單邏輯關(guān)鍵字怎樣“按位值”排序？35設(shè)n個(gè)記錄的序列為：{V0,V1,…,Vn-1}，可以把每個(gè)記錄Vi

的單關(guān)鍵碼Ki

看成是一個(gè)d元組（Ki1,Ki2,…,Kid），則其中的每一個(gè)分量Kij

(1

jd)

也可看成是一個(gè)關(guān)鍵字。4注1：

Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元組；注2：每個(gè)分量Kij(1

j

d)有radix種取值，則稱(chēng)radix為基數(shù)。26(9,8,4)(0,1,…,9)（a,b,…,z）(d,i,a,n)310例1：關(guān)鍵碼984可以看成是

元組；基數(shù)radix

為

。例2：關(guān)鍵碼dian可以看成是

元組；基數(shù)radix

為

。思路：這種LSD排序方法稱(chēng)為：36例：初始關(guān)鍵字序列T=（32,13,27,32*,19，33），請(qǐng)分別用MSD和LSD進(jìn)行排序。法1（MSD）：原始序列：32,19,27,32*,13，33

先按高位Ki1

排序：（19,13）,27,（32,32*，33）

再按低位Ki2排序：13,19

，27,32,32*,33法2（LSD）：原始序列：32,13,27,32*,19，33

先按低位Ki2排序：

32,32*,13,33,27,19

再按高位Ki1排序：

13,19,27,32,32*,33基數(shù)排序用鏈隊(duì)列來(lái)實(shí)現(xiàn)基數(shù)排序—鏈?zhǔn)交鶖?shù)排序2.單邏輯關(guān)鍵字怎樣“按位值”排序？37例:請(qǐng)實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序：

T=（614，738，921，485，637，101，215，530，790，306）614921485637738101215530790306第一趟分配e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]原始序列鏈表：r[0]→（從最低位i=3開(kāi)始排序，f[]

是隊(duì)首指針，e[]

為隊(duì)尾指針）第一趟收集（讓隊(duì)尾指針e[i]

鏈接到下一非空隊(duì)首指針f[i+1]

即可）530790921101614485215306637738r[0]→第一趟收集的結(jié)果38e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第二趟分配（按次低位i=2）530790921101614485215306637738第二趟收集（讓隊(duì)尾指針e[i]

鏈接到下一非空隊(duì)首指針f[i+1]

）530790921101614485215306637738r[0]→r[0]→第二趟收集的結(jié)果39530790921101614485215306637738e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第三趟分配（按最高位i=1）第三趟收集（讓隊(duì)尾指針e[i]

鏈接到下一非空隊(duì)首指針f[i+1]

）530790921101614485215306637738r[0]→r[0]→各種內(nèi)部排序方法的比較40排序方法最好情況平均時(shí)間最壞情況輔助存儲(chǔ)穩(wěn)定性簡(jiǎn)單排序O(n)O(n2)O(n2)O(1）穩(wěn)定快速排序O(nlgn)O(nlgn)O(n2)O(lgn)不穩(wěn)定堆排序O(nlgn)O(nlgn)O(nlgn)O(1）不穩(wěn)定歸并排序O(nlgn)O(nlgn)O(nlgn)O(n）穩(wěn)定基數(shù)排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)穩(wěn)定簡(jiǎn)單選擇O(n2)O(n2)O(n2)O(1）不穩(wěn)定直接插入O(n)O(n2)O(n2)O(1）穩(wěn)定折半插入O(nlgn)O(nlgn)O(nlgn)O(1）穩(wěn)定冒泡O(n)O(n2)O(n2)O(1）穩(wěn)定練習(xí)411.

以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫(xiě)出執(zhí)行直接插入排序的各趟排序過(guò)程。原始序列：

256，301，751，129，937，863，742，694，076，438[256，301]，751，129，937，863，742，694，076，438[256，301，751]，129，937，863，742，694，076，438[129，256，301，751]，937，863，742，694，076，438[129，256，301，751，937]，863，742，694，076，438[129，256，301，751，863，937]，742，694，076，438[129，256，301，742，751，863，937]，694，076，438[129，256，301，694，742，751，863，937]，076，438[076，129，256，301，694，742，751，863，937]，438[076，129，256，301，438，694，742，751，863，937]第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟[]練習(xí)42Q,P,R,Y,S,XC,M,F,H,A,D,P,Q,R,2.

欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母升序重排，則初始步長(zhǎng)為4的希爾排序第一趟的結(jié)果是？答：原始序列：

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

shell一趟后：A,D,H,C,F,M,S,X,Y第一趟希爾排序結(jié)果：PACSQDFXRHMY練習(xí)3、設(shè)文件有10個(gè)記錄，其關(guān)鍵字值分別為:37,23,7,79,29,43,73,19,31,61,試給出冒泡排序法按非遞減的次序進(jìn)行排序過(guò)程中的每一趟結(jié)果序列。4、有一組鍵值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大進(jìn)行排序，請(qǐng)寫(xiě)出第一趟排序過(guò)程中鍵值的移動(dòng)情況。

5、已知有十個(gè)待排序的記錄，其關(guān)鍵字分別為：256，301，751，129，937,863，742，694，076，438請(qǐng)用快速排序的方法將它們從小到大排列。6、設(shè)待排序的記錄共7個(gè)，排序碼分別為8，3，2，5，9，1，6。

(1)寫(xiě)