數(shù)據(jù)結(jié)構(gòu)第10章

第10章排序排序的基本概念插入排序選擇排序交換排序歸并排序基數(shù)排序性能比較主要知識(shí)點(diǎn)10.1排序的基本概念排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過(guò)程,是把一個(gè)數(shù)據(jù)元素序列整理成按關(guān)鍵字遞增（或遞減）排列的過(guò)程。關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域，排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的。主關(guān)鍵字:數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的值也一定不同，是能夠惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字;不滿足主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字。內(nèi)部排序是把待排數(shù)據(jù)元素全部調(diào)入內(nèi)存中進(jìn)行的排序。外部排序是因數(shù)量太大，把數(shù)據(jù)元素分批導(dǎo)入內(nèi)存，排好序后再分批導(dǎo)出到磁盤和磁帶外存介質(zhì)上的排序方法。比較排序算法優(yōu)劣的標(biāo)準(zhǔn):(1)時(shí)間復(fù)雜度:它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的 移動(dòng)次數(shù)(2)空間復(fù)雜度:算法中使用的內(nèi)存輔助空間的多少

(3)穩(wěn)定性:若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的 先后次序保持不變，則稱這種排序算法是穩(wěn)定的10.2插入排序插入排序的基本思想是：每步將一個(gè)待排序的數(shù)據(jù)元素，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組數(shù)據(jù)元素的適當(dāng)位置上，直到數(shù)據(jù)元素全部插入為止。1.直接插入排序常用的插入排序有直接插入排序和希爾排序兩種。其基本思想是：

順序地把待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。算法如下：voidInsertSort(DataTypea[],intn)//用直接插入法對(duì)a[0]--a[n-1]排序{

inti,j;

DataTypetemp;

for(i=0;i<n-1;i++) {temp=a[i+1]; j=i;

while(j>-1&&temp.key<a[j].key) {a[j+1]=a[j]; j--; } a[j+1]=temp; }}算法分析:(1)空間效率：僅占用若干個(gè)臨時(shí)內(nèi)存單元——O(1)(2)算法的穩(wěn)定性：穩(wěn)定(3)時(shí)間效率：

在最壞情況下（反序），所有元素的比較次數(shù)總和為（1＋2＋…＋n-1)→O(n2)。 平均時(shí)間復(fù)雜度也為O(n2)

但在最好情況下（正序），所有元素的比較次數(shù)總和為（1＋1＋…＋1)→O(n)。

分析：元素序列越接近有序，比較次數(shù)越少。時(shí)間復(fù)雜度越接近O(n)

。{64}789624{564}89624{5764}624{576489}24{5676489}{567246489}589624初始關(guān)鍵字序列:第一次排序:第二次排序:第三次排序:第四次排序:第五次排序:7直接插入排序過(guò)程2.希爾(shell)排序(又稱縮小增量排序)(1)基本思想：把整個(gè)待排序的數(shù)據(jù)元素分成若干個(gè)小組，對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次縮小，當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程結(jié)束。

(2)技巧：小組的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)小組,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。(3)優(yōu)點(diǎn)：每次排序都采用直接插入排序法。當(dāng)數(shù)據(jù)元素個(gè)數(shù)n較小時(shí)，盡量調(diào)整元素序列使之接近有序。這樣，當(dāng)數(shù)據(jù)元素個(gè)數(shù)n為全部元素時(shí)，數(shù)據(jù)元素序列已比較接近有序。從而，整體的時(shí)間效率會(huì)好很多。算法如下：voidShellSort(DataTypea[],intn,intd[],int

numOfD)//用希爾排序法對(duì)元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]為希爾增量值{inti,j,k,m,span;

DataTypetemp;

for(m=0;m<numOfD;m++) //共numOfD次循環(huán) {span=d[m]; //取本次的增量值

for(k=0;k<span;k++) //共span個(gè)小組 { //組內(nèi)是直接插入排序，區(qū)別是每次不是增1而是增span

for(i=k;i<n-span;i=i+span) {temp=a[i+span]; j=i;

while(j>-1&&temp.key<a[j].key) {a[j+span]=a[j]; j=j-span; }

a[j+span]=temp; } } }}653425871238564614779223563414771223654625879238結(jié)果序列d=6563414771223654625879238561214653423774625879238結(jié)果序列d=3561214653423774625879238121423253438465665778792結(jié)果序列d=1(a)(b)(c)希爾排序的排序過(guò)程10.3選擇排序基本思想是：每次從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小（或最大）的數(shù)據(jù)元素放到數(shù)據(jù)元素集合的某個(gè)位置，數(shù)據(jù)元素集合不斷縮小，當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序結(jié)束。常用的選擇排序算法：

（1）直接選擇排序

（2）堆排序1.直接選擇排序基本思想是：從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個(gè)數(shù)據(jù)元素交換位置；如此重復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：每趟只能確定一個(gè)元素，表長(zhǎng)為n時(shí)需要n-1趟算法如下：voidSelectSort(DataTypea[],intn){

inti,j,small;

DataTypetemp;

for(i=0;i<n-1;i++) {small=i; //設(shè)第i個(gè)數(shù)據(jù)元素關(guān)鍵字最小

for(j=i+1;j<n;j++) //尋找關(guān)鍵字最小的數(shù)據(jù)元素

if(a[j].key<a[small].key)small=j;//記住最小元素的下標(biāo)

if(small!=i) //當(dāng)最小元素的下標(biāo)不為i時(shí)交換位置 {

temp=a[i];

a[i]=a[small];

a[small]=temp; } }}645789624{5}64789624{56}7896424{567}896424{56724}6489{5672464}89初始關(guān)鍵字序列:第一次排序結(jié)果:第二次排序結(jié)果:第三次排序結(jié)果:第四次排序結(jié)果:第五次排序結(jié)果:{567246489}最后結(jié)果序列:直接選擇排序的排序過(guò)程算法分析時(shí)間效率：O(n2)——雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多。

空間效率：O(1)——僅用到若干個(gè)臨時(shí)變量。算法的穩(wěn)定性：不穩(wěn)定2.堆排序

基本思想:把待排序的數(shù)據(jù)元素集合構(gòu)成一個(gè)完全二叉樹(shù)結(jié)構(gòu)，則每次選擇出一個(gè)最大（或最?。┑臄?shù)據(jù)元素只需比較完全二叉樹(shù)的高度次，即log2n次，則排序算法的時(shí)間復(fù)雜度就是O(nlog2n)。一、堆的定義堆分為最大堆和最小堆兩種。定義如下：設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，數(shù)組下標(biāo)從0開(kāi)始，如果當(dāng)數(shù)組下標(biāo)2i+1<n時(shí)有:a[i].key≥a[2i+1].key(a[i].key≤a[2i+1].key)；如果當(dāng)數(shù)組下標(biāo)2i+2<n時(shí)有:a[i].key≥a[2i+2].key(a[i].key≤a[2i+2].key)，則這樣的數(shù)據(jù)結(jié)構(gòu)稱為最大堆(最小堆)。1050325769408888764050109325(a)(b)(a)完全二叉樹(shù)(b)最大堆性質(zhì)：（1）最大堆的根結(jié)點(diǎn)是堆中值最大的數(shù)據(jù)元素，最小堆的根結(jié)點(diǎn)是堆中值最小的數(shù)據(jù)元素，我們稱堆的根結(jié)點(diǎn)元素為堆頂元素。（2）對(duì)于最大堆，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑上，數(shù)據(jù)元素組成的序列都是遞減有序的；對(duì)于最小堆，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑上，數(shù)據(jù)元素組成的序列都是遞增有序的。二、創(chuàng)建堆

終端結(jié)點(diǎn)（即葉子）沒(méi)有任何子女，無(wú)需單獨(dú)調(diào)整步驟：從最后一個(gè)非終端結(jié)點(diǎn)開(kāi)始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。創(chuàng)建最大堆過(guò)程中要多次調(diào)用函數(shù)：調(diào)整完全二叉樹(shù)中某個(gè)非葉結(jié)點(diǎn)a[i]，使之滿足最大堆定義，前提條件是該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)a[2i+1]和右孩子結(jié)點(diǎn)a[2i+2]都已是最大堆。函數(shù)設(shè)計(jì)如下：

voidCreatHeap(DataTypea[],intn,inth){

inti,j,flag;

DataTypetemp;

i=h; //i為要建堆的二叉樹(shù)根結(jié)點(diǎn)下標(biāo)

j=2*i+1; //j為i的左孩子結(jié)點(diǎn)的下標(biāo)

temp=a[i]; flag=0;

while(j<n&&flag!=1) {//尋找左右孩子結(jié)點(diǎn)中的較大者,j為其下標(biāo)

if(j<n-1&&a[j].key<a[j+1].key)j++;

if(temp.key>a[j].key) //a[i].key>a[j].key flag=1; //標(biāo)記結(jié)束篩選條件

else //否則把a(bǔ)[j]上移 {a[i]=a[j]; i=j; j=2*i+1; } }

a[i]=temp; //把最初的a[i]賦予最后的a[j]}初始化創(chuàng)建最大堆算法如下：voidInitCreatHeap(DataTypea[],intn) {

inti;

for(i=(n-2)/2;i>=0;i--)

CreatHeap(a,n,i);}堆排序的基本思想是：循環(huán)執(zhí)行如下過(guò)程直到數(shù)組為空：（1）把堆頂a[0]元素（為最大元素）和當(dāng)前最大堆的最后一個(gè)元素交換；（2）最大堆元素個(gè)數(shù)減1；（3）由于第（1）步后根結(jié)點(diǎn)不再滿足最大堆的定義，所以調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義。三、堆排序算法1050325769408810503257694088數(shù)組1050328876940510503288769405數(shù)組1050408876932510504088769325數(shù)組1088405076932510884050769325數(shù)組8876405010932588764050109325數(shù)組(a)初始狀態(tài)

(b)調(diào)整結(jié)點(diǎn)5后(c)調(diào)整結(jié)點(diǎn)32后(d)調(diào)整結(jié)點(diǎn)50后(e)調(diào)整結(jié)點(diǎn)10后完全二叉樹(shù)調(diào)整為最大堆的過(guò)程堆排序算法如下：voidHeapSort(DataTypea[],intn){inti;

DataTypetemp;

InitCreatHeap(a,n); //初始化創(chuàng)建最大堆

for(i=n-1;i>0;i--) //當(dāng)前最大堆個(gè)數(shù)每次遞減1{//把堆頂a[0]元素和當(dāng)前最大堆的最后一個(gè)元素交換temp=a[0]; a[0]=a[i];

a[i]=temp;

CreatHeap(a,i,0); //調(diào)整根結(jié)點(diǎn)滿足最大堆}}堆排序算法的排序過(guò)程

算法分析：時(shí)間效率：O(nlog2n)。因?yàn)檎麄€(gè)排序過(guò)程中需要調(diào)用n-1次堆頂點(diǎn)的調(diào)整，而每次堆排序算法本身耗時(shí)為log2n；空間效率：O(1)。僅用到若干個(gè)臨時(shí)變量。穩(wěn)定性：

不穩(wěn)定。優(yōu)點(diǎn)：對(duì)小文件效果不明顯，但對(duì)大文件有效。10.4交換排序

交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。交換排序的主要算法有：1)冒泡排序2)快速排序1.冒泡排序基本思想：每趟不斷將數(shù)據(jù)元素兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以提前結(jié)束排序。算法核心語(yǔ)句如下：

flag=1;for(i=1;i<n&&flag==1;i++){ flag=0;

for(j=0;j<n-i;j++) {

if(a[j].key>a[j+1].key)

{

flag=1; temp=a[j];

a[j]=a[j+1]; a[j+1]=temp; } }}初始關(guān)鍵字序列:第一次排序結(jié)果:第二次排序結(jié)果:第三次排序結(jié)果:第四次排序結(jié)果:第五次排序結(jié)果:最后結(jié)果序列:38519264997166519263849166[97]5192638149[6697]51926138[496697]519126[38496697]5119[2638496697]15[192638496697]1[5192638496697]15192638496697第六次排序結(jié)果:第七次排序結(jié)果:冒泡排序算法的排序過(guò)程算法分析：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做n-1次關(guān)鍵碼比較，不移動(dòng)數(shù)據(jù)元素。最壞情形：初始排列逆序，算法要執(zhí)行n-1趟起泡，第i趟(1

i

n)做了n-i次關(guān)鍵碼比較，執(zhí)行了n-i次數(shù)據(jù)元素交換。此時(shí)的比較總次數(shù)和記錄移動(dòng)次數(shù)為：2.快速排序

基本思想：從待排序列中任取一個(gè)元素(例如取第一個(gè))作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了。優(yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快。因此：時(shí)間效率：O（n2)

—考慮最壞情況空間效率：O（1）

—僅用到若干個(gè)臨時(shí)變量穩(wěn)定性：穩(wěn)定的算法核心語(yǔ)句如下： while(i<j&&temp.key<=a[j].key)j--;//在數(shù)組的右端掃描

if(i<j) {

a[i]=a[j]; i++; }

while(i<j&&a[i].key<temp.key)i++;//在數(shù)組的左端掃描

if(i<j) {

a[j]=a[i]; j--; }6055483710908436365548371090849090365548371090843655483710908436554837109084365548371090843655483710908436554837108436554837106084iiiiiiiijjjjjjjjij初始關(guān)鍵字序列:(1)(2)(3)(4)(5)(6)(7)(8)快速排序算法一次快速排序過(guò)程圖中標(biāo)有下劃?rùn)M線的數(shù)據(jù)元素為本次快速排序選取的標(biāo)準(zhǔn)元素?？焖倥判蛩惴ǜ鞔慰焖倥判蜻^(guò)程初始關(guān)鍵字序列:(1)(2){6055483710908436{3655483710}60{90}{10}36{3755}6084{}(3){10}36{}48{}608490最后結(jié)果1036374855608490{37}48558490時(shí)間效率：O(nlog2n)

—因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O(log2n)—因?yàn)檫f歸要用堆棧穩(wěn)定性：不穩(wěn)定

—因?yàn)橛刑S式交換。算法分析：10.5歸并排序歸并排序主要是二路歸并排序,基本思想是：可以把一個(gè)長(zhǎng)度為n的無(wú)序序列看成是

n個(gè)長(zhǎng)度為1的有序子序列，首先做兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列；再做兩兩歸并，…，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序序列。

一次二路歸并排序算法如下：voidMerge(DataTypea[],intn,DataTypeswap[],intk)//k為子數(shù)組長(zhǎng)度，一次二路歸并排序后的子序列存于數(shù)組swap中{intm=0,u1,l2,i,j,u2;

intl1=0; //第一個(gè)有序子數(shù)組下界為0

while(l1+k<=n-1) {l2=l1+k; //第二個(gè)有序子數(shù)組下界

u1=l2-1; //第一個(gè)有序子數(shù)組上界

u2=(l2+k-1<=n-1)?l2+k-1:n-1;//第二個(gè)子數(shù)組上界//兩個(gè)有序子數(shù)組合并

for(i=l1,j=l2;i<=u1&&j<=u2;m++) {

if(a[i].key<=a[j].key) {swap[m]=a[i];i++;} else {swap[m]=a[j];j++;} }

//子數(shù)組2已完，將子數(shù)組1中剩余的元素存放到swap

while(i<=u1) {swap[m]=a[i];m++;i++; } //子數(shù)組1已完，將子數(shù)組2中剩余的元素存放到swap

while(j<=u2) {swap[m]=a[j];m++;j++; }

l1=u2+1;}

//將原始數(shù)組中只夠一組的數(shù)據(jù)元素順序存放到數(shù)組swap

for(i=l1;i<n;i++,m++)swap[m]=a[i];}二路歸并排序算法分析時(shí)間效率：

O(nlog2n)因?yàn)樵谶f歸的歸并排序算法中，遞歸調(diào)用函數(shù)Merge()約為log2n

次，而每次歸并要執(zhí)行比較約為n次，所以算法總的時(shí)間復(fù)雜度為O(nlog2n)?？臻g效率：

O(n)

因?yàn)樾枰粋€(gè)與原始序列同樣大小的輔助序列。這是此算法的缺點(diǎn)。穩(wěn)定性：穩(wěn)定10.6基數(shù)排序基數(shù)排序也稱作桶排序，是一種當(dāng)關(guān)鍵字為整數(shù)類型時(shí)非常高效的排序方法。

其基本思想是：設(shè)待排序的數(shù)據(jù)元素關(guān)鍵字是m位d進(jìn)制整數(shù)（不足m位的關(guān)鍵字在高位補(bǔ)0），設(shè)置d個(gè)桶，令其編號(hào)分別為0,1,2,…,d-1。首先按關(guān)鍵字最低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序收集分配在各桶中的數(shù)據(jù)元素，這樣就形成了數(shù)據(jù)元素集合的一個(gè)新的排列，我們稱這樣的一次排序過(guò)程為一次基數(shù)排序；

再對(duì)一次基數(shù)排序得到的數(shù)據(jù)元素序列按關(guān)鍵字次低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序收集分配在各桶中的數(shù)據(jù)元素；這樣的過(guò)程重復(fù)進(jìn)行，當(dāng)完成了第m次基數(shù)排序后，就得到了排好序的數(shù)據(jù)元素序列。數(shù)據(jù)元素的關(guān)鍵字序列為{710,342,045,686,006,841,429,134,068,264}排序過(guò)程如下8411342231342644045568600667068871004299710841342134264045686006068429收集后的新序列:放置7101429213438413420454526406867686800609006710429134841342045264068686收集后的新序列:放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列:放置(a)初始狀態(tài)

(b)第一次基數(shù)排序

(c)第二次基數(shù)排序基數(shù)排序算法進(jìn)出桶中的數(shù)據(jù)元素序列滿足先進(jìn)先出的原則，桶實(shí)際就是隊(duì)列。實(shí)現(xiàn)基數(shù)排序算法時(shí)，有基于順序隊(duì)列和基于鏈?zhǔn)疥?duì)列兩種不同的實(shí)現(xiàn)方法。在基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法中，可以把d個(gè)隊(duì)列設(shè)計(jì)成一個(gè)隊(duì)列數(shù)組（設(shè)隊(duì)列數(shù)組名為tub），隊(duì)列數(shù)組的每個(gè)元素中包括兩個(gè)域：front域和rear域。front域用于指示隊(duì)頭，rear域用于指示隊(duì)尾。當(dāng)?shù)趇（i=0,1,2,…,d-1）個(gè)隊(duì)列中有數(shù)據(jù)元素要放入時(shí)，就在隊(duì)列數(shù)組的相應(yīng)元素tub[i]中的隊(duì)尾位置插入一個(gè)結(jié)點(diǎn)。基于鏈?zhǔn)疥?duì)列基數(shù)排序算法的存儲(chǔ)結(jié)構(gòu)示意圖如下圖所示。......rearfrontdatanext∧

012d-1...tub∧

一個(gè)十進(jìn)制關(guān)鍵字K的第i位數(shù)值Ki的計(jì)算公式為：基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法:

#include"LQueue.h"

void

RadixSort(DataTypea[],intn,intm,intd)

{

inti,j,k,power=1;

LQueue*tub; //把d個(gè)隊(duì)列定義為動(dòng)態(tài)數(shù)組

tub=(LQueue*)malloc(sizeof(LQueue)*d);

for(i=0;i<