數(shù)據(jù)結(jié)構(gòu)-內(nèi)部排序

本章主要內(nèi)容：主要介紹以下各種內(nèi)部排序方法的基本思想、算法特點(diǎn)、排序過程及時(shí)間復(fù)雜度分析。本章重點(diǎn)：1.掌握各種排序方法中的高效方法(插入排序的希爾排序、交換排序的快速排序、選擇排序的堆排序、歸并排序)；2.掌握各種排序方法的時(shí)間復(fù)雜度；3.理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。第十章內(nèi)部排序第十章內(nèi)部排序10.1

概

述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種排序方法的比較

10.1

概

述一、排序的定義二、一些排序的術(shù)語一、排序的定義

10.1概

述

排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。排序的目的之一是方便數(shù)據(jù)查找。對排序下一個(gè)確切的定義：假設(shè)含n個(gè)記錄的序列為：{R1，R2，…，Rn}其相應(yīng)的關(guān)鍵字序列為：{K1，K2，…，Kn}

需確定1，2，…，n的一種排列p1，p2，…，pn，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減(或非遞增)關(guān)系：

Kp1≤Kp2≤…≤Kpn使{R1，R2，…，Rn}成為關(guān)鍵字有序的序列：{Rp1，Rp2，…，Rpn}這種操作稱為排序。二、一些排序的術(shù)語

10.1概

述1.排序方法的穩(wěn)定與不穩(wěn)定在排序過程中，有若干記錄的關(guān)鍵字相等，即Ki=Kj(1≤i≤n，11≤j≤n，i≠j)，在排序前后，含相等關(guān)鍵字的記錄的相對位置保持不變，即排序前Ri在Rj之前，排序后Ri仍在Rj之前，稱這種排序方法是穩(wěn)定的；反之，若可能使排序后的序列中Ri在Rj之后，稱所用排序方法是不穩(wěn)定的。2.內(nèi)部排序和外部排序

內(nèi)部排序——如果在排序過程中，只使用計(jì)算機(jī)的內(nèi)存存放待排序所有記錄，稱這種排序?yàn)閮?nèi)部排序。(或?qū)?nèi)存中的記錄進(jìn)行的排序)。

外部排序——如果待排序的文件較大，排序期間文件的全部記錄不能同時(shí)存放在計(jì)算機(jī)的內(nèi)存里，要借助計(jì)算機(jī)的外存才能完成排序，稱之為“外部排序”。在外部排序過程中，記錄必須在計(jì)算機(jī)的內(nèi)存和外存之間移動(dòng)。這樣，內(nèi)外存之間的數(shù)據(jù)交換次數(shù)就成為影響外部排序速度的主要因素。二、一些排序的術(shù)語

10.1概

述3.排序方法的種類(1)按排序過程中依據(jù)不同的原則分為五大類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。(2)按時(shí)間復(fù)雜度劃分為三類：

簡單排序方法：其時(shí)間復(fù)雜度為O(n2)，該方法是穩(wěn)定的，屬于簡單排序的排序方法包括：除希爾排序的插入排序、冒泡排序和簡單排序。

先進(jìn)(高效)的排序方法：其時(shí)間復(fù)雜度為O(nlogn)，屬于此排序方法的有：快速排序、堆排序、歸并排序。其中快速排序和堆排序是不穩(wěn)定的排序方法。

基數(shù)排序方法：其時(shí)間復(fù)雜度為O(d*n)，該方法是穩(wěn)定的。

二、一些排序的術(shù)語10.1概述二、一些排序的術(shù)語

10.1概述4.效率分析(1)時(shí)間復(fù)雜度：關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)。(2)空間復(fù)雜度：執(zhí)行算法所需的附加存儲(chǔ)空間。5．排序的基本操作排序的基本操作主要有兩種：(1)比較兩個(gè)關(guān)鍵字大小(2)根據(jù)比較的結(jié)果將記錄從一個(gè)位置移到另一個(gè)位置。二、一些排序的術(shù)語

10.1概述6．排序記錄的存儲(chǔ)方式

(1)采用順序表，相鄰的記錄，存儲(chǔ)位置也相鄰，記錄的次序關(guān)系由其存儲(chǔ)位置決定，實(shí)現(xiàn)排序必須借助移動(dòng)記錄。

(2)采用靜態(tài)鏈表，記錄之間的次序關(guān)系由指針指示，則實(shí)現(xiàn)排序不需要移動(dòng)記錄，僅需修改指針即可。這種方式下實(shí)現(xiàn)的排序又稱表排序。

(3)待排序記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元內(nèi)，同時(shí)另設(shè)一個(gè)指示各記錄存儲(chǔ)位置的地址向量，在排序過程中不移動(dòng)記錄本身，而移動(dòng)地址向量中這些記錄的“地址”，在排序結(jié)束之后再按照地址向量中的值調(diào)整記錄的存儲(chǔ)位置，這種方式下實(shí)現(xiàn)的排序又稱地址排序。10.2插入排序一、插入排序概述二、直接插入排序三、折半插入排序四、希爾排序(Shell)一、插入排序概述1．插入排序思想插入排序的基本思想是，每一次只考慮一個(gè)待排序的元素，同已排序的元素作比較，在比較完畢之后，把待排序的元素放到合適的位置，然后再選下一個(gè)待排序的元素。10.2插入排序2．插入排序的基本算法假設(shè)所有待排序的元素在數(shù)組r[n]之內(nèi)。(1)初始狀態(tài)排序開始之前，整個(gè)數(shù)組r被劃分兩個(gè)部分：有序區(qū)和無序區(qū)。

有序區(qū)內(nèi)存放的是已排好順序的元素；

無序區(qū)內(nèi)存放的是尚未排好順序的元素。初始時(shí)，有序區(qū)只有1個(gè)元素r[1]。

無序區(qū)里的元素是r[2]～r[n]。(2)終態(tài)在排序操作完成之后，在有序區(qū)中包含整個(gè)數(shù)組r，而在無序區(qū)內(nèi)則為空。整個(gè)狀態(tài)稱為終態(tài)。一、插入排序概述10.2插入排序(3)基本操作步驟a.首先從無序區(qū)中取一個(gè)記錄，通常是第一個(gè)記錄；b.然后將其同有序區(qū)中的元素比較，并按其關(guān)鍵字值大小，把該記錄插入到有序區(qū)中的適當(dāng)位置，這樣有序區(qū)中始終保持有序性；c.再從無序區(qū)中取一個(gè)記錄，重復(fù)b.操作，直到終態(tài)。一、插入排序概述10.2插入排序直接插入排序是一種最簡單的排序方法。它的基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。1．排序思想2．算法將序列中的第1個(gè)記錄看成是一個(gè)有序的子序列;從第2個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。整個(gè)排序過程為進(jìn)行n-1趟插入。同時(shí)后移記錄。二、直接排序概述10.2插入排序3．算法描述voidInsertSort(Sqlist&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//設(shè)置哨兵

for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//記錄后移

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

//插入到正確位置}}二、直接排序概述10.2插入排序例1

直接插入排序的過程。初始關(guān)鍵字：(49)38659776132749

i=2:(38)(38

49)6597761327

49i=3:(65)(3849

65)9776132749i=4:(97)(384965

97)76132749

i=5:(76)(384965

76

97)132749i=6:(13)(13

3849657697)27

49i=7:(27)(13

27

3849657697)

49

i=8:(49)(13273849

49

657697)二、直接排序概述10.2插入排序4.算法分析

(1)穩(wěn)定性直接插入排序是穩(wěn)定的排序方法。(2)算法效率

a.時(shí)間復(fù)雜度時(shí)間復(fù)雜度為O(n2)。b.空間復(fù)雜度它只需要一個(gè)記錄的輔助空間，O(1)。二、直接排序概述10.2插入排序三、折半插入排序從減少“比較”和“移動(dòng)”兩種操作的次數(shù)考慮，折半插入排序是直接插入排序的一種改進(jìn)方法。1．折半插入排序思想由于插入排序的基本操作是在有序表中進(jìn)行查找和插入，在有序表中用折半查找方法可以提高查找效率，利用折半查找的方法來進(jìn)行插入排序可以減少比較次數(shù)，從而提高整個(gè)算法的執(zhí)行效率。10.2插入排序2.算法描述voidBInsertSort(Sqlist&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){m=(low+high)/2;

if(L.r[0].key<L.r[m].key)

high=m-1;elselow=m+1;}for(j=i-1;j>=high+1;--j)

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

//記錄后移

L.r[high+1]=L.r[0];//插入到正確位置}}三、折半插入排序10.2插入排序3．算法分析(1)穩(wěn)定性折半排序是穩(wěn)定的排序方法。(2)算法效率時(shí)間復(fù)雜度仍為O(n2)?？臻g復(fù)雜度為O(1)，附加存儲(chǔ)空間同直接插入排序。三、折半插入排序10.2插入排序四、希爾排序(Shell)又稱“縮小增量排序”，屬于插入排序類的方法，但在時(shí)間效率上較前幾種排序方法有較大的改進(jìn)。1.基本思想在直接插入排序中，當(dāng)n較小時(shí)，排序的效率比較高。

希爾排序方法是先將待排序記錄分割成為若干子序列，分別在子序列中進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接排序。10.2插入排序子序的分割不是簡單的“逐段分割”，而是將待排序的記錄按照某個(gè)增量d分成若干子序列，將相隔d的記錄組成一個(gè)子序列。在子序列中進(jìn)行直接插入排序。隨著增量d的逐步變小，各子序列中的記錄逐漸增多，各子序列中的記錄隨著d的減小而趨于有序。當(dāng)增量減小到1時(shí)，已達(dá)到基本有序，再進(jìn)行直接排序，排序就完成了。在希爾排序中關(guān)鍵字較小的記錄不是一步一步的前移，而是跳躍式的前移，因此效率提高。

四、希爾排序(Shell)10.2插入排序2.算法(1)按距離d將待排序數(shù)組r分成若干個(gè)小組，等距離者在同一個(gè)組中，初始距離為d1；(2)在每個(gè)小組中進(jìn)行直接插入排序；(3)修改距離，選一個(gè)小于上次距離d1的距離d2；(4)重復(fù)(1)、(2)和(3)，直到d=1為止。四、希爾排序(Shell)10.2插入排序3.舉例例2初始關(guān)鍵字：493865

97

761327

49

55

04第一次：

d1=n/2=5分成5組：{49,13}，{38,27}，{65,49}，{97,55}，{76,04}各組排序后：1327

49

5504

493865

9776第二次：d2=d1/2=3分成3組：{13,55,38,76}，{27,04,65}，{49,49,97}排序后：1304

49

38274955659776第三次：d3=2

分成2組：{13,49,27,55,97}，{04,38,49,65,76}排序后：13042738494955659776第四次：d4=104132738494955657697四、希爾排序(Shell)10.2插入排序4．算法描述voidshellsort(Sqlist&L,intdlta[],intt){//按增量序列dlta[0…t-1]

對順序表L作希爾排序

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}voidShellInsert(&L,&dk){for(i=dk+1;i<=L.length;++i)//增量是dk而不是1

if(l.r[i].key<L.r[i-dk].key){L.r[0]=L.r[i];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];}}四、希爾排序(Shell)10.2插入排序5.算法分析(1)穩(wěn)定性希爾算法是不穩(wěn)定的排序方法。(2)時(shí)間復(fù)雜度希爾排序算法的速度是所取的“增量”序列的函數(shù)，不論選擇什么樣的d，最后一個(gè)值必須是1。實(shí)驗(yàn)表明，希爾排序的時(shí)間復(fù)雜度為O(nlog2n)。(3)空間復(fù)雜度為O(1)。四、希爾排序(Shell)10.2插入排序10.3

快速排序一、冒泡排序二、快速排序一、冒泡排序10.3快速排序1．基本思想：從第一個(gè)記錄開始，兩兩記錄比較，若L.r[1]>L.r[2]，則將兩個(gè)記錄交換；依次類推，L.r[i]與L[i+1]比較，直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行比較完畢。第1趟比較結(jié)果將序列中關(guān)鍵字最大的記錄放置到最后一個(gè)位置，稱為“沉底”，而最小的則上浮一個(gè)位置，如水泡在水中上浮，且n個(gè)記錄比較n-1次。第i趟比較，將L.r[1]到L.r[n-i+1]依次比較相鄰兩個(gè)記錄的關(guān)鍵字，并在“逆序”時(shí)交換相鄰記錄，結(jié)果n-i+1個(gè)記錄中關(guān)鍵字最大的記錄放置到n-i+1位置上。

n個(gè)記錄的整個(gè)排序過程需進(jìn)行n-1趟冒泡排序。2.圖示：第一輪：a[1]10a[2]5a[3]8a[4]01055105108010881058100第二輪：

a[1]5a[2]8a[3]0100100沉低上浮55885808008沉低上浮第三輪：a[1]5a[2]0

05結(jié)果：a[1]a[2]a[3]a[4]058104個(gè)數(shù)比較3輪，n個(gè)數(shù)比較n-1輪4個(gè)數(shù)比較3次3個(gè)數(shù)比較2次2個(gè)數(shù)比較1次一、冒泡排序10.3快速排序3.算法：main(){inta[11],i,j,t;printf(“input10numbers:\n”);for(i=1;i<=10;i++)scanf(“%d”,&a[i]);printf(“\n”);

for(i=1;i<=9;i++){for(j=1;j<=10-i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}}printf(“thesortednumbers:\n”);for(i=1;i<11;i++)printf(“%d”,a[i]);}4．算法分析時(shí)間復(fù)雜度O(n2)

一、冒泡排序10.3快速排序1.基本思想快速排序是對冒泡排序的一種改進(jìn)。通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對兩部分記錄繼續(xù)進(jìn)行快速排序，達(dá)到整個(gè)序列有序，是一種分治方法。二、快速排序10.3快速排序2．算法設(shè)待排序記錄序列為：{L.r[s],L.r[s+1],…L.r[t]}。(1)任意選取一個(gè)記錄(通常可選第一個(gè)記錄Lr[s])作為樞軸(或支點(diǎn))(pivot)。(2)將所有關(guān)鍵字較它小的記錄都安置在樞軸之前，將所有關(guān)鍵字較它大的記錄都安置在樞軸之后，在這個(gè)過程中存在兩個(gè)記錄的“交換”。(3)以該“樞軸”記錄最后所在的位置i作為分界線，位置i前的序列為{L.r[s],…,L.r[i-1]}，位置i后的序列為L.r[i+1],…,L.r[t]}。(4)繼續(xù)在兩個(gè)序列上進(jìn)行(1)～(3)的操作。二、快速排序10.3快速排序3．具體操作(1)一趟快速排序附設(shè)兩個(gè)指針low和high，它們的初值分別指向序列的第1個(gè)記錄和最后一個(gè)記錄，設(shè)樞軸記錄的關(guān)鍵字為pivotkey(pivotkey=L.r[low].key)。a.

從high所指位置起向前搜索找到第一個(gè)關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換；b.

從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相交換。c.

重復(fù)這兩步直至low=high為止。二、快速排序10.3快速排序一趟排序結(jié)束，以樞軸為分界點(diǎn)將序列分為兩部分，樞軸前的記錄關(guān)鍵字小于樞軸記錄的關(guān)鍵字，樞軸后記錄的關(guān)鍵字大于樞軸記錄的關(guān)鍵字。(2)按照(1)的方法繼續(xù)對所分兩部分快速排序。整過快速排序是一個(gè)遞歸過程。初始關(guān)鍵字

49

386597761327

4949>27i(low)j(high)j一次交換

27

38

6597761349

49

49<65iij

二次交換

27

38

49977613

65

49

49>13jji三次交換27

38

13

977649

65

4949<97四次交換

27

38

13

497697

65

49i=j完成一趟排序

27

38

13

497697

65

49iijijj二、快速排序10.3快速排序1．算法描述intPartition(Sqlist&L,intlow,inthigh){pivotkey=L.r[low].key;L.r[0]=L.r[low];while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;

L.r[low]←→L.r[high];L.r[low]=L.r[high];While(low<high&&L.r[low].key<=pivotkey)

++low;L.r[low]←→L.r[high];L.r[high]=L.r[low];}

L.r[low]=L.r[0];returnlow;}二、快速排序10.3快速排序遞歸的快速排序算法：voidQsort(Sqlist&L,intlow,inthigh){if(low<high){pivotloc=Partition(L,low,high);//確定樞軸位置

QSort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);}}二、快速排序10.3快速排序5.算法分析(1)穩(wěn)定性快速排序是不穩(wěn)定的排序方法。(2)時(shí)間復(fù)雜度快速排序的時(shí)間復(fù)雜度為O(nlogn)數(shù)量級。(3)空間復(fù)雜度由于快速排序是一個(gè)遞歸過程，需一個(gè)棧的附加空間，棧的深度為O(logn)。二、快速排序10.3快速排序10.4選擇排序一、簡單選擇排序

二、堆排序

基本思想每一次都在數(shù)組中選取關(guān)鍵字最小的一個(gè)記錄，送到已經(jīng)排好序的記錄序列的后面，直到完成整個(gè)排序工作。即每一趟在n-i+1個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。10.4選擇排序10.4選擇排序一、簡單選擇排序1.基本思想通過n-i次關(guān)鍵字的比較，在n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄交換。2.算法描述voidSelectSort(Sqlist&L){for(i=1;i<L.length;++i){min=i;

for(j=i+1;j<=L.length;j++)

if(L.r[j].key<L.r[min].key)

min=j;if(min!=i)

{t=L.r[min];

L.r[min]=L.r[i];L.r[i]=t;}}}3.算法分析(1)穩(wěn)定性簡單選擇排序方法是穩(wěn)定的。(2)時(shí)間復(fù)雜度為O(n2)(3)空間復(fù)雜度為O(1)。

10.4選擇排序

二、堆排序1.樹形選擇排序樹形選擇排序又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。出發(fā)點(diǎn)是利用前一次比較的結(jié)果，減少“比較”的次數(shù)。在n個(gè)關(guān)鍵字中選出最小值，至少進(jìn)行n-1次，在n-1個(gè)關(guān)鍵字中選擇次小值并非一定要進(jìn)行n-2次比較，若能利用前n-1次比較所得信息，則可減少以后各趟選擇排序中所用的比較次數(shù)。每選擇一個(gè)次小關(guān)鍵字僅需進(jìn)行l(wèi)og2n(樹的深度-1)次比較，時(shí)間復(fù)雜度為O(nlog2n)。但所需輔助存儲(chǔ)空間較多。

n-1+(n-1)log2n10.4選擇排序

二、堆排序2.堆排序(1)堆的定義

n個(gè)元素的序列{k1,k2,…,kn}，當(dāng)且僅當(dāng)滿足下述關(guān)系時(shí)，稱之為堆。

ki≤k2i

ki≥k2i

ki≤k2i+1ki≥k2i+1

若將用一維數(shù)組存儲(chǔ)的序列看成是一個(gè)完全二叉樹，則完全二叉樹中的任意非葉結(jié)點(diǎn)的關(guān)鍵字值大(或小)于它的左、右孩子結(jié)點(diǎn)的值。這種數(shù)據(jù)結(jié)構(gòu)即為堆?；?0.4選擇排序

二、堆排序

10.4選擇排序

二、堆排序22124030343650875087403036341222小頂堆大頂堆(2)堆排序在堆結(jié)構(gòu)中輸出堆頂最小值(或最大值)后，使得剩余n-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值(或次大值）。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱為堆排序。堆排序需解決兩個(gè)問題：

a.由一個(gè)無序序列建成一個(gè)堆。

b.在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆。10.4選擇排序

二、堆排序(3)堆排序的算法a.建立包含k1,k2,k3,…kn的堆。b.輸出堆頂元素，采用堆頂元素R1與最后一個(gè)元素Rn交換，最大(或最小)元素得到正確的排序位置，此時(shí)前n-1個(gè)元素不再滿足堆的特性，需重建堆。

c.在b.之后，新的堆頂(根結(jié)點(diǎn))的左、右子樹均為堆，則僅需自上至下進(jìn)行調(diào)整即可。

這個(gè)自堆頂至葉子的調(diào)整過程為“篩選”。

將一個(gè)無序序列建堆的過程就是一個(gè)反復(fù)“篩選”的過程。例310.4選擇排序

二、堆排序例3：對于一個(gè)無序序列{49，38，65，97，76，13，27，49}進(jìn)行堆排序。

1)先建一個(gè)完全二叉樹，如圖所示：

2)進(jìn)行反復(fù)的“篩選”。從最后一個(gè)非終端結(jié)點(diǎn)(第n/2個(gè)元素)開始，將此結(jié)點(diǎn)與其左、右孩子比較，選出大的或小的作為此結(jié)點(diǎn)；依次對其前的非終端結(jié)點(diǎn)重復(fù)進(jìn)行“篩選”操作。直到第1個(gè)元素(根結(jié)點(diǎn))為最大或最小為止，堆建成。10.4選擇排序

二、堆排序3)根結(jié)點(diǎn)就是排序的最大關(guān)鍵字或最小關(guān)鍵字，輸出根結(jié)點(diǎn)，即將13和97交換，再重復(fù)進(jìn)行(2)操作，直到整個(gè)序列有序。10.4選擇排序

二、堆排序

產(chǎn)生的是一個(gè)遞減序列：{97，76，65，49，49，38，27，13}。

10.4選擇排序

二、堆排序作為小頂堆，產(chǎn)生的是一個(gè)遞減序列。作為大頂堆，產(chǎn)生的是一個(gè)遞增序列。(4)算法描述typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];for(j=2*s;j<=m;j*=2)//沿key較小的孩子結(jié)點(diǎn)向下篩選{if(j<m&&!LT(H.r[j].key,H.r[j+1].key))++j;if(LT(rc.key,H.r[j].key))//rc與左、右孩子中小者比break;

H.r[s]=H.r[j];s=j;//將左、右孩子中小者放入s,定義新的s,

}//即新的根H.r[s]=rc;//若rc小，插入s}10.4選擇排序

二、堆排序voidHeapSort(HeapType&H){for(i=H.length/2;i>0;--i)

HeapAdjust(H,i,H.length);//建小頂堆

for(i=H.length;i>1;--i){H.r[1]←→H.r[i];

//堆頂記錄和最后一個(gè)記錄相互交換

HeapAdjust(H,1,i-1);//調(diào)整小頂堆，自上而下}}(5)算法分析a.堆排序是不穩(wěn)定的排序。b.時(shí)間復(fù)雜度為O(nlog2n)。c.空間復(fù)雜度為O(1)。10.4選擇排序

二、堆排序

10.5歸并排序一、2-路歸并排序思想二、2-路歸并排序的方法三、2-路歸并步驟四、算法描述

10.5歸并排序1．歸并的含義將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列。2．歸并排序就是利用歸并思想實(shí)現(xiàn)的排序，把多個(gè)有序表經(jīng)過若干次歸并，最終合并成一個(gè)有序表。3.對兩個(gè)有序序列進(jìn)行歸并，稱為2-路歸并。10.5歸并排序一、2-路歸并排序思想把一個(gè)有n個(gè)元素的無序表的每一個(gè)元素都看成一個(gè)有序表，將兩個(gè)有序子表（有序表）合并成一個(gè)有序子表，一次合并完成后，有序子區(qū)間的數(shù)目減少一半，而子表的長度增加一倍，當(dāng)子表長度從1增加到n（元素個(gè)數(shù)）時(shí)，整個(gè)子表變?yōu)橐粋€(gè)，則該子表中的有序序列即為我們所需的排序結(jié)果。

(1)將n個(gè)記錄看成是n個(gè)長度為1的有序子表；(2)

將兩兩相鄰的有序子表n進(jìn)行歸并，若n為奇數(shù)，則留下的一個(gè)子表直接進(jìn)入下一次歸并；(3)重復(fù)步驟(2)，直到歸并成一個(gè)長度為n的有序表。

10.5歸并排序一、2-路歸并排序思想例4給定排序碼46，55，13，42，94，05，17，70，二路歸并排序過程如圖所示。10.5歸并排序二、2-路歸并排序方法假設(shè)兩個(gè)子表為R1和R2，這兩個(gè)子表將被歸并為T。歸并過程為：首先把兩個(gè)子表為R1和R2的第一個(gè)元素取出來進(jìn)行比較；(1)

將較小的元素放入T；(2)

取較小元素所在的子表的下一個(gè)元素與上一步較大的元素比較；(3)

重復(fù)(1)、(2)，直到一個(gè)子表中的元素取完為止；(4)

把還剩有元素的子表中的元素取出，依次放入T。10.5歸并排序三、2-路歸并排序的步驟1．2-路歸并算法將有序的SR[i..m]和SR[m+1..n]歸并為有序序列TR[i..n]。voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){for(j=m+1,k=i;i<=m&&j<=n;++k)

{ifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];if(j<=n)TR[k..n]=SR[j..n]}10.5歸并排序四、算法描述2.一趟歸并排序上述算法是將相鄰兩個(gè)有序序列2-路歸并。而一趟歸并排序則調(diào)用mergen/2h次，將前后相鄰且長度為h的有序段進(jìn)行兩兩歸并，得到前后相鄰、長度為2h的有序段。3．歸并排序整個(gè)歸并排序就是調(diào)用“一趟歸并”過程若干次的過程。第一趟歸并時(shí)，有序子表長度為1，每趟歸并后有序子表的長度為上一次長度的2倍，當(dāng)有序子表的長度為n時(shí)，2-路歸并排序結(jié)束。見圖10.1310.5歸并排序四、算法描述遞歸算法：voidMsort(RcdTypeSR[],RcdType&TR1[],ints,intt){if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);

Merge(TR2,TR1,s,m,t);}}voidMergeSort(SqList&L){Msort(L.r,L.r,L.length);}10.5歸并排序四、算法描述二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)雜度的乘積。而歸并趟數(shù)為log2n(當(dāng)log2n

為奇數(shù)時(shí)，則為log2n+1)。因?yàn)槊恳惶藲w并就是將兩兩有序子表合并成一個(gè)有序子表，而每一對有序子表歸并時(shí)，記錄的比較次數(shù)均小于等于記錄的移動(dòng)次數(shù)（即由一個(gè)數(shù)組復(fù)制到另一個(gè)數(shù)組中的記錄個(gè)數(shù)），而記錄的移動(dòng)次數(shù)等于這一對有序表的長度之和，所以，每一趟歸并的移動(dòng)次數(shù)均等于數(shù)組中記錄的個(gè)數(shù)n，即每一趟歸并的時(shí)間復(fù)雜度為O(n)。因此，二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。

利用二路歸并排序時(shí)，需要利用與待排序數(shù)組相同的輔助數(shù)組作臨時(shí)單元，故該排序方法的空間復(fù)雜度為O(n)，比前面介紹的其它排序方法占用的空間大。10.5歸并排序五、算法分析1．穩(wěn)定性歸并排序是穩(wěn)定的排序方法。2．時(shí)間復(fù)雜度為O(nlog2n)。3．空間復(fù)雜度為O(n)。

10.5歸并排序五、算法分析

10.6基數(shù)排序一、多關(guān)鍵字的排序二、鏈?zhǔn)交鶖?shù)排序

10.6基數(shù)排序1.基數(shù)排序不用進(jìn)行記錄關(guān)鍵字的比較和交換，而是利用關(guān)鍵字的結(jié)構(gòu)，通過“分類”和“收集”的辦法實(shí)現(xiàn)排序。2.基數(shù)排序?qū)⒍嚓P(guān)鍵字排序的思想用于單邏輯關(guān)鍵字的排序中。

10.6基數(shù)排序一、多關(guān)鍵字的排序1．多關(guān)鍵字排序思想以撲克牌排序?yàn)槔懻摱嚓P(guān)鍵字排序思想。任何一張撲克牌都有花色和面值兩種屬性，以花色為第一關(guān)鍵字K1，面值為第二關(guān)鍵字K2，都可看成由K1和K2組成的復(fù)合關(guān)鍵字。任一張牌的關(guān)鍵字為K1K2。

多關(guān)鍵字排序，就是按復(fù)合關(guān)鍵字的大小排序。具體到撲克牌排序，有兩種方法：

第一種是先花色后面值：按花色分為四類有序，然后每類按面值從小到大排序；

第二種是先面值后花色：先將牌按面值分為13類，然后從小到大將它們收集起來，再按花色分為4堆，最后按花色順序收集起來。

2．多關(guān)鍵字排序定義設(shè)有n個(gè)記錄的序列{R1,R2,…,Rn}，且每個(gè)記錄Ri中含有d個(gè)關(guān)鍵字(Ki0,Ki1,…Kid-1)，規(guī)定Ki0

為主位關(guān)鍵字(或最高位關(guān)鍵字)，Kid-1為次位關(guān)鍵字(最低位關(guān)鍵字)。序列{R1,R2,…,Rn}對關(guān)鍵字(Ki0,Ki1,…Kid-1)有序是指：對于序列中任意兩個(gè)記錄Ri的Rj(1≤i≤j≤n)都滿足下列有序關(guān)系：(Ki0,Ki1,…Kid-1)<(Kj0,Kj1,…Kjd-1)。

10.6基數(shù)排序一、多關(guān)鍵字的排序3.兩種排序方法(1)最高位優(yōu)先(MSD)

先對最主位關(guān)鍵字K0進(jìn)行排序，具有相同的K0值的記錄構(gòu)成一個(gè)子序列，再對關(guān)鍵字K1進(jìn)行排序，依次重復(fù)，直到對Kd-1排序，最后將所有子序列依次連接在一起成為一個(gè)有序序列。將序列逐層分割若干子序列。(2)最低位優(yōu)先(LSD)

從最次位關(guān)鍵字Kd-1起進(jìn)行排序，然后再對Kd-2

進(jìn)行排序，依次重復(fù)，直到對K0進(jìn)行排序后便成為一個(gè)有序序列。不必分成子序列，對每個(gè)關(guān)鍵字都是整個(gè)序列參加排序。10.6基數(shù)排序一、多關(guān)鍵字的排序例：記錄序列為(ABC,ACD,BBC,BAD,ACB，CAD)。MSD：ABCABCABCLSD:ACBBADABC

ACDACDACBABCCADACB

ACBACBACDBBCABCACD

BBCBADBADACDBBCBAD

BADBBCBBCBADACBBBC

CAD

CADCADCADACDCAD10.6基數(shù)排序一、多關(guān)鍵字的排序二、鏈?zhǔn)交鶖?shù)排序1．基數(shù)排序思想采用LSD方法進(jìn)行的排序。即借助“分配”和“收集”兩種操作對單邏輯關(guān)鍵字進(jìn)行排序的一種內(nèi)部排序方法。邏輯關(guān)鍵字可以看成由d個(gè)關(guān)鍵字復(fù)合而成的，而且其中的關(guān)鍵字都具有相同的取值范圍(如數(shù)字0≤Ki≤9，字母’A’≤Ki≤’Z’)，具有這樣特征的關(guān)鍵字，可按LSD進(jìn)行排序，只要從最低數(shù)位關(guān)鍵字起，按關(guān)鍵字的不同值將序列中記錄“分配”到R個(gè)隊(duì)列中后再“收集”，如此反復(fù)d次。這就是基數(shù)排序，這里“基”指的是R的取值范圍，實(shí)際上這里的“基數(shù)”有類似進(jìn)制數(shù)中基數(shù)的含義。

10.6基數(shù)排序2.基數(shù)排序的方法(1)首先根據(jù)所選擇的基數(shù)，設(shè)定r個(gè)隊(duì)列。(2)按LSD法，把n個(gè)關(guān)鍵字按最低位Kd的值分配到相應(yīng)隊(duì)列中。(3)再把r個(gè)隊(duì)列從小到大，首尾相接收集起來，此時(shí)n個(gè)關(guān)鍵字已按最低位Kd的值排好序，這稱為第一趟分配收集。(4)接著按次最低位的值，把第一趟收集起來的關(guān)鍵字再分配到相應(yīng)隊(duì)列中，然后進(jìn)行上述類似收集工作，這就完成了第二趟分配收集。對所有的關(guān)鍵字重復(fù)分配收集的過程。最后一趟分配收集的結(jié)果，就是一個(gè)按關(guān)鍵字從小到大有序的記錄序列。因此基數(shù)排序需要作d趟分配和收集。二、鏈?zhǔn)交鶖?shù)排序10.6基數(shù)排序3.基數(shù)排序的算法(1)記錄的存儲(chǔ)結(jié)構(gòu)在基數(shù)排序中，為避免大量移動(dòng)記錄，一般采用鏈表存儲(chǔ)結(jié)構(gòu)。(2)算法描述略。4．基數(shù)排序的例子二、鏈?zhǔn)交鶖?shù)排序10.6基數(shù)排序278063930589184083109008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]930278109063589184083008

f[0]f[1]f[2]f[3]f[4]

f[5]

f[6]f[7]f[8]f[9]尾指針頭指針930083278008109063589184第一趟分配和收集，使得關(guān)鍵字的最低位有序二、鏈?zhǔn)交鶖?shù)排序008