9.1排序的基本概念9.2插入類排序9.3交換類排序法9.4選擇類排序法9.5歸并排序9.6分配類排序9.7各種排序方法的綜合比較第九章內(nèi)部排序9.8總結(jié)與提高一、排序的定義排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將如下序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,979.1排序的基本概念設(shè)含n個(gè)記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}記錄關(guān)鍵字相互之間可以進(jìn)行比較，即存在關(guān)系：Kp1≤Kp2≤…≤Kpn按此關(guān)系將上述記錄序列調(diào)整為

{Rp1,Rp2,

…，Rpn}的操作稱作排序。定義：

設(shè)待排序記錄序列中有關(guān)鍵字相等的記錄,即ki=kj(i<>j),且在排序前Ri領(lǐng)先于Rj.

若排序后可以保證Ri仍領(lǐng)先于Rj,

則所用的排序方法稱為穩(wěn)定的;

若排序后不能保證Ri仍領(lǐng)先于Rj,

則所用的排序方法稱為不穩(wěn)定的.二、穩(wěn)定的排序和不穩(wěn)定的排序例如：

排序前

(56,34,47,23,66,18,82,

47)若排序后必有結(jié)果：

(18,23,34,47,47,56,66,82)則稱該排序方法是穩(wěn)定的;若排序后可能得結(jié)果：

(18,23,34,47,47,56,66,82)則稱該排序方法是不穩(wěn)定的。若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題為內(nèi)部排序。

反之,若參加排序的記錄數(shù)量很大,整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類排序問(wèn)題為外部排序。三、內(nèi)部排序和外部排序1、順序存儲(chǔ)：移動(dòng)記錄實(shí)現(xiàn)排序；2、(靜態(tài))鏈表：修改指針(游標(biāo))實(shí)現(xiàn)排序；3、地址向量：移動(dòng)地址實(shí)現(xiàn)排序；

(又稱地址排序)四、內(nèi)部排序的存儲(chǔ)方式

本課程我們重點(diǎn)討論在順序存儲(chǔ)結(jié)構(gòu)上，各種排序方法的實(shí)現(xiàn)。9.2插入類排序

將無(wú)序序列中的記錄一個(gè)一個(gè)的“插入”到有序序列中的恰當(dāng)位置，以逐漸增加有序序列的長(zhǎng)度K(K=1N),從而實(shí)現(xiàn)排序。基本思想：有序序列r[1..i-1]r[i]無(wú)序序列r[i..n]有序序列r[1..i]無(wú)序序列r[i+1..n]找位置插入一趟插入排序的基本過(guò)程：實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．插入：將r[i]插入(復(fù)制)到r[j+1]的位置上。2．后移：將r[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．查找插入位置：在r[1..i-1]中查找r[i]的插入位置j+1：

r[1..j].keyr[i].key<r[j+1..i-1].key；直接插入排序（基于順序查找）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）

利用“順序查找”實(shí)現(xiàn)“在r[1..i-1]中查找r[i]的插入位置”算法的實(shí)現(xiàn)：一、直接插入排序1.從r[i-1]起向前進(jìn)行順序查找，循環(huán)結(jié)束確定r[i]的插入位置為j+1;r[0]jr[i]j=i-1插入位置2.

將所有j+1…i-1

的記錄向后移動(dòng)1位;jjj3.將r[0](原r[i])“插入”到j(luò)+1的位置。監(jiān)視哨設(shè)置在r[0]；

可以在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；r[0]=r[i];j=i-1;

while(r[0].key<r[j].key)

{r[j+1]=r[j];j=j-1;}r[0]jr[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置方法的改進(jìn):令i=2,3,…,n,可實(shí)現(xiàn)整個(gè)序列的排序。Voidinssort(recordtyper[],intn){for（i=2;i<=n;i++){r[0]=r[i];j=i-1;

while(r[0].key<r[j].key)

{r[j+1]=r[j];j=j-1;}

r[j+1]=r[0];}}算法：穩(wěn)定？實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)：（2）“移動(dòng)”記錄。（1）“比較”序列中兩個(gè)關(guān)鍵字的大小；時(shí)間復(fù)雜度分析：對(duì)于直接插入排序：最好的情況(關(guān)鍵字在記錄序列中順序有序):“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：2(n-1)“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：?1=n-1ni=2?(i)=ni=2(n+2)(n-1)2?(i+1)=ni=2(n+4)(n-1)2

所以，時(shí)間復(fù)雜度為O(n2)

因?yàn)閞[1..i-1]是一個(gè)按關(guān)鍵字有序的序列,則可以利用折半查找實(shí)現(xiàn)在“r[1..i-1]中查找r[i]的插入位置”,如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉Ｋ荒軠p少查找的次數(shù)不能減少移動(dòng)的次數(shù),因此與查找后移同時(shí)實(shí)現(xiàn)的直接插入排序比較,改進(jìn)不大。算法見:p302，自學(xué)！二、折半插入排序ilowhighmmlowlowhighilowhighmhighmhighmlow例如:再如:插入位置插入位置14364952805861239775L.r14364952586180239775L.rm

由于插入排序的效率取決于:記錄的個(gè)數(shù)及記錄的原始序；

“宏觀”調(diào)整：先“跳躍式”的分組進(jìn)行排序,使得整個(gè)序列“基本有序”。(每組記錄少)

“微觀”調(diào)整：在整個(gè)序列“基本有序”后,再進(jìn)行直接插入排序使整個(gè)序列“完全有序”。（記錄的原始序優(yōu)）三、希爾排序(縮小增量排序)

所以希爾排序的基本思想為：對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。將記錄序列跳躍式的分成若干組，分別對(duì)每組進(jìn)行插入排序，組數(shù)不斷減少，最后僅剩一組。其中,d

稱為增量,它的值在排序過(guò)程中從大到小逐漸縮小,直至最后一趟排序減為

1.

例如：將n個(gè)記錄{r[1],r[2]…r[d],r[1+d],r[2+d]…r[2d],r[1+2d]…r[n]}

分成d個(gè)子序列：{r[1]，r[1+d]，r[1+2d]，…,r[1+kd]…}{

r[2]，r[2+d]，r[2+2d]，…,r[2+kd]…}…{r[d],r[2d],r[3d],…,r[(k+1)d]}具體做法：例如：162512304711233691831

第一趟希爾排序，設(shè)增量d=51123

12

9

181625

36

30

4731

第二趟希爾排序，設(shè)增量d=3918

121123

162531

304736第三趟希爾排序，設(shè)增量d=1

911121618232530313647Voidshellinsert(recordtyper[],intlength,intd)

{for(i=1+d;i<=length;i++)if(r[i].key<r[i-d].key)

{r[0]=r[i];/*是監(jiān)視哨嗎？*/for(j=i-d;j>0&&r[0].key<r[j].key;j-=d)r[j+d]=r[j];r[j+d]=r[0];}}Voidshellsord(recordtyper[],intlength,intd[],intn)

{for(i=0;i<=n-1,++i)shellinsert(r,length,d[i]);}算法：穩(wěn)定？

希爾排序的時(shí)間復(fù)雜度分析是一個(gè)數(shù)學(xué)上尚未解決的難題。增量序列d[1..t]的設(shè)計(jì)至關(guān)重要，目前沒(méi)有統(tǒng)一定論，以經(jīng)驗(yàn)為主。逆轉(zhuǎn)數(shù)：對(duì)于待排序序列中的某個(gè)記錄的關(guān)鍵字，它的逆轉(zhuǎn)數(shù)是指在它之前比此關(guān)鍵字大的關(guān)鍵字的個(gè)數(shù)。直接插入排序：一次移動(dòng)只能減少一個(gè)逆序數(shù)。逆轉(zhuǎn)數(shù)之和就是排序所需要移動(dòng)的記錄的次數(shù)。希爾排序：一次移動(dòng)后減少的逆轉(zhuǎn)數(shù)不止一個(gè)。希爾排序的時(shí)間復(fù)雜度為O(n1.5).372512304711233691831

例：d=5,3,1,對(duì)如下記錄進(jìn)行排序KiKjKjKi設(shè)比較位置如下圖所示，此時(shí)：Ki>Kj交換后如下圖：可以確定交換位置之前，之后的關(guān)鍵字的逆轉(zhuǎn)數(shù)不變化。僅交換位置以及其間的關(guān)鍵字的逆轉(zhuǎn)數(shù)發(fā)生變化。假設(shè)：Ki和Kj之間：關(guān)鍵字值大于Ki的記錄有M個(gè)

關(guān)鍵字值小于Kj的記錄有N個(gè)

關(guān)鍵字值介于Kj和Ki之間的記錄有L個(gè)則：關(guān)鍵字值大于Ki和小于Kj的記錄，其逆轉(zhuǎn)數(shù)不變；關(guān)鍵字值介于Kj和Ki之間的記錄，其逆轉(zhuǎn)數(shù)減1；Ki的逆轉(zhuǎn)數(shù)增加M;Kj的逆轉(zhuǎn)數(shù)減少（L+M+1）;逆轉(zhuǎn)數(shù)總和將減少2L+1.9.3交換類排序法一、起泡排序二、快速排序三、快速排序的時(shí)間分析

假設(shè)在排序過(guò)程中，記錄序列r[1..n]的狀態(tài)為：一趟起泡排序無(wú)序序列r[1..i]有序序列r[i+1..n]i無(wú)序序列r[1..i-1]有序序列r[i..n]對(duì)無(wú)序序列，比較(交換)相鄰記錄，可將關(guān)鍵字最大的記錄交換到i的位置上有序序列大于無(wú)序序列一、起泡排序算法一：voidbubblesort(recordtyper[],intlength);{n=length;change=true;

for(i=n;i>1&&change;--i)

{change=false;

change=true;

}}for(j=1;j<i;++j)if(r[j+1].key<r[j].key)

{x=r[j];r[j]=r[j+1];r[j+1]=x;}穩(wěn)定？算法二：voidbubblesort(recordtyper[],intn);

{i=n;

while(i>1)

{

laste=1;for(j=1;j<i;j++)if(r[j+1].key<r[j].key)

{x=r[j];r[j]=r[j+1];r[j+1]=x;

laste=j;

}{記下進(jìn)行交換的記錄位置}

i=laste;

{本趟最后一次進(jìn)行交換的記錄位置}

}}5231978注意:2.算法一每經(jīng)過(guò)一趟“起泡”則“i減1”，

但算法二并不是每趟如此。例如:2553157989i=7i=613i=21.起泡排序的結(jié)束條件為，

最后一趟沒(méi)有進(jìn)行“交換記錄”。lastelaste1132最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進(jìn)行一趟起泡“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進(jìn)行n-1趟起泡“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：n-1?(i

-1)=ni=2n

(n-1)23?(i

-1)=ni=23n

(n-1)2

所以，時(shí)間復(fù)雜度為O(n2)時(shí)間分析:

起泡排序一趟之后，使最大的記錄定位到最后,如果一趟之后可使某記錄(任意)定位在它應(yīng)處的位置(在有序序列中),而將其余的無(wú)序序列以它為樞軸,分成兩部分,比它小的放在它的前面,比它大的的放在它的后面,下一趟分別對(duì)前后的子序列排序,顯然可加快速度。這就是快速排序二、快速排序

目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無(wú)序序列r[s..t]將分割成兩部分：r[s..i-1]和r[i+1..t]，且

r[j].key≤r[i].key≤r[j].key(s≤j≤i-1)

樞軸

(i+1≤j≤t)。一趟快速排序（一次劃分）lowhigh設(shè)r[s]=52為樞軸

將r[high].key和樞軸的關(guān)鍵字進(jìn)行比較，要求r[high].key≥

樞軸的關(guān)鍵字

將r[low].key和樞軸的關(guān)鍵字進(jìn)行比較，要求r[low].key≤

樞軸的關(guān)鍵字highlowhighlow52498036145861972375str[s]52highhighhighlowlow23801452例如可見，經(jīng)過(guò)“一次劃分”，將關(guān)鍵字序列

52,49,80,36,14,58,61,97,23,75變?yōu)?23,49,14,36,(52)58,61,97,80,75

在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針：low

和high，它們的初值分別為：s和t，

之后逐漸減小high，增加low，并保證

r[high].key≥52，和r[low].key≤52,否則進(jìn)行記錄的“交換”(實(shí)際只需賦值)。一趟快速排序算法intQKpass(recordtyper[],ints,intt)/*本算法對(duì)r[s..t]進(jìn)行一趟快速排序*/

{x=r[s];i=s;j=t;

while(i<j)

/*low用i表示,high用j表示*/{while(i<j)&&(r[j].key>=x.key)j=j-1;r[i]=r[j];

while(i<j)&&(r[i].key<=x.key)i=i+1;r[j]=r[i];

}r[i]=x;returni;}

首先對(duì)無(wú)序的序列進(jìn)行“一次劃分”,之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。無(wú)序的記錄序列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸一次劃分分別進(jìn)行快速排序快速排序過(guò)程voidQKsort(recordtyper[],intlow,inthigh);

/*對(duì)記錄序列r[low..high]進(jìn)行快速排序*/

{if(low<high){pos=QKpass(r,low,high);

/*對(duì)r[low..high]進(jìn)行一趟劃分,pos為樞軸*/

QKsort(r,low,pos-1);

/*對(duì)低子序列遞歸排序*/

QKsort(r,pos+1,high);

/*對(duì)高子序列遞歸排序*/

}}快速排序算法穩(wěn)定？假設(shè)一次劃分所得樞軸位置i=k，則對(duì)n個(gè)記錄進(jìn)行快速排序所需時(shí)間：其中Tpass(n)為對(duì)n個(gè)記錄進(jìn)行一次劃分所需時(shí)間。

若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則k

取1至n

中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)三、快速排序的時(shí)間分析設(shè)Tavg(0)≤b,Tavg(1)≤b,c,b為常數(shù)則用數(shù)學(xué)歸納法可證明：Tavg(n)≤2

n

(b+c)

ln

(n)結(jié)論:快速排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排序所需時(shí)間的平均值為：Tavg(n)=cn+?[Tavg(k-1)+Tavg(n-k)]nk=1n1=cn+

?Tavg(i)n-1i=1n2

若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判颍鋾r(shí)間復(fù)雜度為O(n2)。

為避免出現(xiàn)這種情況，需在第一次劃分之前，進(jìn)行“予處理”，即：

先對(duì)r[s].key,r[t].key和r[

(s+t)/2].key進(jìn)行相互比較，然后取關(guān)鍵字為“中間”

的記錄為樞軸記錄。9.4選擇類排序法一、簡(jiǎn)單選擇排序二、樹形選擇排序三、堆排序一、簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中,待排記錄序列的狀態(tài)為：有序序列r[1..i-1]無(wú)序序列r[i..n]

第i趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的記錄有序序列r[1..i]無(wú)序序列

r[i+1..n]有序序列小于無(wú)序序列簡(jiǎn)單選擇排序算法voidSelectSort(RecordTyper[],intlength){n=length;for(i=1;i<=n－1;++i){k=i；

for(j=i+1;j<=n;++j)if(r[j].key<r[k].key)k=j；

if(k!=i){x=r[i]；r[i]=r[k]；r[k]=x;}}}穩(wěn)定？時(shí)間性能分析

對(duì)n個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)總計(jì)為：移動(dòng)記錄的次數(shù)：最小值為0

最大值為3(n-1)。二、樹形選擇排序

是一種按錦標(biāo)賽的思想進(jìn)行排序的方法。選擇時(shí)兩兩比較,第一輪小者為勝者再進(jìn)行第二輪比較,逐層向上直到比出冠軍為最小者。比較的過(guò)程是一個(gè)二叉樹結(jié)構(gòu),其中記錄了互相之間的比較結(jié)果,利用此結(jié)果再比較很快會(huì)得到第二第三…。01

02

03

04

05

06

07

0801

03

05

06010501

按錦標(biāo)賽規(guī)則，05將成為亞軍，顯然不合理。解決的方法是在01奪冠之后，01退出，01參加過(guò)的比賽重新進(jìn)行（再篩選）。020202如此，第二、第三…各名次的結(jié)果才真實(shí)、合理。

由此，引出堆排序方法(空間、時(shí)間效率更高)三、堆排序堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:(小頂堆)(大頂堆)rir2i

r2i+1

可將該數(shù)列視作按層次存儲(chǔ)的完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。例如:3412362765498173554098{12,36,27,65,40,34,98,81,73,55,49}是堆是小頂堆不14{12,36,27,65,40,14,98,81,73,55,49}不是堆

可利用堆的特性(首元素最小或最大)對(duì)記錄序列進(jìn)行排序！堆排序的特征

堆排序是在排序過(guò)程中，將向量中存儲(chǔ)的數(shù)據(jù)看成一棵完全二叉樹,利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇關(guān)鍵字最小的記錄，即待排序記錄仍采用向量數(shù)組方式存儲(chǔ)，并非采用樹的存儲(chǔ)結(jié)構(gòu)，僅僅是采用完全二叉樹順序結(jié)構(gòu)的特征進(jìn)行分析處理。

堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法,過(guò)程如下：1、對(duì)給定序列建堆；2、輸出堆頂；(首元素與尾元素交換)3、對(duì)剩余元素重建堆；(篩選首元素)4、重復(fù)2，3，直至所有元素輸出。1、如何由一個(gè)無(wú)序序列“建堆”？問(wèn)題:2、輸出堆頂后如何“重建堆”

？?jī)蓚€(gè)問(wèn)題均可歸結(jié)為“篩選”問(wèn)題？建大頂堆{98,81,49,73,36,27,40,55,64,12}{12,81,49,73,36,27,40,55,64,98}交換98

和12重新調(diào)整為大頂堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}經(jīng)過(guò)篩選

繼續(xù)重復(fù)，可的有序序列。{12,73,49,64,36,27,40,55,81,98}交換81

和12例如：

所謂“篩選”指的是，對(duì)一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆。堆堆篩選814973556412362740是大頂堆但98和12互換后(去掉98),不為堆。因此，需要對(duì)它進(jìn)行“篩選”(調(diào)整12)。981298比較比較981281736412建初堆也是一個(gè)“篩選”的過(guò)程！例如:

建初堆是從最后一個(gè)有孩子的結(jié)點(diǎn)開始，往前逐個(gè)結(jié)點(diǎn)進(jìn)行“篩選”的過(guò)程。40554973816436122798例如給定的關(guān)鍵字序列為:40,55,49,73,12,27,98,81,64,36123681734998817355

現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹是個(gè)“堆”即可。98494064361227篩選算法voidsift（RecordTyper[],intｋ，intｍ）

/*調(diào)整r[k]，使整個(gè)序列r[k..m]滿足堆的性質(zhì)*/{t=r[k]；x=r[k].key；

i=k；j=2*i；finished=FALSE；

while(j<=m&&!finished)

{if(j<m&&r[j].key<r[j+1].key)j=j+1；

if(x>=r[j].key)finished=TRUE；

/*篩選完畢*/

else{r[i]=r[j]；i=j；j=2*i；}

/*繼續(xù)篩選*/

}r[i]=t;/*r[k]填入到恰當(dāng)?shù)奈恢?/

}

建初堆算法voidcrt_heap(RecordTyper[],intlength)

/*對(duì)記錄數(shù)組r建堆，length為數(shù)組的長(zhǎng)度*/{n=length;for(i=n/2;i>=1;--i)sift(r，i，n)；

}穩(wěn)定？堆排序算法voidHeapSort（RecordTyper[],intlength）

/*對(duì)r[1..n]進(jìn)行堆排序*/

{crt_heap(r,length)；n=length;for(i=n;i>=2;--i){b=r[1];r[1]=r[i];r[i]=b;

/*將堆頂記錄和堆中最后一個(gè)記錄互換*/

sift(r，1，i-1)；/*進(jìn)行篩選,使r[1..i-1]成為堆*/

}}堆排序時(shí)間復(fù)雜度分析：1.對(duì)深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3.重建堆

n-1

次，所需進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò)：(n-1)*2

log2n;

因此，堆排序的時(shí)間復(fù)雜度為(最壞情況):O(n*

log2n

+

(n-1)*2

log2n)=O(nlogn)。2.n

個(gè)關(guān)鍵字的堆深度為

log2n+1,初建堆所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為：n*

log2n;9.5歸并排序

歸并排序的過(guò)程基于下列基本思想進(jìn)行：

將兩個(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的有序子序列歸并為一個(gè)有序的序列。有序序列r[l..n]有序子序列r[l..m]有序子序列r[m+1..n]這個(gè)操作對(duì)順序表而言，是輕而易舉的。歸并例：(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13,19,27)(01,16,26,31)(01,05,13,16,19,26,27,31)52,23,80,36,68,14[52,23,80][36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]完整的歸并排序過(guò)程為：先分組再歸并。合并算法voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper[])

/*r1[low..mid]和r1[mid+1..high]分別有序，將它們合并*/{i=low；j=mid+1；k=low；

while((i<=mid)&&(j<=high)){if(r1[i].key<=r1[j].key){r[k]=r1[i]；++i；}

else

{r[k]=r1[j]；++j；}++k；}if(i<=mid)r[k..high]=r1[i..mid]；

if(j<=high)r[k..high]=r1[j..high]；

}2-路歸并排序算法voidMergeSort(RecordTyper1[],intlow,inthigh,RecordTyper[])

/*r1[low..high]經(jīng)排序后放在r[low..high]中,r2[low..high]為輔助空間*/

{RecordTyper2[hight-low+1]；

if(low==high)r[low]=r1[low]；

else{mid=(low+high)/2；

MergeSort(r1，low，mid,r2)；

MergeSort(r1，mid+1，high,r2)；

Merge(r2，low，mid，high，r)；}}穩(wěn)定？歸并排序的復(fù)雜度分析：容易看出，對(duì)n個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為Ο(nlogn)。即：每一趟歸并的時(shí)間復(fù)雜度為O(n)，總共需進(jìn)行

log2n

趟。

歸并排序的空間復(fù)雜度較高，需要有長(zhǎng)度為n的輔助數(shù)組，即為O(n)。9.6分配類排序

基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序基數(shù)排序

n

個(gè)記錄的序列{R1,R2,…，Rn}對(duì)關(guān)鍵字(Ki0,Ki1,…,Kid-1)有序是指：

其中:K0被稱為“最主/最高”位關(guān)鍵字Kd-1被稱為“最次/最低”位關(guān)鍵字

對(duì)于序列中任意兩個(gè)記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關(guān)系：

(Ki0,Ki1,

…,Kid-1)<(Kj0,Kj1,

…,Kjd-1)一、多關(guān)鍵字的排序

實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種方法:最低位優(yōu)先LSD法最高位優(yōu)先MSD法以撲克牌排序?yàn)槔?

將撲克牌的排序看成由花色和面值兩個(gè)關(guān)鍵字進(jìn)行排序的問(wèn)題。若規(guī)定花色和面值的順序如下：花色：梅花★<方塊◆<紅桃●<黑桃▲；面值：A<2<3<…<10<J<Q<K；花色的優(yōu)先級(jí)高于面值；則一副牌從小到大的順序?yàn)椋?/p>

★A,★2,…,★K；◆A,◆2,…,◆K；

●A,●2,…,●K；▲A,▲2,…,▲K。撲克牌的排序過(guò)程

訪法一(LSD)：

訪法二(MSD)：

先按K0進(jìn)行排序，并按K0的不同值將記錄序列分成若干子序列，之后再分別按K1進(jìn)行排序，...…，依次類推,直至最后分別按最次位關(guān)鍵字Kd-1排序完成為止。最高位優(yōu)先MSD法：

先按Kd-1進(jìn)行排序，然后按Kd-2進(jìn)行穩(wěn)定的排序，依次類推，直至按最主位關(guān)鍵字K0排序完成為止。

LSD排序過(guò)程中不需要根據(jù)“前一個(gè)”關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(gè)子序列。最低位優(yōu)先LSD法：

例:學(xué)生記錄含三個(gè)關(guān)鍵字:系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。

無(wú)序序列對(duì)K2排序?qū)1排序?qū)0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序過(guò)程如下:二、基數(shù)排序當(dāng)每個(gè)關(guān)鍵字的取值范圍相同時(shí)，其排序可采用“分配”而非“比較”的方法進(jìn)行。對(duì)于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，而此時(shí)每個(gè)“關(guān)鍵字”的取值范圍是原關(guān)鍵字的基數(shù)。

對(duì)于數(shù)字型或字符型的“多關(guān)鍵字”

,可用LSD法，并采用

“分配-收集”再“分配-收集”…的辦法實(shí)現(xiàn)排序,這就是基數(shù)排序。例如：對(duì)下列這組關(guān)鍵字

{369，367，167，239，237，138，230，139}

首先按其“個(gè)位數(shù)”取值“分配”成10組，之后按從0至9的順序?qū)⒏鹘M“收集”在一起；

然后按其“十位數(shù)”取值“分配”成10組，之后再按從0至9的順序?qū)⒏鹘M“收集”

起來(lái)；

最后按其“百位數(shù)”

取值“分配”成10組，之后再按從0至9的順序?qū)⒏鹘M“收集”

起來(lái)。

實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，可采用鏈表作存儲(chǔ)結(jié)構(gòu)。１．待排序記錄以鏈表為存儲(chǔ)結(jié)構(gòu)；２．“分配”時(shí)，按當(dāng)前“關(guān)鍵字位”將記錄分配到不同的“鏈隊(duì)列”中，每個(gè)隊(duì)列中記錄的當(dāng)前“關(guān)鍵字位”相同；３．“收集”時(shí)，將各隊(duì)列按關(guān)鍵字從小到大首尾相鏈構(gòu)成一個(gè)新鏈表;４．按LSD對(duì)每個(gè)關(guān)鍵字位重復(fù)2、3,便可獲得有序序列。具體方法：p→369→367→167→239→237→138→230→139進(jìn)行第一次分配進(jìn)行第一次收集p→230→230←→367←→167→237→367→167→237→138→369→239→139→369←→239→139→138←f[0]r[0]f[7]r[7]f[8]r[8]f[9]r[9]…例如：進(jìn)行第二次分配p→230→237→138→239→139p→230→367→167→237→138→369→239→139→230←→237→138→239→139→367←→167→369→367→167→369進(jìn)行第二次收集f[3]r[3]f[6]r[6]…

進(jìn)行第三次收集p→230→237→138→239→139→367→167→369進(jìn)行第三次分配→138←→139→167→230←→237→239→367←→369p→138→139→167→230→237→239→367→369已得到記錄的有序序列f[1]r[1]f[2]r[2]f[3]r[3]…存儲(chǔ)結(jié)構(gòu)：

為有效地存儲(chǔ)和重排記錄，算法采用靜態(tài)鏈表，有關(guān)數(shù)據(jù)類型的定義如下：#defineRADIX10#defineKEY_SIZE6#defineLIST_SIZE20typedefintKeyType;typedefstruct{ KeyTypekeys[KEY_SIZE];/*子關(guān)鍵字?jǐn)?shù)組*/ OtherTypeother_data;/*其它數(shù)據(jù)項(xiàng)*/

intnext;/*靜態(tài)鏈域*/ }RecordType1;typedefstruct{RecordType1r[LIST_SIZE+1];/*r[0]為頭結(jié)點(diǎn)*/ intlength; intkeynum;}SLinkList;/*靜態(tài)鏈表*/typedefintPVector[RADIX];

分配算法：voidDistribute(RecordType1r[],inti,PVectorhead,PVectortail)

/*數(shù)組r已按低位關(guān)鍵字key[i+1]，…，key[d]進(jìn)行了“低位優(yōu)先”排序*/{for(j=0;j<=RADIX-1;++j)head[j]=0；/*將RADIX個(gè)隊(duì)列初始化為空隊(duì)列*/

p=r[0].next；/*p指向鏈表中的第一個(gè)記錄*/

while(p!=0){j=Order(r[p].key[i])；/*用第i位關(guān)鍵字求相應(yīng)隊(duì)列號(hào)*/

if(head[j]==0)head[j]=p;/*將p結(jié)點(diǎn)加入第j隊(duì)列*/

elser[tail[j]].next=p；

tail[j]=p；p=r[p].next；}}voidCollect(RecordTyper[],PVectorhead,PVectortail)

/*從0到RADIX-1

掃描各隊(duì)列，將非空隊(duì)列首尾相接成一個(gè)鏈表*/

{j=0；while(head[j]==0)++j

；/*找第一個(gè)非空隊(duì)列*/

r[0].next=head[j]；t=tail[j]；

while(j<RADIX-1)

/*尋找并串接所有非空隊(duì)列*/

{++j；while((j<RADIX-1)&&(head[j]==0))++j；

/*找下一個(gè)非空隊(duì)列*/

if(head[j]!=0)

/*鏈接非空隊(duì)列*/

{r[t].next=head[j]；t=tail[j]；}}r[t].next=0;

/*t指向最后一個(gè)非空隊(duì)列中的最后一個(gè)結(jié)點(diǎn)*/}收集算法：基數(shù)排序算法：voidRadixSort(RecordTyper[],intlength)

/*length個(gè)記錄存放在數(shù)組r中，進(jìn)行基數(shù)排序*/

{n=length；

for(i=0;i<=n-1;++i)r[i].next=i+1；/*構(gòu)造靜態(tài)鏈表*/r[n].next=0；d=keynum；

for(i=d-1;i>=0;--i)

/*從最低位子關(guān)鍵字開始，進(jìn)行d趟分配和收集*/

{Distribute(r，i，head，tail)；/*第i趟分配*/

Collect(r，head，tail)/*第i趟收集*/

}}

基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd))其中：分配為O(n)

收集為O(rd)(rd為“基”)

d為“分配-收集”的趟數(shù)1.插入類直接插入排序和希爾排序2.交換類起泡排序和快速排序。3.選擇類4.歸并類5.分配類基數(shù)排序簡(jiǎn)單選擇排序和堆排序

歸并排序9.7各種排序方法的綜合比較排序方法平均時(shí)間最壞時(shí)間輔助空間

穩(wěn)定性簡(jiǎn)單排序O(n2)O(n2)

O(1)