,數(shù) 據(jù) 結(jié) 構(gòu) （Data Structure ）,第三章 排 序 （Sorting）,第三章 排序,3.1 排序的基本概念 3.2 簡單排序方法 3.3 先進(jìn)法排序方法 3.4 基數(shù)排序 3.5 各種排序方法的綜合比較,第三章 排序,待排序數(shù)據(jù)元素（記錄）的存儲結(jié)構(gòu)： typedef int KeyType /定義關(guān)鍵字類型為整型 typedef struct KeyType key; /關(guān)鍵字項 InfoType otherinfo; /其他數(shù)據(jù)項 RcdType; /記錄類型 本章的排序圖例只標(biāo)出了記錄的關(guān)鍵字。,3.1 排序的基本概念,3.1.1 排序的定義 3.1.2 排序的特性穩(wěn)定性與不穩(wěn)定性 3.1.3 排序的分類 3.1.4 內(nèi)排序的特點 3.1.5 選擇排序法,3.1 排序的基本概念,3.1.1 排序的定義 簡單定義：排序是按照關(guān)鍵字的非遞減或非遞增順序?qū)σ唤M記錄重新進(jìn)行整隊（或排列）的操作。 數(shù)學(xué)定義：假設(shè)含有n個記錄的序列為： r1, r2, ,rn (3-1) 它們的關(guān)鍵字相應(yīng)為k1, k2, ,kn,對式(3-1)的記錄序列進(jìn)行排序就是要確定序號1,2, ,n的一種排列p1, p2,pn使其相應(yīng)的關(guān)鍵字滿足如下的非遞增(減)關(guān)系： kp1 kp2 kpn (3-2) 也就是使式(3-2)的記錄序列重新排列成一個按關(guān)鍵字有序的序列rp1 rp2 rpn (3-3),3.1 排序的基本概念,3.1.2 排序的特性穩(wěn)定性與不穩(wěn)定性 當(dāng)待排記錄中的關(guān)鍵字ki(1,2,n)都不相同時，則任何一個記錄的無序序列經(jīng)排序后得到的結(jié)果是惟一的。 簡單地說，穩(wěn)定性排序-數(shù)據(jù)排序過后能使值相同的數(shù)據(jù)，保持原順序中之相對位置。反之，則稱為“不穩(wěn)定性排序” 。 若排序的序列中存在兩個或兩個以上關(guān)鍵字相等的記錄時，則排序得到的記錄序列的結(jié)果不惟一。 假設(shè)ki= kj (1i n, 1jn, ij )，且在排序前的序列中 ri 領(lǐng)先于rj (即ij ) 。若在排序后的序列中ri 總是領(lǐng)先于rj ，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中 rj領(lǐng)先于ri ，則稱所用的排序方法是不穩(wěn)定的。,3.1.2 排序的特性穩(wěn)定性與不穩(wěn)定性,3.1.3 排序的分類,根據(jù)在排序的過程涉及的存儲器不同，排序方法可分為兩類： 1.內(nèi)部排序（Internal Sort）：在排序進(jìn)行的過程中不使用計算機(jī)外部存儲器的排序過程。 選擇排序 插入排序 起泡排序 快速排序 歸并排序 堆排序 基數(shù)排序 2. 外部排序（External Sort）：在排序進(jìn)行的過程中需要對外存進(jìn)行訪問的排序過程。,3.1.4 內(nèi)排序的特點,待排序記錄序列的存儲結(jié)構(gòu)： const int MAXSIZE=20 /定義最大順序表的長度 typedef struct RcdType rMAXSIZE+1;/r0閑置或作為“哨兵” int length; /順序表的真正長度 SqList; /順序表類型 內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序序列的過程。通常在排序的過程中，參與排序的記錄序列可劃分兩個區(qū)域：有序序列區(qū)和無序序列區(qū)，其中有序序列區(qū)的的記錄已按關(guān)鍵字非遞減有序排列。 使有序序列中記錄的數(shù)目至少增加一個的操作稱為一趟排序。,3.1.5 選擇排序法,思想：在排序過程序中，依次從待排序的記錄序列中選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字值次小的記錄、，并分別有序序列中的第1個位置、第二個位置、，最后剩下一個關(guān)鍵字值最大的記錄位于序列的最后一個位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大排列的的有序序列。,Rj,Ri,一趟排序后,一趟排序開始,3.1.5 選擇排序法,一趟排序算法： void SelectPass(SqList / SelectPass,3.1.5 選擇排序法,整個算法： void SelectSort(SqList / for / SelectSort,3.1.5 選擇排序法,初始狀態(tài),i=1,i=2,i=3,i=4,i=5,i=6,i=7,3.1.5 選擇排序法,時間復(fù)雜度：O(n2) 空間復(fù)雜度：O(1) 優(yōu)點： 算法簡單；輔助空間少。 缺點： 效率低；不穩(wěn)定性排序。,3.2 簡單排序方法,3.2.1 插入排序 3.2.2 起泡排序,3.2.1 插入排序,基本思想：依次將記錄序列中的每一個記錄插入到有序段中，使有序段的長度不斷地擴(kuò)大。其具體的排序過程可以描述如下：首先將待排序記錄序列中的第一個記錄作為一個有序段，將記錄序列中的第二個記錄插入到上述有序段中，形成由兩個記錄組成的有序段，再將記錄序列中的第三個記錄插入到這個有序段中，形成由三個記錄組成的有序段，依此類推，每一趟都是將一個記錄插入到前面的有序段中。 假設(shè)當(dāng)前欲處理第i個記錄，則將Ri這個記錄插入到有序R1i-1 段中，從而使有序序列長度增1，直到所有記錄都插入到有序段中。一共需要經(jīng)過n-1趟就可以將初始序列的n個記錄重新排列成按關(guān)鍵字值大小排列的有序序列。,Ri,一趟排序后,一趟排序開始,3.2.1 插入排序,6,9,3,6,9,3,4,6,9,插入9,插入3,插入4,起始,3.2.1 插入排序,一趟排序算法： void InsertPass(SqList /插入到正確位置 /InsertPass,3.2.1 插入排序,整個算法： void InsertSort(SqList /插入到正確位置 /InsertSort,3.2.1 插入排序,初始狀態(tài),i=2,i=3,i=4,i=5,i=6,i=7,i=8,3.2.1 插入排序,時間復(fù)雜度 最佳狀況（正序）： O（n） 最壞狀況（逆序）：O(n2) 平均狀況： O(n2) 空間復(fù)雜度：O(1) 優(yōu)點： 算法簡單；穩(wěn)定排序。 缺點： 花費較長的排序時間。,3.2.2 起泡排序,思想：通過對無序序列區(qū)中的記錄進(jìn)行相鄰記錄關(guān)鍵字間的“比較”和記錄位置的“交換”實現(xiàn)關(guān)鍵字較小的記錄向“一頭”漂移，而關(guān)鍵字較大的記錄向“另一頭”下沉，從而達(dá)到記錄按關(guān)鍵字非遞減順序有序排列的目標(biāo)。,i,一趟排序后,一趟排序開始,3.2.2 起泡排序,96,8,96,54,8,37,3.2.2 起泡排序,一趟排序算法： void BubblePass(SqList / if /for /BubblePass,3.2.2 起泡排序,整個算法： void BubbleSort(SqList / if /for /for /BubbleSort,3.2.2 起泡排序,改進(jìn)的起泡算法： void BubbleSort(SqList /while /BubbleSort,3.2.2 起泡排序,初始狀態(tài),i=8,i=7,i=6,i=5,i=3,i=2,3.2.2 起泡排序,時間復(fù)雜度 最佳狀況：O(n) 最壞狀況：O(n2) 平均狀況：O(n2) 空間復(fù)雜度： O(1) 優(yōu)點： 算法簡單；空間效率高；結(jié)點順序好效率就高；穩(wěn)定的排序法。 缺點： 結(jié)點順序不好則效率過低。,3.3 先進(jìn)排序方法,3.3.1 快速排序 3.3.2 歸并排序 3.3.3 堆排序（略）,3.3.1 快速排序,基本思想： 通過一趟排序?qū)⒋庞涗浄指畛上噜彽膬蓚€區(qū)域，其中一個區(qū)域中記錄的關(guān)鍵字均比另一個區(qū)域中記錄的關(guān)鍵字小（區(qū)域內(nèi)不一定有序），則可分別對這兩個區(qū)域的記錄進(jìn)行再排序，以達(dá)到整個序列有序。 假設(shè)將待排序的原始記錄序列為（rs, rs+1, rt-1,rt），則一趟快速排序的基本操作是：任選一個記錄（通常選rs ），以他的關(guān)鍵字作為“樞軸”，凡序列中關(guān)鍵字小于樞軸的記錄均移動至該記錄之前；反之，凡序列中關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列Rst將分割成兩部分：Rsi-1和Ri+1t，且使 Rj.keyRi.key rj.key (s j i-1) 樞軸 (i +1j t),3.3.1 快速排序,一趟排序具體操作過程：假設(shè)樞軸記錄的關(guān)鍵字為pivotkey，附設(shè)兩個指針low和high，它們的初值分別為s和t。 將樞軸記錄復(fù)制到臨時變量 檢測指針high所指記錄 若Rhigh.key=pivotkey，則減小high 否則將Rhigh移至指針low所指位置 檢測指針?biāo)赣涗?若Rlow.key=pivotkey，則增加low 否則將Rlow移至指針high所指位置 重復(fù)進(jìn)行，直至low和high指向同一位置。,3.3.1 快速排序,17,14,65,28,36,3.3.1 快速排序,一趟排序算法： int Partition(RcdType R,int low,int high) int pivotkey; R0=Rlow; /將樞軸放在閑置單元 pivotkey=Rlow.key; /將樞軸的關(guān)鍵字放在pivotkey while(low=pivotkey) high-; /high往左找，比小時停止 if(lowhigh) Rlow+=Rhigh;/把比樞軸小的記錄移到低端 while(lowhigh /返回樞軸位置 /Partition,3.3.1 快速排序,整個算法： void QSort(RcdType R,int s,int t) /對記錄序列Rst進(jìn)行快速排序 if(s1 pivotLoc=Partition(R,s,t); /對Rst進(jìn)行一次劃分 QSort(R,s,pivotLoc-1); /對低端子序列遞歸排序 QSort(R,s,pivotLoc-1); /對高端子序列遞歸排序 /if /QSort void QuickSort(SqList /QuickSort,一趟快速排序示例,3.3.1 快速排序,初始狀態(tài),一次劃分,3.3.1 快速排序,時間復(fù)雜度： 最佳狀況(當(dāng)每次分割的兩個區(qū)塊都均勻大小時)：O(n*log2n) 最壞狀況(每次分割的兩個區(qū)塊大小相差很多時)：O(n2) 平均狀況： O(n*log2n) 空間復(fù)雜度：使用遞歸的深度 最佳狀況: O(log2n) 最壞狀況: O(n) 平均狀況：介于O(log2n) 和O(n)之間 優(yōu)點： 平均時間復(fù)雜度低，適用于完全隨機(jī)的序列。 缺點： 不穩(wěn)定性排序;空間效率低；結(jié)點順序不好則效率低。,3.3.2 歸并排序,歸并排序法是利用“歸并”操作的一種排序方法。 基本思想： 將待排序的原始記錄序列Rst中取一個中間位置(s+t)/2，先分別對子序列Rs(s+t)/2和R(s+t)/2+1 t進(jìn)行遞歸的歸并排序，然后進(jìn)行一次歸并處理。,3.3.2 歸并排序,歸并排序基本操作將兩個位置相鄰的有序記錄子序列Rim和Rm+1n歸并為一個有序記錄序列Rn，算法如下： void Merge(RcdType SR,RcdType TR,int i,int m,int n) /對有序的Rim和Ri+1n歸并為一個有序的Rn for(j=m+1,k=i;i=m /將剩余的Rjn復(fù)制到TR /Merge,3.3.2 歸并排序,整個算法： void MSort(RcdType SR,RcdType TR1, int s,int t) /對記錄序列Rst進(jìn)行歸并排序，排序后存入TR1st RcdType TR2t-s+1; /開設(shè)存放中間結(jié)果的輔助空間 if(s=t) TR1s=SRs;/遞歸出口 else m=(s+t)/2; /將SRst平分為SRsm和SRm+1t MSort(SR,TR2,s,m); /遞歸地將SRsm歸并為TR2sm MSort(SR,TR2,m+1,t); /遞歸地將SRm+1t歸并為TR2m+1t Merge(TR2,TR1,s,m,t); /將TR2sm和TR2m+1t歸并到TR1st /else /MSort void MergeSort(SqList /MergeSort,3.3.2 歸并排序,2,3,1,4,3.3.2 歸并排序,時間復(fù)雜度：O(n*log2n) 空間復(fù)雜度：O（n） 優(yōu)點： 可用來處理大量數(shù)據(jù)的排序； 是穩(wěn)定性排序。,3.3.3 堆排序,累堆的外觀為完全二叉樹的根最小或最大樹，而累堆排序所用的堆是“最大堆”（堆頂元素最大）。,父節(jié)點： Vi 子節(jié)點： V2i （左） V2i+1 （右）,(2) 將此二叉樹建成最大堆,(1) 將n個數(shù)存入數(shù)組,(3) 取出樹根，將剩下的節(jié)點在排成堆,(4) 重復(fù)（3），直到所有值均以輸出,3.3.3 堆排序,n=8n/2=4,（1）考慮n4,n4 n8 不變,3.3.3 堆排序,（2）考慮n3,n3 n7 交換,3.3.3 堆排序,（3）考慮n2,n4n2 n5n2 不變,3.3.3 堆排序,（4）考慮n1,n1 n2 交換,3.3.3 堆排序,考慮n2,n4 n2 交換,3.3.3 堆排序,考慮n4,n4n8 不變,最大堆,3.3.3 堆排序,取出樹根與最后一個節(jié)點交換,n1n8,n1n7成堆,3.3.3 堆排序,n1n7,n1n6成堆,3.3.3 堆排序,n1n6,n1n5成堆,3.3.3 堆排序,n1n5,n1n4成堆,3.3.3 堆排序,n1n4,n1n3成堆,3.3.3 堆排序,n1n3,n1n2成堆,3.3.3 堆排序,n1n2,void HeapSort(int *heap,int index) int i,j,temp; for(i=index/2;i=1;i-) createHeap(heap,i,index); for(i=index-1;i=1;i-) heap1heapi+1; /借助temp交換 createHeap(heap,1,i); ,void createHeap(int *heap,int root,int index) int i,j,temp,finish=0; j=2*root;temp=heaproot; while(j=heapj) finish=1; else heapj/2=heapj; j*=2; heapj/2=temp; ,堆排序算法,調(diào)用HeapSort(list,index);,3.3.3 堆排序,時間復(fù)雜度：O(nlog2n) 空間復(fù)雜度：O(1) 優(yōu)點： 最壞情況下時間復(fù)雜度也僅為O(nlog2n) 。 缺點： 運(yùn)行時間主要耗費在建初始堆和調(diào)整堆上，排序數(shù)據(jù)較少時，不值得提倡。,3.4 基數(shù)排序,基本思想： 基數(shù)排序：假設(shè)記錄的邏輯關(guān)鍵字由多個關(guān)鍵字構(gòu)成，每個關(guān)鍵字可能取r個值，則只要從最低位關(guān)鍵字起，按關(guān)鍵字的不同值將記錄“分配”到r個隊列之后再“收集”在一起，如此重復(fù)趟，最終完成整個記錄序列的排序?！盎鶖?shù)”指的是r的取值范圍。 例：關(guān)鍵字為三位整數(shù)，其關(guān)鍵字構(gòu)成是（k2, k1 , k0 ）， k2, k1 , k0 的基數(shù)為10 例：關(guān)鍵字為5個字母，其關(guān)鍵字構(gòu)成是（ k4, k3 , k2, k1 , k0 ）， kj,(0收集-分配-收集,基數(shù)排序 示例,3.4 基數(shù)排序,記錄數(shù)組A,計數(shù)數(shù)組（個位）,（a）初始狀態(tài)和對“個位數(shù)”計數(shù)的結(jié)果,計數(shù)數(shù)組累加,記錄數(shù)組B,30,63,83,74,94,25,05,78,18,09,89,69,（b）計數(shù)器的累加結(jié)果和記錄“復(fù)制”后的狀態(tài),2,11,6,5,4,10,3,0,1,9,8,7,3.4 基數(shù)排序,（b）計數(shù)器的累加結(jié)果和記錄“復(fù)制”后的狀態(tài),計數(shù)數(shù)組（十位）,計數(shù)數(shù)組累加,記錄數(shù)組A,05,09,18,25,30,63,69,74,78,83,89,94,（c）對“十位數(shù)”計數(shù)、累加和記錄“復(fù)制”后的狀態(tài),記錄數(shù)組B,6,10,1,2,8,0,3,11,7,9,5,4,3.4 基數(shù)排序,基數(shù)排序需說明的數(shù)據(jù)結(jié)構(gòu) const int MAX_NUM_OF_KEY=6 /關(guān)鍵字項數(shù)的最大值 const int RADIX=10 /關(guān)鍵字的基數(shù) const int MAXSIZE=10000 typedef struct KeysType keysMAX_NUM_OF_KEY; /關(guān)鍵字?jǐn)?shù)組 InfoType otheritems; /其他數(shù)據(jù)項 /int bitsnum; /關(guān)鍵字的位數(shù) RcdType; /基數(shù)排序中的記錄類型,3.4 基數(shù)排序,一趟基數(shù)排序算法： void RadixPass(RcdType A,RcdType B, int n,int i) /對數(shù)組A中記錄關(guān)鍵字的“第i位”計數(shù)，并累計count的值 /將數(shù)組A中復(fù)制到數(shù)組B中 for(j=0;j=0;k-) /從右端開始復(fù)制記錄 j=Ak.keysi; Bcountj-1=Ak; countj-; /for /RadixPass,3.4 基數(shù)排序,整個算法： void RadixSort(SqList /while /RadixSort,Typedef struct RcdType *r; int bitnum; int length; SqList,3.4 基數(shù)排序,時間復(fù)雜度： 最佳狀況、最壞狀況、平均狀況：O(d*n) 空間復(fù)雜度： 最佳狀況、最壞狀況、平均狀況：O(n) 優(yōu)點： 平均時間復(fù)雜度低；穩(wěn)定性排序。 缺點： 空間效率低。,3.5 各種排序方法的綜合比較,3.5.1 時間性能 3.5.2 空間性能 3.5.3 排序方法穩(wěn)定性能 3.5.4 小結(jié),3.5.1 時間性能,按平均的時間性能來分，有三類排序方法： 時間復(fù)雜度O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中快速排序目前被認(rèn)為是最快的一種排序方法，后兩者之比較，在n值較大的情況下，歸并排序較堆排序更快。 時間復(fù)雜度O(n2 )的方法有：插入排序、起泡排序和選擇排序，其中以插入排序為最常用，特別是已按關(guān)鍵字基本有序排列的記錄序列尤為如此，選擇排序過程中記錄移動次數(shù)最少。 當(dāng)待排記錄序列按關(guān)鍵字順序有序時，插入排序和起泡排序能達(dá)到O(n)的時間復(fù)雜度；而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2) 選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變，人們應(yīng)事先對要排序的記錄關(guān)鍵字的分布情況有所了解，才可1對癥下藥，選擇有針對性的排序方法。 當(dāng)待排序記錄中其他各數(shù)據(jù)項比關(guān)鍵字占有更大的數(shù)據(jù)量時，還應(yīng)考慮到排序過程中移動記錄的操作時間，起泡排序效率最低。,3.5.2 空間性能,空間性能指的是排序過程中所需的輔助空間大小。 所有的簡單排序方法（包括：插入、起泡和選擇排序）和堆排序的空間復(fù)雜度均為O（1）. 快速排序為O(logn),為遞歸程序執(zhí)行過程中棧所需的輔助空間。 歸并排序和基數(shù)排序所需輔助空間最多，其空間復(fù)雜度為O(n)。,3.5.3 排序方法穩(wěn)定性能,穩(wěn)定的排序方法指的是對于兩個關(guān)鍵字相等的記錄在經(jīng)過排之后，不改變它們在排序之前在序列中的相對位置。 除快速排序和堆排序是不穩(wěn)定的排序方法外，本章討論的其他排序訪方法都是穩(wěn)定的，例如， 例如：對關(guān)鍵字序列（41，3，42，2）進(jìn)行快速排序，其結(jié)果為（2，3，42，41）。 “穩(wěn)定性”是由方法本身決定的，一般來說，排序過程中所進(jìn)行的比較操作和交換數(shù)據(jù)僅發(fā)生在相鄰的記錄之間，沒有大步距的數(shù)據(jù)調(diào)整時，則排序方法是穩(wěn)定的。,3.5.4 小結(jié),3.5.4 小結(jié),若待排序的記錄個數(shù)n值較?。ɡ鏽30），則可選用插入排序法，若記錄所含數(shù)據(jù)項較多，所占存儲量大時，應(yīng)選用選擇排序法，反之，若待排序的記錄個數(shù)n值較大時，應(yīng)選用快速排序法，若待排序記錄關(guān)鍵字有“有序”傾向時，就慎用快速排序，而寧可選用歸并排序或堆排序。 快速排序和歸并排序在n值較小時的性能不及插入排序，可將它們和插入排序“混合”使用，如在快速排序劃分子區(qū)間的長度小于某值時，轉(zhuǎn)而調(diào)用插入排序，或者對待排記錄序列先逐段進(jìn)行插入排序，然后再利用“歸并操作”進(jìn)行兩兩歸并直至整個序列有序為止。 基數(shù)排序的時間復(fù)雜度為O（d*n），因此特別適合于待排記錄數(shù)n值很大，而關(guān)鍵字“位數(shù)d”較小的情況。并且還可以