第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.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

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

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

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

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

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

KeyTypekey;

//關(guān)鍵字

InfoTypeotherinfo;

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

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

RecordTyper[MAXSIZE+1];

//存儲順序表的向量

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

intlength;

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

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

（4）希爾排序

每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。6.2.1直接插入排序6直接插入排序是最簡單的排序方法新元素插入到哪里？在已形成的有序表中線性查找，并在適當位置插入，把原來位置上的元素向后順移。6.2.1直接插入排序7例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列。【13】,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），

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

O(n2)——因為在最壞情況下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動元素的次數(shù)?？臻g效率：O（1）——因為僅占用1個緩沖單元算法的穩(wěn)定性：穩(wěn)定——因為25*排序后仍然在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）排序（又稱縮小增量排序）10基本思想先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。技巧

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

的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，dk

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

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

（1）冒泡排序

（2）快速排序交換排序的基本思想是：6.3.1冒泡排序13基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實現(xiàn)過程。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;//交換標志

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

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

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

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

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

}}6.3.2快速排序15

從待排序列中任取一個元素(例如取第一個)作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。此時便為有序序列了?；舅枷耄豪?：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。(設(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}，分別對{08，16}和{25*，49，25}進行快速排序?qū)08，16}

進行快速排序

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

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;//取支點的關(guān)鍵碼存入pivotkey變量while(i<j){

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

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

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

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

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

if(i<j){

pivot=Partition(L,i,j);

QSort(L,i,pivot-1);

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

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

（1）簡單選擇排序

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

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]交換位置簡單選擇排序的算法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個記錄交換6.4.2堆排序241.什么是堆？堆的定義：設(shè)有n個元素的序列k1，k2，…，kn，當且僅當滿足下述關(guān)系之一時，稱之為堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

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

??！注：終端結(jié)點（即葉子）沒有任何子女，無需單獨調(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)當向下比較??！3.怎樣進行堆排序？27關(guān)鍵：將堆的當前頂點輸出后，如何將剩余序列重新調(diào)整為堆？方法：將當前頂點與堆尾記錄交換，然后仿建堆動作，從上至下新調(diào)整，如此反復(fù)直至排序結(jié)束。例：對剛才建好的大根堆進行排序28刪除49交換1號與6號記錄492525*211608123456初始最大堆2525*1621136542084929刪除25交換1號與5號記錄從1號到5號重新調(diào)整為最大堆082525*2116491234561625*08252149136542082525*08從1號到4號重新調(diào)整為最大堆25*16082125491234566.5歸并排序30歸并排序的基本思想是：將兩個（或以上）的有序表組成新的有序表。更實際的意義：可以把一個長度為n的無序序列看成是n個長度為1的有序子序列，首先做兩兩歸并，得到n/2個長度為2的子序列；再做兩兩歸并，…，如此重復(fù)，直到最后得到一個長度為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），請給出歸并排序的具體實現(xiàn)過程。6.6基數(shù)排序32要討論的問題：1.什么是“多關(guān)鍵字”排序？實現(xiàn)方法？2.單邏輯關(guān)鍵字怎樣“按位值”排序？基數(shù)排序的基本思想是：借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序。即：用關(guān)鍵字不同的位值進行排序。1.什么是“多關(guān)鍵字”排序？實現(xiàn)方法？33例1：對一副撲克牌該如何排序？

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

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

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

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

的單關(guān)鍵碼Ki

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

(1

jd)

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

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

j

d)有radix種取值，則稱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排序方法稱為：36例：初始關(guān)鍵字序列T=（32,13,27,32*,19，33），請分別用MSD和LSD進行排序。法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ù)排序用鏈隊列來實現(xiàn)基數(shù)排序—鏈式基數(shù)排序2.單邏輯關(guān)鍵字怎樣“按位值”排序？37例:請實現(xiàn)以下關(guā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開始排序，f[]

是隊首指針，e[]

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

鏈接到下一非空隊首指針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第二趟收集（讓隊尾指針e[i]

鏈接到下一非空隊首指針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）第三趟收集（讓隊尾指針e[i]

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

）530790921101614485215306637738r[0]→r[0]→各種內(nèi)部排序方法的比較40排序方法最好情況平均時間最壞情況輔助存儲穩(wě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)定簡單選擇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）為例，寫出執(zhí)行直接插入排序的各趟排序過程。原始序列：

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)鍵碼按字母升序重排，則初始步長為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個記錄，其關(guān)鍵字值分別為:37,23,7,79,29,43,73,19,31,61,試給出冒泡排序法按非遞減的次序進行排序過程中的每一趟結(jié)果序列。4、有一組鍵值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大進行排序，請寫出第一趟排序過程中鍵值的移動情況。

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

(1)寫