1、數 據 結 構 第7章 排序 概述 什么是排序？ 排序是計算機內經常進行的一種操作，其目的是將一 組“無序”的元素序列調整為“有序”的元素序列。 排序的分類 待排序元素關鍵字個數 單關鍵字排序 多關鍵字排序 待排序元素的存儲介質 內部排序：排序過程不需要訪問外存便能完成 外部排序：排序過程需要訪問外存才能完成 概述 內部排序的類別 插入類：直接插入排序、折半排序、2-路插入排序、 希爾排序 分劃類：冒泡排序、快速排序 選擇類：簡單選擇排序、堆排序 歸并類：2-路歸并排序 其他方法：基數排序 概述 排序的兩個基本操作 比較兩個關鍵字大小 將記錄從一個位置移動到另一個位置 穩定性 待排序列 a1,

2、 a2, an，其相應的關鍵字序列 k1, k2, kn，假設ki = kj ( 1i, jn且i j)，且在排序前的 序列中ai領先于 aj。 若在排序后的序列中ai仍領先于 aj，則稱所用的排序方 法是穩定的，反之，則稱其是不穩定的。 7.1 插入類排序 插入類排序 將待排序元素逐個插入到已排好序的有序表中，從而 得到一個新的有序表。 應用插入類排序思想的算法 直接插入排序 折半插入排序 2-路插入排序 希爾排序 7.1.1 直接插入排序 排序過程 整個排序過程為n-1趟插入，即先將序列中第1個記錄看 成是一個有序子序列，然后從第2個記錄開始，逐個進行 插入，直至整個序列有序 第i趟直接插

3、入排序的基本思想 有序序列A0.i-1 Ri 無序序列 Ai.n-1 有序序列A0.i無序序列 Ai+1.n-1 直接插入排序例 7.1.1 直接插入排序 直接插入排序算法 / 直接插入排序,數組data用于存放待排序元素，n為待排序元素個數 template void InsertSort(ElemType data, int n) ElemType tmp; int i, j; for (i = 1; i datai - 1) continue; tmp = datai; / 保存待插入的元素 datai = datai - 1; for ( j = i - 1; j 0 j-) data

4、j = dataj - 1;/ 元素后移 dataj = tmp; / 插入到正確位置 7.1.1直接插入排序 算法評價 時間復雜度 正序 元素移動次數：0 元素比較次數：n-1 逆序 元素移動次數： 元素比較次數： 平均情況 O(n2) 2 (1)(1)/ 2 n i in n 2 (1)(4)(1)/ 2 n i inn 7.1.2 折半插入排序 因為 A0.i-1 是一個按關鍵字有序的有序序列，則可以利 用“折半查找”實現“在A0.i-1中查找Ai的插入位置” ，如此實現的插入排序為折半插入排序。 減少元素關鍵字間的比較次數，但元素移動次數不變 折半插入排序例 折半插入排序算法 7.1.

5、2 折半插入排序 template void BInsertSort(ElemType data, int n) ElemType tmp; int i, j, mid, low, high; for (i = 1; i n; i+) tmp = datai, low = 0, high = i-1; while (low = high) / 在datalow.high中查找插入的位置 mid = (low + high) / 2; / 折半 if (tmp = low; j-) dataj + 1 = dataj; / 元素后移 datalow = tmp; / 插入到正確位置 7.1.3

6、2-路插入排序 將插入區域分成大致等長的兩段，選擇性地插人到其中一 段 排序過程 設置一個和原數組data 同類型，同規模的是數組d，并 將其視為循環數組（即位置n-1和0邏輯上相鄰） d0 = data0，將d0看作為排好序中處于中間位置的 元素，從第二個元素data1開始做以下操作 如果dataid0，將datai插入d0之后的有序序列， 并保持插入后有序；反之，將其插入d0之前的有序序 列，并保持插入后有序 2-路插入排序例 7.1.3 2-路插入排序 算法評價 減少約為n2/8的元素移動次數 基準元素選取的好壞直接影響排序的效率 7.1.4 希爾排序 希爾排序又稱縮小增量排序 將記錄序

7、列分成若干子序列，分別對每個子序列進行 插入排序。 例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 其中，d 稱為增量，它的值在排序過程中從大到小逐 漸縮小，直至最后一趟排序減為 1。 希爾排序例 34288179 22165524996446 設增量d=5 16282479 22345581996446 設增量d=3 1622245528346446997981 設增量d=1 1622242834465564798199 7.1.4 希爾排序 希爾排序算法 template

8、 void ShellSort(ElemType data, int increments , int n, int incrementsLength) int i, j, k; ElemType tmp; for ( k = 0; k incrementsLength; k+) / 進行以incrementsk為增量的排序 for ( i = incrementsk; i = incrementsk; j -= incrementsk) if ( tmp = dataj - incrementsk) break; dataj = dataj - incrementsk; dataj = tm

9、p; 7.1.4 希爾排序 特點 子序列的構成不是簡單的“逐段分割”，而是將相隔 某個增量的元素組成一個子序列 希爾排序可提高排序速度，因為 分組后n值減小，n更小，而T(n)=O(n),所以T(n)從 總體上看是減小了 關鍵字較小的記錄跳躍式前移，在進行最后一趟增 量為1的插入排序時，序列已基本有序 7.1.4 希爾排序 算法評價 算法效率依賴于增量序列的選擇 時間復雜度 在O(n3/2)到O(n7/6)之間 增量序列的取法 最后一個增量必須為1 其他增量間保持“互質” 7.2 分劃類排序 分劃類排序 通過一趟劃分確定一個元素在序列中的位置，保證在 它之前的一組元素不比它大，之后的不比它小，

10、接著 對兩組元素繼續分劃，直至待排序列有序。 應用插入類排序思想的算法 冒泡排序 快速排序 7.2.1 冒泡排序 排序過程 將第一個和第二個元素的關鍵字進行比較，若為逆序 ，則將兩元素互換；接著比較第二個和第三個元素的 關鍵字，依次類推，直至最后兩個元素的完成比較， 這稱為第一趟冒泡排序。第一趟排序分劃出一組元素 個數為n-1的待排序列和一個關鍵字最大的元素。 第i趟對前n - i + 1個的元素進行類似的排序操作，得到 一組元素個數為n - i的待排序列和一個關鍵字次大的元 素。 這樣不斷分劃直至一趟分劃時無元素互換為止。 7.2.1 冒泡排序 假設在排序過程中，元素序列A1.n的狀態為：

11、無序序列無序序列A1.n-i+1有序序列有序序列 An-i+2.n n-i+1 無序序列無序序列A1.n-i有序序列有序序列 An-i+1.n 比較相鄰記錄，將關鍵字最大比較相鄰記錄，將關鍵字最大 的記錄的記錄交換到交換到 n-i+1 的位置上的位置上 第第 i 趟起泡排序趟起泡排序 冒泡排序例 7.2.1 冒泡排序 冒泡排序算法 template void BubbleSort(ElemType data, int n) int lastSwapIndex = n - 1; / 用于記錄最后一次交換的元素下標 int i, j; for (i = lastSwapIndex; i 0;i =

12、 lastSwapIndex) lastSwapIndex = 0; for (j = 0; j dataj + 1) Swap( dataj,dataj + 1); lastSwapIndex = j; 7.2.1 冒泡排序 算法評價 最好情況（正序） 移動次數：0 比較次數：n-1 最壞情況（逆序） 移動次數：3n(n-1)/2 比較次數：n(n-1)/2 T(n) = O(n2) 7.2.2 快速排序 一趟快速排序 選第一個待排序元素作為樞軸（或支點pivot），根據 樞軸將待排序列劃分為兩個子列 這兩個子列必須滿足以下條件：一個子列的元素關鍵 字都不大于樞軸的關鍵字，另一個子列的元素關

13、鍵字 都不小于樞軸的關鍵字。 7.2.2 快速排序 首先對無序的記錄序列進行“一次劃分”，之后分別對分 割所得兩個子序列“遞歸”進行快速排序。 無無 序序 的的 元元 素素 序序 列列 無序記錄子序列無序記錄子序列(1)無序子序列無序子序列(2) 樞軸樞軸 一次劃分一次劃分 分別進行快速排序分別進行快速排序 7.2.2 快速排序 排序過程 對待排序列A進行快速排序的遞歸算法QuickSort(A)可 以描述如下： 如果A中元素的個數為0或1，則返回；否則，繼續 選取A中的一個元素p作為樞軸（pivot） 將A中剩下的元素“劃分”成兩個不相交的集合： QuickSort (A1), p, Qui

14、ckSort (A2) 12 | ., | .AxApxkeypkeyAxApxkeypkey 一趟快速排序例 7.2.2 快速排序 / 對datalow.high進行分劃，確定樞軸的位置，并返回其所在位置 / 子序列中，在樞軸之前（后）的元素均不大（小）于它 template int Partition(ElemType data , int low , int high) ElemType pivot = datalow; / 用子序列的頭元素作為樞軸 while (low high) while (low = pivot) high-; datalow = datahigh;/ 比樞軸小

15、的元素移到低端 while (low = datalow) low+; datahigh = datalow;/ 比樞軸大的元素移到高端 datalow = pivot;/ 確定樞軸的合適位置 return low;/ 返回樞軸的位置 一趟快速排序算法 7.2.2 快速排序 快速排序算法 / 對databegin.end進行快速排序 template void QuickSort(ElemType data, int begin, int end) if (begin = end) / data長度小于等于時返回 return; int pivot = Partition(data , beg

16、in , end); / 對databegin.end進行分劃 QuickSort(data , begin , pivot - 1); / 對低端子列進行遞歸排序 QuickSort(data , pivot + 1, end); / 對高端子列進行遞歸排序 / 快速排序 template void QuickSort(ElemType data, int n) if (n 2) return; QuickSort(data, 0, n-1); 7.2.2 快速排序 算法分析 最好情況 每次中間值作為樞軸 T(n)=O(nlog2n) 最壞情況 每次總選最大或最小元素作為樞軸 T(n)=O(

17、n) 平均情況 T(n)= O(nlogn) 三數中值分割法 7.3 選擇類排序 選擇類排序 逐趟掃描未排序的部分，從中選取一個元素移動到合 適的位置 。 應用選擇類排序思想的算法 簡單選擇排序 樹形選擇排序 堆排序 7.3.1 簡單選擇排序 假設排序過程中，待排記錄序列的狀態為： 有序序列有序序列A1.i-1無序序列無序序列 Ai.n 第第 i 趟簡單選擇排序趟簡單選擇排序 從中選出關鍵字最小的從中選出關鍵字最小的 元素元素 有序序列有序序列A1.i無序序列無序序列 Ai+1.n 7.3.1 簡單選擇排序 排序過程 第一趟掃描所有待排序元素，找出關鍵字最小的元素 并將它與第一個元素進行交換；

18、 第i趟，掃描待排序列中剩余n - i + 1個元素，找出關鍵 字最小的元素與序列中第i個位置上的元素交換 重復上述操作,直到所有的元素都放到正確的位置上為 止 簡單選擇排序例 簡單選擇排序算法 7.3.1 簡單選擇排序 template void SelectionSort(ElemType data, int n) int i, j, min; for (i = 0; i n; i+) min = i; for (j = i + 1; j n; j+) / 選擇datai+1.n-1中最小的元素 if ( dataj datamin) min = j; Swap(datai,datamin

19、); / 將datai與第i小的元素交換 7.3.1 簡單選擇排序 算法分析 最好情況 比較次數： 移動次數：0 最壞情況 比較次數： 移動次數： 3(n - 1) T(n)=O(n) 1 2 1 1 ()() 2 n i ninn 1 2 1 1 ()() 2 n i ninn 7.3.2 樹形選擇排序 簡單選擇排序中一趟排序中的比較操作可能在前一趟中已 經做過，但前一趟中未保存這些比較結果，因此在后一趟 的排序中又重復執行了這些操作。為了解決這個問題，樹 形選擇排序應運而生。 算法思想 先將n個元素的關鍵字兩兩比較，然后將其中 個較小者 兩兩比較，如此重復，不斷的淘汰較大者，最終選出 關鍵

20、字最小的元素 樹形選擇排序例 7.3.3 堆排序 堆的定義：堆是滿足下列性質的數列a1, a2, ，an： 或或 2 21 ii ii aa aa 2 21 ii ii aa aa (小頂堆)(大頂堆) 12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 小頂堆 12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 不是堆 7.3.3 堆排序 若將該數列視作完全二叉樹，則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子 ai a2i a2i+1 12 3627 65 49817355 403498 不是堆不是堆 1

21、4 7.3.3 堆排序 堆排序即是利用堆的特性對記錄序列進行排序的一種排序 方法。 建大頂堆 98, 53, 55, 18, 4, 22, 24 24, 53, 55, 18, 4, 22, 98 交換 98 和 24 重新調整為大頂堆 55, 53, 24, 18, 4, 22, 98 22, 18, 53, 98, 4, 24, 55 經過篩選 7.3.3 堆排序 排序過程 將待排序列A0n-1調整為大頂堆； 將堆頂元素A0（即關鍵字最大的元素）與堆尾元素（ 即堆中最后一個元素）交換，從堆中除去堆尾元素(即 關鍵字最大的元素)，同時調整堆中剩余元素，使它們 恢復堆屬性； 反復進行步驟2，直

22、至堆中元素個數為1。 7.3.3 堆排序 堆排序需解決的兩個問題： 如何將初始的待排序列調整為一個堆？ 因堆頂元素與堆尾元素交換后，新的堆頂元素可能破 壞了堆屬性，如何再調整成為堆？ 第二個問題解決方法 輸出堆頂元素之后，以堆中最后一個元素替代之；然 后將根結點值與左、右子樹的根結點值進行比較，并 與其中較大者進行交換；重復上述操作，直至葉子結 點，將得到新的堆，稱這個從堆頂至葉子的調整過程 為“篩選” 例例 堆排序調整例 堆排序調整例 7.3.3 堆排序 第一個問題解決方法 從最后一個非葉子結點（即第 個元素）開始對所有非 葉子結點調整操作 建堆例 含7個元素的無序序列（22, 18, 53

23、, 98, 4, 24, 55） 22 18 5524498 22 5518 5324498 22 5598 5324418 98 5522 5324418 53 調整堆算法 7.3.3堆排序 / 將datai.n-1中的元素調整為大頂堆 template void HeapAdjust(ElemType data, int i, int n) ElemType tmp; int child; for ( tmp = datai; LeftChild(i) datachild) / 取較大的孩子結點 child+; if (tmp datachild) datai = datachild; e

24、lse break; datai = tmp; 7.3.3 堆排序 堆排序算法 / 堆排序 template void HeapSort(ElemType data, int n) int i; for (i = n/2; i = 0; i-)/ 建堆 HeapAdjust(data, i, n); / 將堆的根結點與最后的一個葉結點交換,并進行調整 for (i = n - 1;i 0; i-) Swap(data0,datai); HeapAdjust(data, 0, i); 7.3.3 堆排序 算法評價 最好情況：O(n) 最壞情況：O(nlogn) 平均： O(nlogn) 7.4

25、歸并類排序 歸并 將兩個有序列合并成為一個新的有序列 2-路歸并排序 將相鄰的元素兩兩歸并，得到 個長度為2或1的有序子 序列，再將這些子序列兩兩歸并，如此重復，直至得 到一個長度為n的有序列為止 2-路歸并排序例 “歸并”算法 / 將數組data中，lptr.rptr-1rptr.rightEnd兩部分的元素進行合并 / tmpArr為合并時的輔存空間 template void Merge(ElemType data, ElemType tmpArr, int lptr , int rptr, int rightEnd) int leftEnd = rptr - 1; int ptr,i;

26、 ptr = i = lptr; while (lptr = leftEnd else tmpArrptr+ = datarptr+; while (lptr = leftEnd) tmpArrptr+ = datalptr+; while (rptr = rightEnd) tmpArrptr+ = datarptr+; for (;i = rightEnd; i+) datai = tmpArri; 2-路歸并排序算法 template void MPass(ElemType data, ElemType tmpArr, int n, int mergeLength) int i = 0;

27、 while (i = n - 2 * mergeLength) Merge(data, tmpArr, i, i+mergeLength, i+2*mergeLength-1); i = i + 2 * mergeLength; if (i + mergeLength n) Merge(data, tmpArr, i, i + mergeLength, n - 1); / 2-路歸并算法非遞歸實現 template void MergeSortNonRecursion(ElemType data, int n) int mergeLength = 1; / mergeLength記錄每趟歸并

28、的步長 ElemType* pArr = NULL; pArr = new ElemTypen;/ pArr為合并時的輔存空間 while (mergeLength n) MPass(data, pArr, n, mergeLength); mergeLength *= 2; delete pArr; 7.4 歸并類排序 算法評價 T(n)= O(nlogn) 缺點 空間復雜度為O(n) 算法中需要較多的拷貝工作 7.5 基數排序 無須比較關鍵字 通過“分組”和“收集”兩個過程來完成排序任務 借助“多關鍵字排序”的思想 7.5.1 多關鍵字的排序 假設待排序列 a1, a2, an中每個元素a

29、i有d個關鍵字 ， 該序列對關鍵字 有序是指： 對序列中任意兩個元素ai和aj(1 i j n)都滿足下列有 序關系： 當兩個元素的所有關鍵字都相等時，則必須保持其穩 定性。其中 稱為最主位關鍵字， 稱為最次位關鍵 字。 12 (,.,) d iii k kk 1212 (,.,)(,.,) dd iiijjj k kkk kk 1 k d k 7.5.1 多關鍵字的排序 排序方法 最高位優先法（MSD） 先對最高位關鍵字k1排序，將序列分成若干子序列 ，每個子序列有相同的k1值 接著讓每個子序列對次關鍵字k2排序，又分成若干 更小的子序列 依次重復，直至就每個子序列對最低位關鍵字kd排 序；

30、最后將所有子序列依次連接在一起成為一個有 序序列 最低位優先法（LSD） 從最低位關鍵字kd起進行排序，然后再對高一位的 關鍵字排序，依次重復，直至對最高位關鍵字 k1排序后，便成為一個有序序列 7.5.1 多關鍵字的排序 MSD與LSD不同特點 按MSD排序，必須將序列逐層分割成若干子序列，然 后對各子序列分別排序 按LSD排序，不必分成子序列，對每個關鍵字都是整個 序列參加排序；并且可不通過關鍵字比較，而通過若 干次分配與收集實現排序 7.5.2 基數排序 基數排序依次根據各關鍵字分量進行“分配”、“收集” 完成排序 在單關鍵字排序中，一個關鍵字可以看作由若干個關鍵字 分量復合而成，如整數

31、可視為若干數位的集合。 基數排序例 7.5.2 基數排序 用數組實現的基數排序算法 void RadixSort(int data, int n) const int radix = 10; const int digits = 10; int i,j,k,factor; queue queuesradix; for ( i = 0,factor = 1; i digits;i+,factor *= radix) for ( j = 0;j n; j+) queues(dataj/factor)%radix.push(dataj); / 分配 for ( k = j = 0; j radix;

32、 j+,k+) / 收集 while (!queuesj.empty() datak = queuesj.front(); queuesj.pop(); 7.5.2 基數排序 用數組實現基數排序的缺點 雖然不需要進行“比較”操作，但仍需要大量的元素 移動操作 還需要額外的空間來存放10個隊列 鏈式基數排序 用鏈表作存儲結構的基數排序 7.5.2 基數排序 鏈式基數排 設置10個隊列，fronti和reari分別為第i個隊列的頭指 針和尾指針 第一趟分配對最低位關鍵字（個位）進行，改變元素 的指針值，將鏈表中的元素分配至10個鏈隊列中，每 個隊列記錄的關鍵字的個位相同 第一趟收集是改變所有非空隊

33、列的隊尾記錄的指針域 ，令其指向下一個非空隊列的隊頭記錄，重新將10個 隊列鏈成一個鏈表 重復上述兩步，進行第二趟、第三趟分配和收集，分 別對十位、百位進行，最后得到一個有序序列 鏈式基數排序（第一趟）例 靜態鏈表 class SLList struct Node int keyDIGITS; int info; int next; ; friend ostream public: SLList():data(NULL),length(0); SLList(); void Arrange(); /重排 void Init(int arr,int n); void RadixSort(); /鏈

34、式基數排序 private: void Distribute(int, int, int); /分配 void Collection(int, int, int); /收集 Node *data; int length; ; 7.5.2 基數排序 void SLList:Distribute(int front, int rear, int digit) int i, index; for (i = 0; i 0; i = L.datai.next) index = datai.key / (int)pow(10.0, digit) - datai.key / (int)pow(10.0, d

35、igit + 1) * 10; if (frontindex = 0) frontindex = i; else datarearindex.next = i; rearindex = i; 鏈式基數排序 “分配”算法 鏈式基數排序 “收集”算法 7.5.2 基數排序 void SLList:Collection(int front, int rear, int digit) int i, current; for (i = 0; fronti = 0; i+);/ 找到第一個非空子表 data0.next = fronti;/ 頭結點指向第一個非空子表中第一個結點 current = rea

36、ri+; for (; i RADIX; i+) if (fronti = 0) continue; datacurrent.next = fronti;/ 鏈接兩個非空子表 current = reari; datacurrent.next = 0; 鏈式基數排序 算法 7.5.2 基數排序 / 用SLList實現的基數排序 void SLList:RadixSort() int i; int frontRADIX,rearRADIX; / 從最低位優先依次對各關鍵字進行分配收集 for ( i = 0; i DIGITS; i+) Distribute(front, rear, i); C

37、ollection(front, rear, i); 7.5.2 基數排序 重排 鏈式基數排序產生的是一個有序循環鏈表，只能對它 進行順序訪問，無法進行隨機訪問，因此有時需要對 元素重新排列，將元素按照鏈表結點中next域的值調整 位置使其順序存儲 具體做法 順序掃描有序鏈表，將鏈表中第i個結點移動至靜態 鏈表中的第i個分量 重排例 重排算法 7.5.2 基數排序 void SLList:Arrange() int i, tmp; int current = data0.next;/ current存放第一個元素的當前位置 for (i = 1; i length; i+) while (cu

38、rrent i) / 找到第i個元素，并用current存放其在靜態 / 鏈表中當前位置 current = datacurrent.next; tmp = datacurrent.next; if (current != i) Swap(datacurrent, datai); / 第i個元素調整到位 datai.next = current; / 指向被移走的元素 current = tmp; / 為找第i + 1個元素做準備 7.5.2 基數排序 算法分析 空間復雜度 O(r + n) 時間復雜度 T(n)= O(d (n + r) 其中，n為待排序元素個數，d為元素的關鍵字分量數 ，r

39、為基數 7.6 內部排序的比較 排序方法平均情況最好情況最壞情況 基數排序O(d(n + r)O(d(n + r)O(d(n + r) 2-路歸并排序O(n log n)O(n log n)O(n log n) 堆排序O(n log n)O(n)O(n log n) 快速排序O(n log n)O(n log n)O(n2) 希爾排序O(n) 直接插入排序O(n2)O(n)O(n2) 簡單選擇排序O(n2)O(n2)O(n2) 7.6 內部排序的比較 從平均性能而言，快速排序最佳，但最壞情況下不如堆排 序和歸并排序 直接插入排序、簡單選擇排序、冒泡排序是O(n2)的排序， 不適合處理n較大的情況 從空間復雜度角度考慮 歸并排序需要與待排序列等量的輔助存儲空間，其空 間復雜度為O(n)； 基數排序次之，空間復雜度為O(r + n)； 快速排序最壞情況下需要的棧空間為O(n)，最好情況下 需要的棧空間為O(log