C++程序設(shè)計第七章排序

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

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

3、A0.i-1Ri無序序列 Ai.n-1有序序列A0.i無序序列 Ai+1.n-1直接插入排序例7.1.1 直接插入排序 直接插入排序算法/ 直接插入排序,數(shù)組data用于存放待排序元素，n為待排序元素個數(shù)templatevoid 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 & dataj - 1 tmp;j-) dataj

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

5、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 2-路插入排序 將插入?yún)^(qū)域分成大致等

6、長的兩段，選擇性地插人到其中一段 排序過程 設(shè)置一個和原數(shù)組data 同類型，同規(guī)模的是數(shù)組d，并將其視為循環(huán)數(shù)組（即位置n-1和0邏輯上相鄰） d0 = data0，將d0看作為排好序中處于中間位置的元素，從第二個元素data1開始做以下操作 如果dataid0，將datai插入d0之后的有序序列，并保持插入后有序；反之，將其插入d0之前的有序序列，并保持插入后有序2-路插入排序例7.1.3 2-路插入排序 算法評價 減少約為n2/8的元素移動次數(shù) 基準元素選取的好壞直接影響排序的效率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設(shè)增量d=516282479 22345581996446設(shè)增量d=31622245528346446997981設(shè)增量d=116222428344655647981997.1.4 希爾排序 希爾排序算法templatevoid ShellSort(ElemType data, int inc

8、rements , 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 = tmp; 7.1.4 希爾排序 特點 子序列的構(gòu)成不是簡單的“逐段分割”，而是將

9、相隔某個增量的元素組成一個子序列 希爾排序可提高排序速度，因為 分組后n值減小，n更小，而T(n)=O(n),所以T(n)從總體上看是減小了 關(guān)鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序7.1.4 希爾排序 算法評價 算法效率依賴于增量序列的選擇 時間復(fù)雜度在O(n3/2)到O(n7/6)之間 增量序列的取法 最后一個增量必須為1 其他增量間保持“互質(zhì)”7.2 分劃類排序 分劃類排序 通過一趟劃分確定一個元素在序列中的位置，保證在它之前的一組元素不比它大，之后的不比它小，接著對兩組元素繼續(xù)分劃，直至待排序列有序。 應(yīng)用插入類排序思想的算法 冒泡排序 快速排序7

10、.2.1 冒泡排序 排序過程 將第一個和第二個元素的關(guān)鍵字進行比較，若為逆序，則將兩元素互換；接著比較第二個和第三個元素的關(guān)鍵字，依次類推，直至最后兩個元素的完成比較，這稱為第一趟冒泡排序。第一趟排序分劃出一組元素個數(shù)為n-1的待排序列和一個關(guān)鍵字最大的元素。 第i趟對前n - i + 1個的元素進行類似的排序操作，得到一組元素個數(shù)為n - i的待排序列和一個關(guān)鍵字次大的元素。 這樣不斷分劃直至一趟分劃時無元素互換為止。7.2.1 冒泡排序 假設(shè)在排序過程中，元素序列A1.n的狀態(tài)為：無序序列無序序列A1.n-i+1有序序列有序序列 An-i+2.nn-i+1無序序列無序序列A1.n-i有序序

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

12、dataj,dataj + 1); lastSwapIndex = j;7.2.1 冒泡排序 算法評價 最好情況（正序） 移動次數(shù)：0 比較次數(shù)：n-1 最壞情況（逆序） 移動次數(shù)：3n(n-1)/2 比較次數(shù)：n(n-1)/2 T(n) = O(n2)7.2.2 快速排序 一趟快速排序 選第一個待排序元素作為樞軸（或支點pivot），根據(jù)樞軸將待排序列劃分為兩個子列 這兩個子列必須滿足以下條件：一個子列的元素關(guān)鍵字都不大于樞軸的關(guān)鍵字，另一個子列的元素關(guān)鍵字都不小于樞軸的關(guān)鍵字。7.2.2 快速排序 首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無無

13、 序序 的的 元元 素素 序序 列列無序記錄子序列無序記錄子序列(1)無序子序列無序子序列(2)樞軸樞軸一次劃分一次劃分分別進行快速排序分別進行快速排序7.2.2 快速排序 排序過程 對待排序列A進行快速排序的遞歸算法QuickSort(A)可以描述如下： 如果A中元素的個數(shù)為0或1，則返回；否則，繼續(xù) 選取A中的一個元素p作為樞軸（pivot） 將A中剩下的元素“劃分”成兩個不相交的集合： QuickSort (A1), p, QuickSort (A2)12 | ., | .AxApxkeyp keyAxApxkeyp key一趟快速排序例7.2.2 快速排序/ 對datalow.high

14、進行分劃，確定樞軸的位置，并返回其所在位置/ 子序列中，在樞軸之前（后）的元素均不大（?。┯谒黷emplateint Partition(ElemType data , int low , int high) ElemType pivot = datalow; / 用子序列的頭元素作為樞軸 while (low high) while (low = pivot) high-; datalow = datahigh;/ 比樞軸小的元素移到低端 while (low = datalow) low+; datahigh = datalow;/ 比樞軸大的元素移到高端 datalow = pivot;

15、/ 確定樞軸的合適位置 return low;/ 返回樞軸的位置 一趟快速排序算法7.2.2 快速排序 快速排序算法/ 對databegin.end進行快速排序templatevoid QuickSort(ElemType data, int begin, int end) if (begin = end) / data長度小于等于時返回 return; int pivot = Partition(data , begin , end); / 對databegin.end進行分劃 QuickSort(data , begin , pivot - 1); / 對低端子列進行遞歸排序 QuickS

16、ort(data , pivot + 1, end); / 對高端子列進行遞歸排序 / 快速排序templatevoid QuickSort(ElemType data, int n) if (n 2) return; QuickSort(data, 0, n-1);7.2.2 快速排序 算法分析 最好情況 每次中間值作為樞軸 T(n)=O(nlog2n) 最壞情況 每次總選最大或最小元素作為樞軸 T(n)=O(n) 平均情況 T(n)= O(nlogn) 三數(shù)中值分割法7.3 選擇類排序 選擇類排序 逐趟掃描未排序的部分，從中選取一個元素移動到合適的位置 。 應(yīng)用選擇類排序思想的算法 簡單選

17、擇排序 樹形選擇排序 堆排序7.3.1 簡單選擇排序 假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列有序序列A1.i-1無序序列無序序列 Ai.n第第 i 趟簡單選擇排序趟簡單選擇排序從中選出關(guān)鍵字最小的從中選出關(guān)鍵字最小的元素元素有序序列有序序列A1.i無序序列無序序列 Ai+1.n7.3.1 簡單選擇排序 排序過程 第一趟掃描所有待排序元素，找出關(guān)鍵字最小的元素并將它與第一個元素進行交換； 第i趟，掃描待排序列中剩余n - i + 1個元素，找出關(guān)鍵字最小的元素與序列中第i個位置上的元素交換 重復(fù)上述操作,直到所有的元素都放到正確的位置上為止簡單選擇排序例 簡單選擇排序算法7.3.1 簡單

18、選擇排序templatevoid 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); / 將datai與第i小的元素交換 7.3.1 簡單選擇排序 算法分析 最好情況 比較次數(shù)： 移動次數(shù)：0 最壞情況 比較次數(shù)： 移動次數(shù)： 3(n - 1) T(n)=O(n)1211()()2nininn1

19、211()()2nininn7.3.2 樹形選擇排序 簡單選擇排序中一趟排序中的比較操作可能在前一趟中已經(jīng)做過，但前一趟中未保存這些比較結(jié)果，因此在后一趟的排序中又重復(fù)執(zhí)行了這些操作。為了解決這個問題，樹形選擇排序應(yīng)運而生。 算法思想 先將n個元素的關(guān)鍵字兩兩比較，然后將其中 個較小者兩兩比較，如此重復(fù)，不斷的淘汰較大者，最終選出關(guān)鍵字最小的元素樹形選擇排序例7.3.3 堆排序 堆的定義：堆是滿足下列性質(zhì)的數(shù)列a1, a2, ，an：或或221iiiiaaaa221iiiiaaaa(小頂堆)(大頂堆)12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 小頂堆1

20、2, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 不是堆7.3.3 堆排序 若將該數(shù)列視作完全二叉樹，則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子aia2i a2i+1 1236276549817355403498不是堆不是堆147.3.3 堆排序 堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。建大頂堆98, 53, 55, 18, 4, 22, 2424, 53, 55, 18, 4, 22, 98交換 98 和 24重新調(diào)整為大頂堆55, 53, 24, 18, 4, 22, 98 22, 18, 53, 98, 4, 24,

21、 55經(jīng)過篩選7.3.3 堆排序 排序過程 將待排序列A0n-1調(diào)整為大頂堆； 將堆頂元素A0（即關(guān)鍵字最大的元素）與堆尾元素（即堆中最后一個元素）交換，從堆中除去堆尾元素(即關(guān)鍵字最大的元素)，同時調(diào)整堆中剩余元素，使它們恢復(fù)堆屬性； 反復(fù)進行步驟2，直至堆中元素個數(shù)為1。7.3.3 堆排序 堆排序需解決的兩個問題： 如何將初始的待排序列調(diào)整為一個堆？ 因堆頂元素與堆尾元素交換后，新的堆頂元素可能破壞了堆屬性，如何再調(diào)整成為堆？ 第二個問題解決方法 輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中較大者進行交換；重復(fù)上述操作，直至葉子結(jié)點，將

22、得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”例例堆排序調(diào)整例堆排序調(diào)整例7.3.3 堆排序 第一個問題解決方法 從最后一個非葉子結(jié)點（即第 個元素）開始對所有非葉子結(jié)點調(diào)整操作建堆例 含7個元素的無序序列（22, 18, 53, 98, 4, 24, 55）2218552449822551853244982255985324418985522532441853 調(diào)整堆算法7.3.3堆排序/ 將datai.n-1中的元素調(diào)整為大頂堆templatevoid HeapAdjust(ElemType data, int i, int n) ElemType tmp; int child; fo

23、r ( tmp = datai; LeftChild(i) datachild) / 取較大的孩子結(jié)點 child+; if (tmp datachild) datai = datachild; else break; datai = tmp;7.3.3 堆排序 堆排序算法/ 堆排序templatevoid HeapSort(ElemType data, int n) int i; for (i = n/2; i = 0; i-)/ 建堆 HeapAdjust(data, i, n); / 將堆的根結(jié)點與最后的一個葉結(jié)點交換,并進行調(diào)整 for (i = n - 1;i 0; i-) Swap

24、(data0,datai); HeapAdjust(data, 0, i); 7.3.3 堆排序 算法評價 最好情況：O(n) 最壞情況：O(nlogn) 平均： O(nlogn)7.4 歸并類排序 歸并 將兩個有序列合并成為一個新的有序列 2-路歸并排序 將相鄰的元素兩兩歸并，得到 個長度為2或1的有序子序列，再將這些子序列兩兩歸并，如此重復(fù)，直至得到一個長度為n的有序列為止2-路歸并排序例“歸并”算法/ 將數(shù)組data中，lptr.rptr-1rptr.rightEnd兩部分的元素進行合并/ tmpArr為合并時的輔存空間templatevoid Merge(ElemType data,

25、ElemType tmpArr, int lptr , int rptr, int rightEnd) int leftEnd = rptr - 1; int ptr,i; ptr = i = lptr; while (lptr = leftEnd & rptr = rightEnd) if (datalptr = datarptr) tmpArrptr+ = datalptr+; else tmpArrptr+ = datarptr+; while (lptr = leftEnd) tmpArrptr+ = datalptr+; while (rptr = rightEnd) tmp

26、Arrptr+ = datarptr+; for (;i = rightEnd; i+) datai = tmpArri;2-路歸并排序算法templatevoid MPass(ElemType data, ElemType tmpArr, int n, int mergeLength) int i = 0; while (i = n - 2 * mergeLength) Merge(data, tmpArr, i, i+mergeLength, i+2*mergeLength-1); i = i + 2 * mergeLength; if (i + mergeLength n) Merge(

27、data, tmpArr, i, i + mergeLength, n - 1);/ 2-路歸并算法非遞歸實現(xiàn)templatevoid MergeSortNonRecursion(ElemType data, int n) int mergeLength = 1; / mergeLength記錄每趟歸并的步長 ElemType* pArr = NULL; pArr = new ElemTypen;/ pArr為合并時的輔存空間 while (mergeLength n) MPass(data, pArr, n, mergeLength); mergeLength *= 2; delete pA

28、rr;7.4 歸并類排序 算法評價 T(n)= O(nlogn) 缺點 空間復(fù)雜度為O(n) 算法中需要較多的拷貝工作7.5 基數(shù)排序 無須比較關(guān)鍵字 通過“分組”和“收集”兩個過程來完成排序任務(wù) 借助“多關(guān)鍵字排序”的思想7.5.1 多關(guān)鍵字的排序 假設(shè)待排序列 a1, a2, an中每個元素ai有d個關(guān)鍵字 ，該序列對關(guān)鍵字 有序是指： 對序列中任意兩個元素ai和aj(1 i j n)都滿足下列有序關(guān)系： 當(dāng)兩個元素的所有關(guān)鍵字都相等時，則必須保持其穩(wěn)定性。其中 稱為最主位關(guān)鍵字， 稱為最次位關(guān)鍵字。12(,.,)diiik kk1212(,.,)(,.,)ddiiijjjk kkk kk

29、1kdk7.5.1 多關(guān)鍵字的排序 排序方法 最高位優(yōu)先法（MSD） 先對最高位關(guān)鍵字k1排序，將序列分成若干子序列，每個子序列有相同的k1值 接著讓每個子序列對次關(guān)鍵字k2排序，又分成若干更小的子序列 依次重復(fù)，直至就每個子序列對最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列 最低位優(yōu)先法（LSD） 從最低位關(guān)鍵字kd起進行排序，然后再對高一位的關(guān)鍵字排序，依次重復(fù)，直至對最高位關(guān)鍵字k1排序后，便成為一個有序序列7.5.1 多關(guān)鍵字的排序 MSD與LSD不同特點 按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序 按LSD排序，不必分成子序列，對每個

30、關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實現(xiàn)排序7.5.2 基數(shù)排序 基數(shù)排序依次根據(jù)各關(guān)鍵字分量進行“分配”、“收集”完成排序 在單關(guān)鍵字排序中，一個關(guān)鍵字可以看作由若干個關(guān)鍵字分量復(fù)合而成，如整數(shù)可視為若干數(shù)位的集合?；鶖?shù)排序例7.5.2 基數(shù)排序 用數(shù)組實現(xiàn)的基數(shù)排序算法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 digi

31、ts;i+,factor *= radix) for ( j = 0;j n; j+) queues(dataj/factor)%radix.push(dataj); / 分配 for ( k = j = 0; j radix; j+,k+) / 收集 while (!queuesj.empty() datak = queuesj.front(); queuesj.pop(); 7.5.2 基數(shù)排序 用數(shù)組實現(xiàn)基數(shù)排序的缺點 雖然不需要進行“比較”操作，但仍需要大量的元素移動操作 還需要額外的空間來存放10個隊列 鏈式基數(shù)排序 用鏈表作存儲結(jié)構(gòu)的基數(shù)排序7.5.2 基數(shù)排序 鏈式基數(shù)排 設(shè)置1

32、0個隊列，fronti和reari分別為第i個隊列的頭指針和尾指針 第一趟分配對最低位關(guān)鍵字（個位）進行，改變元素的指針值，將鏈表中的元素分配至10個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同 第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表 重復(fù)上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列鏈式基數(shù)排序（第一趟）例靜態(tài)鏈表class SLList struct Node int keyDIGITS; int info; int next;friend ostream& operator(o

33、stream& os, SLList &s);public: SLList():data(NULL),length(0); SLList(); void Arrange(); /重排 void Init(int arr,int n); void RadixSort(); /鏈式基數(shù)排序private: void Distribute(int, int, int); /分配 void Collection(int, int, int); /收集 Node *data; int length;7.5.2 基數(shù)排序void SLList:Distribute(int front, i

34、nt 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, digit + 1) * 10; if (frontindex = 0) frontindex = i; else datarearindex.next = i; rearindex = i; 鏈式基數(shù)排序 “分配”算法 鏈式基數(shù)排序 “收集”算法7.5.2 基數(shù)排序void SLList:Collection(int

35、 front, int rear, int digit) int i, current; for (i = 0; fronti = 0; i+);/ 找到第一個非空子表 data0.next = fronti;/ 頭結(jié)點指向第一個非空子表中第一個結(jié)點 current = reari+; for (; i RADIX; i+) if (fronti = 0) continue; datacurrent.next = fronti;/ 鏈接兩個非空子表 current = reari; datacurrent.next = 0; 鏈式基數(shù)排序 算法7.5.2 基數(shù)排序/ 用SLList實現(xiàn)的基數(shù)排

36、序void SLList:RadixSort() int i; int frontRADIX,rearRADIX; / 從最低位優(yōu)先依次對各關(guān)鍵字進行分配收集 for ( i = 0; i DIGITS; i+) Distribute(front, rear, i); Collection(front, rear, i); 7.5.2 基數(shù)排序 重排 鏈式基數(shù)排序產(chǎn)生的是一個有序循環(huán)鏈表，只能對它進行順序訪問，無法進行隨機訪問，因此有時需要對元素重新排列，將元素按照鏈表結(jié)點中next域的值調(diào)整位置使其順序存儲 具體做法 順序掃描有序鏈表，將鏈表中第i個結(jié)點移動至靜態(tài)鏈表中的第i個分量重排例 重

37、排算法7.5.2 基數(shù)排序void SLList:Arrange() int i, tmp; int current = data0.next;/ current存放第一個元素的當(dāng)前位置 for (i = 1; i length; i+) while (current i) / 找到第i個元素，并用current存放其在靜態(tài)/ 鏈表中當(dāng)前位置 current = datacurrent.next; tmp = datacurrent.next; if (current != i) Swap(datacurrent, datai); / 第i個元素調(diào)整到位 datai.next = curren

38、t; / 指向被移走的元素 current = tmp; / 為找第i + 1個元素做準備 7.5.2 基數(shù)排序 算法分析 空間復(fù)雜度O(r + n) 時間復(fù)雜度T(n)= O(d (n + r)其中，n為待排序元素個數(shù)，d為元素的關(guān)鍵字分量數(shù)，r為基數(shù)7.6 內(nèi)部排序的比較排序方法平均情況最好情況最壞情況基數(shù)排序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 內(nèi)部排序的比較 從平均性能而言，快速排序最佳，但最壞情況下不如堆排序和歸并排序 直接插入排序、簡單選擇排序、冒泡排序是O(n2)的排序，不適合處理n較大的情況 從空間復(fù)雜度角度考慮 歸并排序需要與待排序列等量的輔助存儲空間，其空間復(fù)雜度為O(n)； 基數(shù)排序次之，空間復(fù)雜度為O(r + n)； 快速排序最壞情況下需要的棧空間為O(n)