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

本章主要內(nèi)容：主要介紹以下各種內(nèi)部排序方法的基本思想、算法特點、排序過程及時間復(fù)雜度分析。本章重點：1.掌握各種排序方法中的高效方法(插入排序的希爾排序、交換排序的快速排序、選擇排序的堆排序、歸并排序)；2.掌握各種排序方法的時間復(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概

述

排序是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一個按關(guān)鍵字有序的序列。排序的目的之一是方便數(shù)據(jù)查找。對排序下一個確切的定義：假設(shè)含n個記錄的序列為：{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)部排序——如果在排序過程中，只使用計算機的內(nèi)存存放待排序所有記錄，稱這種排序為內(nèi)部排序。(或?qū)?nèi)存中的記錄進行的排序)。

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

10.1概

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

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

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

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

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

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

10.1概述6．排序記錄的存儲方式

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

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

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

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

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

無序區(qū)里的元素是r[2]～r[n]。(2)終態(tài)在排序操作完成之后，在有序區(qū)中包含整個數(shù)組r，而在無序區(qū)內(nèi)則為空。整個狀態(tài)稱為終態(tài)。一、插入排序概述10.2插入排序(3)基本操作步驟a.首先從無序區(qū)中取一個記錄，通常是第一個記錄；b.然后將其同有序區(qū)中的元素比較，并按其關(guān)鍵字值大小，把該記錄插入到有序區(qū)中的適當位置，這樣有序區(qū)中始終保持有序性；c.再從無序區(qū)中取一個記錄，重復(fù)b.操作，直到終態(tài)。一、插入排序概述10.2插入排序直接插入排序是一種最簡單的排序方法。它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。1．排序思想2．算法將序列中的第1個記錄看成是一個有序的子序列;從第2個記錄起逐個進行插入，直至整個序列變成按關(guān)鍵字非遞減有序序列為止。整個排序過程為進行n-1趟插入。同時后移記錄。二、直接排序概述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.時間復(fù)雜度時間復(fù)雜度為O(n2)。b.空間復(fù)雜度它只需要一個記錄的輔助空間，O(1)。二、直接排序概述10.2插入排序三、折半插入排序從減少“比較”和“移動”兩種操作的次數(shù)考慮，折半插入排序是直接插入排序的一種改進方法。1．折半插入排序思想由于插入排序的基本操作是在有序表中進行查找和插入，在有序表中用折半查找方法可以提高查找效率，利用折半查找的方法來進行插入排序可以減少比較次數(shù)，從而提高整個算法的執(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)算法效率時間復(fù)雜度仍為O(n2)?？臻g復(fù)雜度為O(1)，附加存儲空間同直接插入排序。三、折半插入排序10.2插入排序四、希爾排序(Shell)又稱“縮小增量排序”，屬于插入排序類的方法，但在時間效率上較前幾種排序方法有較大的改進。1.基本思想在直接插入排序中，當n較小時，排序的效率比較高。

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

四、希爾排序(Shell)10.2插入排序2.算法(1)按距離d將待排序數(shù)組r分成若干個小組，等距離者在同一個組中，初始距離為d1；(2)在每個小組中進行直接插入排序；(3)修改距離，選一個小于上次距離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)時間復(fù)雜度希爾排序算法的速度是所取的“增量”序列的函數(shù)，不論選擇什么樣的d，最后一個值必須是1。實驗表明，希爾排序的時間復(fù)雜度為O(nlog2n)。(3)空間復(fù)雜度為O(1)。四、希爾排序(Shell)10.2插入排序10.3

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

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個數(shù)比較3輪，n個數(shù)比較n-1輪4個數(shù)比較3次3個數(shù)比較2次2個數(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．算法分析時間復(fù)雜度O(n2)

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

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

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

重復(fù)這兩步直至low=high為止。二、快速排序10.3快速排序一趟排序結(jié)束，以樞軸為分界點將序列分為兩部分，樞軸前的記錄關(guān)鍵字小于樞軸記錄的關(guān)鍵字，樞軸后記錄的關(guān)鍵字大于樞軸記錄的關(guān)鍵字。(2)按照(1)的方法繼續(xù)對所分兩部分快速排序。整過快速排序是一個遞歸過程。初始關(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)時間復(fù)雜度快速排序的時間復(fù)雜度為O(nlogn)數(shù)量級。(3)空間復(fù)雜度由于快速排序是一個遞歸過程，需一個棧的附加空間，棧的深度為O(logn)。二、快速排序10.3快速排序10.4選擇排序一、簡單選擇排序

二、堆排序

基本思想每一次都在數(shù)組中選取關(guān)鍵字最小的一個記錄，送到已經(jīng)排好序的記錄序列的后面，直到完成整個排序工作。即每一趟在n-i+1個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。10.4選擇排序10.4選擇排序一、簡單選擇排序1.基本思想通過n-i次關(guān)鍵字的比較，在n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換。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)時間復(fù)雜度為O(n2)(3)空間復(fù)雜度為O(1)。

10.4選擇排序

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

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

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

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

ki≤k2i

ki≥k2i

ki≤k2i+1ki≥k2i+1

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

二、堆排序

10.4選擇排序

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

a.由一個無序序列建成一個堆。

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

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

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

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

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

二、堆排序例3：對于一個無序序列{49，38，65，97，76，13，27，49}進行堆排序。

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

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

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

二、堆排序

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

10.4選擇排序

二、堆排序作為小頂堆，產(chǎn)生的是一個遞減序列。作為大頂堆，產(chǎn)生的是一個遞增序列。(4)算法描述typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];for(j=2*s;j<=m;j*=2)//沿key較小的孩子結(jié)點向下篩選{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];

//堆頂記錄和最后一個記錄相互交換

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

二、堆排序

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

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

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

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

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

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

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

重復(fù)(1)、(2)，直到一個子表中的元素取完為止；(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.一趟歸并排序上述算法是將相鄰兩個有序序列2-路歸并。而一趟歸并排序則調(diào)用mergen/2h次，將前后相鄰且長度為h的有序段進行兩兩歸并，得到前后相鄰、長度為2h的有序段。3．歸并排序整個歸并排序就是調(diào)用“一趟歸并”過程若干次的過程。第一趟歸并時，有序子表長度為1，每趟歸并后有序子表的長度為上一次長度的2倍，當有序子表的長度為n時，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歸并排序四、算法描述二路歸并排序的時間復(fù)雜度等于歸并趟數(shù)與每一趟時間復(fù)雜度的乘積。而歸并趟數(shù)為log2n(當log2n

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

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

10.5歸并排序五、算法分析

10.6基數(shù)排序一、多關(guān)鍵字的排序二、鏈式基數(shù)排序

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

10.6基數(shù)排序一、多關(guān)鍵字的排序1．多關(guān)鍵字排序思想以撲克牌排序為例，討論多關(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個記錄的序列{R1,R2,…,Rn}，且每個記錄Ri中含有d個關(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)有序是指：對于序列中任意兩個記錄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進行排序，具有相同的K0值的記錄構(gòu)成一個子序列，再對關(guān)鍵字K1進行排序，依次重復(fù)，直到對Kd-1排序，最后將所有子序列依次連接在一起成為一個有序序列。將序列逐層分割若干子序列。(2)最低位優(yōu)先(LSD)

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

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

ACDACDACBABCCADACB

ACBACBACDBBCABCACD

BBCBADBADACDBBCBAD

BADBBCBBCBADACBBBC

CAD

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

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