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

第十章內(nèi)部排序主要內(nèi)容10.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較討論排序概念所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。NBA成績表；獎學金評定綜合分；？什么是排序？為什么排序？如何排序？內(nèi)部排序外部排序

將欲處理的數(shù)據(jù)整個存放到內(nèi)部存儲器中排序，數(shù)據(jù)可被隨機存取交換式排序選擇式排序插入式排序借助外部的輔助存儲器（比如：硬盤），由于數(shù)據(jù)是存在外存中，故數(shù)據(jù)不可隨機被存取

排序的分類歸并排序基數(shù)排序排序比較標準

空間復雜度時間復雜度穩(wěn)定性穩(wěn)定不穩(wěn)定

排序過后能使值相同的數(shù)據(jù)保持原順序中的相對位置排序過后不能使值相同的數(shù)據(jù)保持原順序493256492727324949562732494956基本操作大多數(shù)排序算法都有兩個基本的操作：比較兩個排序碼的大??；改變指向記錄的指針或移動記錄本身。

注意：

第(2)種基本操作的實現(xiàn)依賴于待排序記錄的存儲方式。

#defineMAXSIZE20 //一個用作示例的小順序表的最大長度typedefintKeyType;//定義關鍵字類型為整數(shù)類型typedefstruct{KeyTypekey; //關鍵字

InfoTypeotherinfo; //其它數(shù)據(jù)項}RedType; //記錄類型typedefstruct{RedTyper[MAXSIZE+1];

//r[0]賦閑或用作哨兵單元

intlength; //順序表長度}SqList;10.2插入排序直接插入排序折半插入排序2-路插入排序表插入排序希爾排序基本思想：順序地把待排序的數(shù)據(jù)元素按其值的大小插入到已排序數(shù)據(jù)元素子集合的適當位置有序序列無序序列一、直接插入排序12578630941256783094直接插入排序子集合的數(shù)據(jù)元素個數(shù)從只有一個數(shù)據(jù)元素開始逐次增大。當子集合大小等于原集合時排序完畢。直接插入排序[64]789624[564]89624[5764]624[576489]248957896初始序列:第一次排序:第二次排序:第三次排序:[5676489]24第四次排序:[5672464]第五次排序:Temp6j896476jjjvoidInsertSort(SqList&L){//對順序表L做直接插入排序

for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key))

{//將L.r[i]插入有序子表 L.r[0]=L.r[i]; for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; //記錄后移

L.r[j+1]=L.r[0];

//插入到正確位置

}}//InsertSort[576489]246第三次排序:Temp689647low6二、折半插入基本思想：在查找插入位置時，使用折半查找算法。mhigh]voidBInsertSort(SqList&L){//對順序表L做折半插入排序

for(i=2;i<=L.length;++i){ L.r[0]=L.r[i]; //將L.r[i]暫存到L.r[0] low=1;high=i-1; while(low<=high)//在r[low..hight]中折半查找有序插入的位置

{ m=(low+high)/2; if(LT(L.r[0].key,L.r[m].key)) high=m-1; else low=m+1; } //插入位置為hight+1

for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];

//記錄后移

L.r[high+1]=L.r[0];

//插入到正確位置

}}//BInsertSort三、2-路插入排序基本思想：增設同類型數(shù)組d,視為循環(huán)向量。以d[1]為中心，原數(shù)列中比d[1]小的往前插，比d[1]大的往后插。原數(shù)列：4938659776132749d數(shù)組：49d1firstfinal38first6597final76final13first27first9749final四、表插入排序#defineSIZE100 //靜態(tài)鏈表容量typedefstruct{RedTyperc; //記錄項

intnext; //指針項}SLNode; //表結點類型typedefstruct{SLNoder[SIZE];

//0號單元為表頭結點

intlength; //鏈表當前長度}SlinkListType; //靜態(tài)鏈表類型采用靜態(tài)鏈表結構，令r[0]為表頭結點，且r[0].rc.key為MAXINT（1）將r[0]和r[1]構成一個循環(huán)鏈表（2）將r[2]到r[n]依次插入循環(huán)鏈表key:4938659776132749表插入排序只得到一個有序鏈表，只能進行順序查找，不能隨機查找和折半查找。要進行折半查找，則需要重排記錄：順序掃描有序鏈表，將第i個結點移至數(shù)組的第i個分量中。設SlinkListTypeSL;第i個最小關鍵字的下標為p，（p的初值為r[0].next,要求p>i，否則依next繼續(xù)找p,因為前i-1個數(shù)的位置已調(diào)整好）

q=r[p].next;

互換r[p]和r[i];r[i].next=p;voidArrange(SlinkListType&SL){//根據(jù)靜態(tài)鏈表SL中各結點的指針調(diào)整記錄位置，

//使SL中的記錄按關鍵字非遞減有序順序排列

p=SL.r[0].next; //p指示第一個記錄的當前位置

for(i=1;i<SL.length;++i) //SL.r[1..i-1]中記錄已按關鍵字有序排列 //第i個記錄在SL中的當前位置應不小于i { while(p<i)

p=SL.r[p].next; //找到第i個記錄，并用p指示其在SL中的當前位置

q=SL.r[p].next; //q指示尚未調(diào)整的表尾

if(p!=i) { SL.r[p]SL.r[i]; //交換記錄，使第i個記錄到位

SL.r[i].next=p;

//指向被移走的記錄，以后可由while循環(huán)找回

} p=q;//指示尚未調(diào)整的表尾，為找第i+1個記錄做準備

}}//Arrange

基本思想：把待排序的數(shù)據(jù)元素分成若干個小組，對同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個數(shù)逐次縮小；當完成了所有數(shù)據(jù)元素都在一個組內(nèi)的排序后排序過程結束。希爾排序又稱作縮小增量排序。五、希爾排序增量序列為：5，3，149

38

65

977613

27

4913

27

49

977649

386513

27

49

97

76

49

386513

27

49

38

65

49

9776132738494965769712345678voidShellInsert(SqList&L,intdk){//對順序表L作一趟希爾插入排序.//本算法與一趟直接插入排序比較,作了以下修改

//1.前后記錄位置的增量是dk,而不是1//2.r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到

for(i=dk+1;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-dk].key))

//將L.r[i]插入有序增量子表

{ L.r[0]=L.r[i]; //暫存在L.r[0]

for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk) L.r[j+dk]=L.r[j]; //記錄后移，查找插入位置

L.r[j+dk]=L.r[0]; //插入

}}//ShellInsertvoidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]對順序表L作希爾排序

for(k=0;k<t;++t) ShellInsert(L,dlta[k]);//一趟增量為dalt[k]的插入排序}//ShellSort練習關鍵字為：503087512061908170897275653426增量序列為：

(9,5,3,1)一、起泡排序算法思想：設數(shù)組a中存放了n個數(shù)據(jù)元素，循環(huán)進行n-1趟如下的排序過程：依次比較相鄰兩個數(shù)據(jù)元素，若a[i]>a[i+1]，則交換兩個數(shù)據(jù)元素，否則不交換。當完成一趟交換以后，最大的元素將會出現(xiàn)在數(shù)組的最后一個位置。依次重復以上過程，當?shù)趎-1趟結束時，n個數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a[1]中，a[0]中放置了最小的數(shù)據(jù)元素。10.3快速排序起泡排序493865977613279797973849271376653849276513384927133849271338271376766549382713特點：1.n個數(shù)排序共需進行n-1趟比較2.第i趟共需要進行n-i次比較voidBubbleSort(SqList&L){ for(i=1;i<n;i++) { change=FALSE; for(j=1;j<n-i+1;j++) if(L.r[j].key>L.r[j+1].key) { change=TRUE; L.r[j]L.r[j+1]; }

if(!change)return; }}共進行n-1趟排序，共進行n(n-1)/2次比較T(n)=O(n2)二、快速排序算法思想：指定樞軸(通常為第一個記錄)通過一趟排序?qū)⒁詷休S為中心，把待排記錄分割為獨立的兩部分，使得左邊記錄的關鍵字小于樞軸值，右邊記錄的關鍵字大于樞軸值對左右兩部分記錄序列重復上述過程，依次類推，直到子序列中只剩下一個記錄或不含記錄為止。27381349769765494938659776132749i27386597761349

492738499776136549jiiijjijj2738139776496549ijiij27381376976549jj具體實現(xiàn)：

low=s;high=t;pivotkey=L.r[low].key;從high開始往前找第一個關鍵字小于pivotkey的記錄，與樞軸記錄交換從low開始往后找第一個關鍵字大于pivotkey的記錄，與樞軸記錄交換重復上述兩步直到low==high為止此時樞軸記錄所在的位置i=low=high273813497697654913

27

384965

76

97intpartition(SqList&L,intlow,inthigh){//交換順序表L中的子表L.r[low..high]的記錄,樞軸記錄到位,并返回其所在位置

//此時在它之前（后）的記錄均不大（小）于它

piovtkey=L.r[low].key; //用子表的第一個記錄作樞軸記錄

while(low<high) //從表的兩端交替地向中間掃描

{ while(low<high&&L.r[high].key>=piovtkey) --high; L.r[low]L.r[high]; //將比樞軸記錄小的記錄交換到低端

while(low<high&&L.r[low].key<=priotkey) ++low; L.r[low]L.r[high]; //將比樞軸記錄大的記錄交換到高端

} returnlow; //返回樞軸所在的位置}//Partitionintpartition(SqList&L,intlow,inthigh){//交換順序表L中的子表L.r[low..high]的記錄，樞軸記錄到位，

//并返回其所在位置。此時在它之前（后）的記錄均不大（?。┯谒?/p>

L.r[0]=L.r[low]; //用子表的第一個記錄作樞軸記錄

piovtkey=L.r[low].key; //樞軸記錄關鍵字

while(low<high) //從表的兩端交替地向中間掃描

{ while(low<high&&L.r[high].key>=pivotkey) --high; L.r[low]=L.r[high]; //將比樞軸記錄小的記錄交換到低端

while(low<high&&L.r[low].key<=pivotkey) ++low; L.r[high]=L.r[low]; //將比樞軸記錄大的記錄交換到高端

} L.r[low]=L.r[0]; //樞軸記錄到位

returnlow; //返回樞軸所在的位置}//PartitionvoidQsort(SqList&L,intlow,inthigh){//對順序表L中的子表L.r[low..high]作快速排序

if(low<high)//長度大于1 { pivotloc=Partition(L,low,high);

//將L.r[low..high]一分為二

Qsort(L,low,pivotloc-1);

//對低子表遞歸排序，pivotloc是樞軸位置

Qsort(L,pivotloc+1,high); //對高子表遞歸排序

}}//QsortvoidQuickSort(SqList&L){//對順序表L作快速排序

QSort(L,1,L.length);}//QuickSortT(n)=O(nlog2n)10.4選擇排序一、直接選擇排序基本思想：從待排序的數(shù)據(jù)元素集合中選取最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個數(shù)據(jù)元素交換位置；然后從不包括第一個位置上數(shù)據(jù)元素的集合中選取最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個數(shù)據(jù)元素交換位置；如此重復，直到數(shù)據(jù)元素集合中只剩一個數(shù)據(jù)元素為止。直接選擇排序149238365497576613727849ki=1jkjjjjkjjk1349直接選擇排序149238365497576613727849i=kjjjjjj1349kk2voidSelectSort(SqList&L){//對順序表L作簡單選擇排序

for(i=1;i<L.length;++i)//選擇第i個最小的記錄，并交換到位

{ j=SelectMinkey(L,i); //在L.r[i..L.length]中選擇key最小的記錄

if(i!=j)L.r[j]L.r[i];//與第i記錄交換

}}intSelectMinKey(SqListL,intk){//在L.r[k..L.length]中選擇key最小的記錄并返回它的位置

min=L.r[k].key; minp=k; for(i=k+1;i<=L.length;i++) if(L.r[i].key<min) { min=L.r[i].key; minp=i; } returnminp;}共進行n-1趟排序，n(n-1)/2次比較T(n)=O(n2)二、樹形選擇排序算法思想對n個記錄的關鍵字兩兩比較，共進行[n/2]次，如此重復直到最后找出最小記錄，此過程可以用有n個葉子的完全二叉樹表示；將葉子結點中最小關鍵字改為MAXINT，然后該葉子與其左/右兄弟關鍵字比較，依次修改從葉子到根的路徑上各結點的關鍵字值，則根結點為次小記錄；重復2，直到葉子結點均為MAXINT為止。2125492516086395a[0]a[1]162116166325212125492516Max6395MaxMax08080821250863210808a[2]2121Max63252121254925MaxMax639563a[3]252563Max632525Max254925MaxMax6395MaxMax161616a[4]252563Max6325MaxMaxMax4925MaxMax6395a[5]494963Max6349MaxMaxMax49MaxMaxMax6395MaxMaxa[6]63Max63Max63MaxMaxMaxMaxMaxMaxMaxMax6395a[7]95Max95Max95MaxMaxMaxMaxMaxMaxMaxMaxMax95Max

若用一個一維數(shù)組存放滿足此關系的序列，把這個一維數(shù)組看成是一棵完全二叉樹，則堆對應的完全二叉樹中所有非終端結點的值均大于或均小于其左右孩子的值。三、堆排序HeapSort堆的定義：n個元素的序列{K1，K2，，Kn}當且僅當滿足如下關系時稱為堆：

KiK2i

或KiK2iKiK2i+1KiK2i+1大頂堆大根堆堆排序方法：由一個無序的序列建成一個堆輸出堆頂?shù)淖钚≈凳Ｓ嗟脑亟ǔ梢粋€新的堆重復2和3093811962783小頂堆小根堆30854712243691534938659776132749輸出13后,用序列中最后一個記錄代替根結點篩選為堆頂元素與它的左右子樹根結點比較若右子樹根<左子樹根<堆頂根結點與右子樹根交換若左子樹根<右子樹根<堆頂根結點與左子樹根交換這個從堆頂?shù)饺~子的調(diào)整過程稱為篩選13384976972765499738497627654927384976496597對一個無序序列建立堆也是篩選過程,篩選從[n/2]個記錄開始。493865977613274976274913496538974997657649273813建立大頂堆493865764927971349766549382797134997657649273813497665493827971349276549387697134965274938769713496527493876971349132749387697651349274938769765134927493876976549132749387697654949273813769765494927381376976549132738497697654938271349769765建大頂堆，排序結果為從小到大493827134976976549273813497697654913382749769765typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){//已知H.r[s..m]中記錄的關鍵字除H.r[s].key外均滿足堆的定義，

//本函數(shù)調(diào)整H.r[s]的關鍵字，使H.r[s..m]成為一個大頂堆rc=H.r[s]; rc=h.r[s]; for(j=2*s;j<=m;j*=2) //沿key較大的孩子結點向下篩選

{ if(j<m&<(H.r[j].key,H.r[j+1].key)) ++j; //j為孩子中key較大的記錄的下標

if(GT(rc.key,H.r[j].key)) break; //篩選結束

H.r[s]=H.r[j]; s=j; } H.r[s]=rc; //rc應插入在位置s上}//HeapAdjustvoidHeapSort(HeapType&H){//對順序表H進行堆排序

for(i=H.length/2;i>0;--i)//把H.r[1..length]建成大頂堆

HeapAdjust(H,i,H.length); for(i=H.length;i>1;--i) { H.r[1]H.r[i]; //將堆頂記錄和當前未經(jīng)排序子序列

//H.r[1..i]中最后一個記錄相交換

HeapAdjust(H,1,i-1); //將H.r[1..i-1]重新調(diào)整為大頂堆

}}//HeapSortT(n)=O(nlog2n)10.5歸并排序基本思想：將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列;然后進行兩兩歸并，得到n/2個長度為2的有序序列;再進行兩兩歸并，得到n/4個長度為4的有序序列;不斷重復歸并直至得到一個長度為n的有序序列為止。歸并排序過程<初態(tài)>(49)(38)(65)(97)(76)(13)(27)(3849)<第2趟>(38496597)<第1趟>(6597)(1376)(27)<第3趟>(13273849657697)(132776)voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n] for(j=m+1,k=i;i<=m&&j<=n;++k)

//將SR中記錄由小到大地并入TR { ifLQ(SR[i].key,SR[j].key) TR[k]=SR[i++]; else TR[k]=SR[j++]; } if(i<=m) TR[k..n]=SR[i..m];//將剩余的SR[i..m]復制到TR if(j<=n) TR[k..n]=SR[j..n];//將剩余的SR[j..n]復制到TR}//MergevoidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){//將SR[s..t]歸并排序為TR1[s..t]

if(s==t) TR1[s]=SR[s]; else { m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1..t] Msort(SR,TR2,s,m,);

//遞歸地將SR[s..m]歸并為有序的TR2[s..m] Msort(SR,TR2,m+1,t);

//遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t] Merge(TR2,TR1,s,m,t);

//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t] }}//MsortvoidMergeSort(SqList&L){//對順序表L作歸并排序.

Msort(L.r,L.r,1,L.length);}//MergeSort10.6基數(shù)排序不通過關鍵字之間的比較進行排序一、多關鍵字排序最高位優(yōu)先法MSD：

先按關鍵字K0排序，將序列分成若干個子序列

每個子序列記錄的K0均相等然后在每個子序列中按K1排序按K1值把子序列分成更小的子序列

……………

直到最后按Kd-1排序后，整個序列有序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(1,3),(2,4),(2,3),(3,2),(3,4),(4,4),(4,3)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)最低位優(yōu)先法LSD：根據(jù)最次關鍵字Kd-1起對記錄排序再根據(jù)Kd-2對記錄排序。。。。。。根據(jù)K0對記錄排序后，

整個序列有序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)二、鏈式基數(shù)排序用分配和收集兩種操作對單關鍵字進行排序某些單關鍵字可以看成是若干個關鍵字復合而成,如多位數(shù)可以看成是由多個數(shù)字復合而成的。分配：

按關鍵字把不同的記錄送到不同的隊列中收集：按某種順序把不同隊列中的記錄集中起來排序思想基數(shù)排序是按組成關鍵字的各位的值進行分配和收集，與前面介紹的排序方法不同，它無需進行關鍵字之間的比較。設關鍵字有d位，每位的取值范圍為r(稱為基數(shù))，則需要進行d趟分配與收集，需要設立r個隊列。例如：關鍵字是4位字符串，需要26個隊列，4趟分配與收集；關鍵字3位十進制數(shù)，需要10個隊列，3趟分配與收集基數(shù)排序過程278—109—063—930—589—184—505—269—008—083f[0]f[1]f[2]f[3]

f[4]f[5]f[6]f[7]f[8]f[9]e[0]e[1]e[2]e[3]

e[4]e[5]e[6]e[7]e[