第7章排序§7.5歸并排序

歸并排序

將兩個(gè)已排序的子序列合并成一個(gè)有序序列。11324262152738AptrBptrCptrCptr

T

(N)=O(

)，

N

是元素個(gè)數(shù).N12

S

(N)=O(

)。N

方法是穩(wěn)定的。二路歸并。也可以使用多路歸并。voidMerge(ElementTypeA[],ElementTypeTmpA[],intLeft,intMid,intRight){/*將有序的A[Left]~A[Mid-1]和A[Mid]~A[Right]歸并成一個(gè)有序序列*/intTp,LeftEnd,i;

Tp=Left;/*有序序列的起始位置*/LeftEnd=Mid–1;/*左邊序列終止的位置*/while((Left<LeftEnd)&&(Mid<Right))

if(A[Left]<=A[Mid])TmpA[Tp++]=A[Left++];/*將左邊元素復(fù)制到TmpA*/

elseTmpA[Tp++]=A[Mid++];/*將右邊元素復(fù)制到TmpA*/while(Left<=LeftEnd)/*如果左邊有元素剩下而右邊已經(jīng)結(jié)束*/TmpA[Tp++]=A[Left++];/*將左邊剩余元素復(fù)制到TmpA*/while(Mid<=Right)/*如果右邊有元素剩下而左邊已經(jīng)結(jié)束*/TmpA[Tp++]=A[Mid++];/*將右邊剩余元素復(fù)制到TmpA*/for(i=Right-Left;i>=0;i--,Right--)A[Right]=TmpA[Right];/*將有序的TmpA[]復(fù)制回A[]*/}第7章排序§7.5歸并排序voidMSort(ElementTypeA[],ElementTypeTmpA[],

intLeft,intRight){intCenter;/*遞歸地將A[Left]~A[Right]排序*/

if(Left<Right){/*如果還有元素要排序*/ Center=(Left+Right)/2; MSort(A,TmpA,Left,Center);/*遞歸排左半邊T(N/2)*/ MSort(A,TmpA,Center+1,Right);/*遞歸排右半邊T(N/2)*/ Merge(A,TmpA,Left,Center+1,Right);/*歸并，O(N)*/}}voidMergesort(ElementTypeA[],intN){ElementType*TmpArray;/*需要O(N)輔助空間*/TmpArray=malloc(N*sizeof(ElementType));MSort(A,TmpArray,0,N-1);free(TmpA);}如果TmpA定義成Merge的局部變量，那么每次調(diào)用Merge都需要開(kāi)辟不同的空間,那么S(N)=O()NlogN第7章排序§7.5歸并排序

時(shí)間復(fù)雜性分析：T

(1

)=1T

(N)=2T(N/2

)+O(N)=2k

T(N/2k

)+k*O(N)=N*T(1

)+logN*O(N)=O(N+NlogN)

非遞歸的算法思想:A0123…………n4n3n2n1…………………………注意:

歸并排序需要線性的額外存儲(chǔ),并且經(jīng)常復(fù)制臨時(shí)數(shù)組導(dǎo)致效率降低。

它很少用于內(nèi)部排序，然而在外部排序中非常常用。第7章排序§7.5歸并排序

桶排序〖例〗假設(shè)有N個(gè)學(xué)生，每個(gè)人的成績(jī)分布在0到100(令M=101種可能的成績(jī)).如何在線性的時(shí)間內(nèi)按照成績(jī)給他們排序?count0110088算法思想：{

初始化鏈表頭數(shù)組count[];

while(讀一個(gè)學(xué)生的成績(jī))

把它插入鏈表count[stdnt.grade];

for(i=0;i<M;i++){

if(count[i])

輸出鏈表count[i];}}T(N,M)=O(M+N)M>>N

將會(huì)怎樣?第7章排序§7.6基數(shù)排序

“基數(shù)排序

(RadixSort)”是“桶排序

(BucketSort)”的推廣。

基數(shù)排序

基數(shù)排序：一般用于多關(guān)鍵字的排序第7章排序§7.6基數(shù)排序〖例〗

一疊牌的排序要基于兩個(gè)關(guān)鍵字。第一關(guān)鍵字[花色]<

<

<第一關(guān)鍵字[面值]2<3<4<5<6<7<8<9<10<J<Q<K<A排序結(jié)果應(yīng)該是:2...A2...A2...A2...A

基數(shù)排序的方法一般采用“主位優(yōu)先法”(MostSignificantDigitFirst,MSD)或者“次位優(yōu)先法”(LeastSignificantDigitFirst,LSD)相當(dāng)于“分治法”“分配-收集”法

主位優(yōu)先法(MSD)排序先排花色:比方,建立4個(gè)花色的“桶”3

3

5

5

A

A

4

4

再排面值:每個(gè)桶分別獨(dú)立排序(可以采用以前介紹的任何排序方法)

第7章排序§7.6基數(shù)排序先排面值:建立13個(gè)面值的“桶”，把牌放入相應(yīng)的桶中〔這叫“分配”〕；2

2

3

3

4

4

5

5

A

A

...

依次“收集”它們成為一疊牌；A

A

3

3

2

2

再排花色:建立4個(gè)桶進(jìn)行再“分配”；

次位優(yōu)先法(LSD)排序④

再次“收集”它們成為一疊牌即告完成。第7章排序§7.6基數(shù)排序還不趕緊拿一副牌出來(lái)試試？〖例〗給定

N=10個(gè)整數(shù)，范圍介于0到999(M

=1000)之間。是否可以在線性的時(shí)間內(nèi)把它們排序?

單關(guān)鍵字的基數(shù)排序輸入:64,8,216,512,27,729,0,1,343,1250桶：123456789〔3位數(shù)可以看成個(gè)3關(guān)鍵字，再按“次位優(yōu)先法”排序〕0輪次1151234364125216278729輪次20151234364125216278729輪次30185122161252772934364輸出:0,1,8,27,64,125,216,343,512,729時(shí)間復(fù)雜性：T=O(D(N+R))其中D是輪次,N

是元素個(gè)數(shù),R

是桶的數(shù)量.按“主位優(yōu)先法”排序?qū)?huì)怎樣?第7章排序§7.6基數(shù)排序空間復(fù)雜性：S=O(N+R),N

是元素個(gè)數(shù),R

是桶的數(shù)量.穩(wěn)定性：穩(wěn)定用鏈?zhǔn)絻?chǔ)存更便于分配與收集？typedefstructNode*PtrToNode;typedefPtrToNodeList;structNode{

intKey[MaxDigit];/*MaxDigit是關(guān)鍵字個(gè)數(shù),Key可以定義成char類型數(shù)組*/PtrToNodeNext;};ListRadixSort(ListA)/*基數(shù)排序*/{ListBucket[Radix]；/*建立Radix個(gè)桶*/ListRear[Radix];/*需要記錄每個(gè)桶鏈表的尾元素位置*/inti,j,Digit;for(i=MaxDigit-1;i>=0;i--){/*從最次位關(guān)鍵字開(kāi)始*/

for(j=0;j<Radix;j++)Bucket[j]=Rear[j]=NULL;/*初始化*/

while(A){/*將關(guān)鍵字逐一分配到桶*/Digit=A->Key[i];/*取出當(dāng)前關(guān)鍵字位*/

if(!Bucket[Digit])/*若對(duì)應(yīng)的桶是空的*/Bucket[Digit]=A;/*放入空桶*/

elseRear[Digit]->Next=A;/*否則放入桶尾*/Rear[Digit]=A;/*更新尾指針*/A=A->Next;}/*結(jié)束while分配過(guò)程*/

for(j=Radix-1;i>=0;j--){/*將所有桶中元素收集串聯(lián)*/

if(Bucket[j]){Rear[j]->Next=A;A=Bucket[j];}}/*結(jié)束for收集過(guò)程*/}returnA;}第7章排序§7.7外部排序*

外部排序*(ExternalSort)

內(nèi)部排序和外部排序分兩個(gè)步實(shí)施：(a)分段內(nèi)排序(b)歸并〔二路或多路〕磁盤內(nèi)存有序有序磁盤內(nèi)存有序有序周轉(zhuǎn)盤輸入塊輸出塊

要提高外排的效率，關(guān)鍵要解決以下4個(gè)問(wèn)題：

如何減少歸并輪數(shù)；

如何有效安排內(nèi)存中的輸入、輸出塊，使得機(jī)器的并行處理能力被最大限度地利用；

如何有效生成歸并段；

如何將歸并段進(jìn)行有效歸并。第7章排序§7.8排序總結(jié)排序方法平均時(shí)間復(fù)雜度最壞情況下時(shí)間復(fù)雜度額外空間復(fù)雜度穩(wěn)定性簡(jiǎn)單選擇排序O(N2)O(N2)O(1)不穩(wěn)定直接插入排序O(N2)O(N2)O(1)穩(wěn)定冒泡排序O(N2)O(N2)O(1)穩(wěn)