《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第8章 排序C語(yǔ)言描述（第2版）張乃孝編著

8.1 基本概念8.2 插入排序8.3 選擇排序8.4 交換排序8.5 分配排序8.6 歸并排序（1）排序的確切定義： 假設(shè)R0, R1, , Rn-1是由n個(gè)記錄組成的文件， K0, K1, , Kn-1是排序碼集合，所謂排序是將記錄 按排序碼不增（或不減）的次序排列。 排序碼可以是主關(guān)鍵碼，也可以是次關(guān)鍵碼。 （2）穩(wěn)定排序和不穩(wěn)定排序 假設(shè)Ki=Kj(0=i,j=n-1,ij)，且在排序前的序列 中Ri領(lǐng)先于Rj(即ij)，若在排序后的序列中Ri仍領(lǐng) 先于Rj，則稱所用的排序方法是穩(wěn)定的，否則是不 穩(wěn)定的。 （3）排序中的基本操作： 比較關(guān)鍵碼大小 移動(dòng)記錄（4）待排序的記錄在排序過程中全部存放在內(nèi)存的稱為內(nèi)排序，如果排序過程中需要使用外存的稱為外排序。本章討論的都是內(nèi)排序的方法，但有些方法(特別是歸并排序的思想)也可以用于外排序。排序方法：一、插入排序二、選擇排序三、交換排序四、分配排序五、歸并排序六、外部排序* 評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條第一是執(zhí)行算法所需的時(shí)間；第二是執(zhí)行算法所需要的附加空間；另外算法本身的復(fù)雜程度也是考慮的一個(gè)因素。由于排序是經(jīng)常使用的一種運(yùn)算，因此，排序的時(shí)間開銷是算法好壞的最重要的標(biāo)志。而排序的時(shí)間開銷又可以用算法執(zhí)行中的比較和移動(dòng)次數(shù)來(lái)衡量。 8.2.1 8.2.1 直接插入排序直接插入排序 8.2.2 8.2.2 二分法插入排序二分法插入排序 8.2.3 8.2.3 表插入排序表插入排序 8.2.4 8.2.4 ShellShell排序排序8.2.1 8.2.1 直接插入排序直接插入排序 初始： 49 38 65 97 76 13 27 49 i=1: 38 49 65 97 76 13 27 49 i=2: 38 49 65 97 76 13 27 49 i=3: 38 49 65 97 76 13 27 49 i=4: 38 49 65 76 97 13 27 49 i=5: 13 38 49 65 76 97 27 49 i=6: 13 27 38 49 65 76 97 49 i=7: 13 27 38 49 49 65 76 97 穩(wěn)定排序 typedef int KeyTypetypedef int KeyType; ;typedef int DataTypetypedef int DataType; ;typedef atructtypedef atruct KeyType KeyType key; key; DataType DataType info; info;RecordNodeRecordNode; ;typedef structtypedef struct int int n; n; RecordNode RecordNode * *record;record;SortObjectSortObject; ;算法算法8.1 直接插入排序直接插入排序void insertSort(SortObject * pvector)/ 按增序進(jìn)行直接插入排序按增序進(jìn)行直接插入排序 int i, j; RecordNode temp; for( i = 1; i n; i+ ) /* 依次插入記錄依次插入記錄R1, R2Rn-1 */ temp = pvector-recordi; j = i-1; while (temp.key recordj.key)&(j=0) ) /* 由后向前找插入位置由后向前找插入位置 */ pvector-recordj+1 = pvector-recordj; /* 將排序碼大于將排序碼大于ki的記錄后移的記錄后移 */ j-; if( j!=(i-1) ) pvector-recordj+1 = temp; 算法分析： 空間效率：只需要一個(gè)記錄的輔助空間。 時(shí)間效率：比較記錄的次數(shù): 最小: n-1次;最大: n(n-1)/2次移動(dòng)記錄的次數(shù): 最小: n-1 最大: (n+4)(n-1)/2 i-1 i-1 pjcj =(1/i)(j+1) =(i+1)/2 j=0 j=0 n-1 (i+1)/2 = O(n2) i=1平均情況：比較O(n2)，移動(dòng)O(n2) 由于插入排序的基本操作是在有序表中進(jìn)行查找,而查找的過程是可以用折半查找來(lái)實(shí)現(xiàn)的。由此實(shí)現(xiàn)的排序稱為二分法插入排序。8.2.2 8.2.2 二分法插入排序二分法插入排序 二分法插入排序必須采用順序存儲(chǔ)方式。 二分法插入排序的比較次數(shù)與待排序記錄的初始狀態(tài)無(wú)關(guān)，僅依賴于記錄的個(gè)數(shù) 二分法插入排序(1) 1327384965769749 left=0 mid=3right=6(2) 1327384965769749left=4 mid=5 right=6(3) 1327384965769749left=4 mid=4 right=4 49right 已找到插入位置left=4(4) 1327384949657697圖8.2 二分法插入排序示例 算法分析： 空間效率：同直接插入排序 時(shí)間效率：僅減少了比較次數(shù)，移動(dòng)記錄次數(shù)不變。 n log2i nlog2n i=1最壞的情況為n2/2，最好的情況為2n，平均移動(dòng)次數(shù)為O(n2) 4938659776132749 prenow3849659776132749 prenow3849659776132749 prenow3849659776132749 prenow類型聲明如下：struct Node;typedef struct Node ListNode;struct Node KeyType key; DataType info; ListNode *next; ;typedef ListNode * LinkList;算法 8.3 表插入排序算法分析： 空間效率：每個(gè)記錄中增加了一個(gè)next字段，所以，輔助空間為S(n)=O(n)。 時(shí)間效率： 用鏈表方式減少記錄移動(dòng)的次數(shù)，時(shí)間復(fù)雜度仍為O(n2)。算法由條件p.key=now.key保證表插入排序是穩(wěn)定的。 shell排序又稱縮小增量排序(Diminishing Increment Sort)。 先將整個(gè)待排記錄序列分割成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序“時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序，就可以完成整個(gè)的排序工作。 shell排序的一個(gè)特點(diǎn)是：子序列的構(gòu)成不是簡(jiǎn)單“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列。 8.2.4 shell.2.4 shell排序排序非形式算法如下所示： increment=d; /* d0) 相距 increment的記錄為一組 對(duì)每組進(jìn)行插入排序； increment=increment/2; ;Shell排序的平均比較次數(shù)和平均移動(dòng)次數(shù)都為O(n1.3)左右。Shell排序算法中增加了一個(gè)輔助空間temp，因此算法的輔助空間為S(n)=O(1)。Shell排序是不穩(wěn)定的。 算法 8.4 shell 排序例題 待排序序列為49,38,65,97,13,76,27,49，請(qǐng)用 Shell排序法排序。 原始序列 49 38 65 97 13 76 27 491. d=4 2. d=2 13 38 27 49 49 76 65 97 3. d=1 13 38 27 49 49 76 65 97 排序結(jié)果 13 27 38 49 49 65 76 97 基本思想是：每一趟在n-i+1個(gè)記錄中選取關(guān)鍵碼最小的記錄作為有序序列中第i個(gè)記錄。 8.3.1 8.3.1 直接選擇排序直接選擇排序 8.3.2 8.3.2 堆排序堆排序直接選擇排序的時(shí)間復(fù)雜度： 移動(dòng)：最好時(shí)：0最壞時(shí)：3（n-1) 比較：n(n-1)/2 總的時(shí)間復(fù)雜度：O(n2)穩(wěn)定性：不穩(wěn)定 首先在所有記錄中選出排序碼最小的記錄，與第一個(gè)記錄交換，然后在其余的記錄中再選出排序碼最小的記錄與第二個(gè)記錄交換，以此類推，直到所有記錄排好序。 直接選擇排序的比較次數(shù)與文件初始狀態(tài)無(wú)關(guān)。 8.3.1 直接選擇排序直接選擇排序49 38 65 97 49 13 27 76 13 38 65 97 49 49 27 76 13 27 65 97 49 49 38 76 13 27 38 97 49 49 65 7613 27 38 49 97 49 65 7613 27 38 49 49 97 65 7613 27 38 49 49 65 97 7613 27 38 49 49 65 76 9713 27 38 49 49 65 76 97 算法8.5 直接選擇排序void selectSort(SortObject * pvector)/ 按遞增序進(jìn)行選擇排序 int i, j, k; RecordNode temp; for( i = 0; i n-1; i+ )/* 做n-1趟選擇排序 */ k=i; for(j=i+1; jn; j+) /* 在無(wú)序區(qū)內(nèi)找出排序碼最小的記錄Rk*/ if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) /* 記錄Rk與Ri互換 */ temp=pvector-recordi; pvector-record i= pvector-record k; pvector-record k=temp; 選擇排序選擇排序的主要操作是比較比較，要提高它的速度必須減少比較的次數(shù)。而實(shí)際上如果能利用以前的比較結(jié)果則可以提高排序速度。 樹形選擇排序樹形選擇排序(Tree Selection Sort)，又稱錦標(biāo)錦標(biāo)賽排序賽排序(Tournament Sort)。其方法是：首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在n/2個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)直到選出最小關(guān)鍵字的記錄為止。然后對(duì)剩下的記錄作同樣的操作，選出具有次小關(guān)鍵字的記錄。這個(gè)過程可以用一個(gè)完全二叉樹來(lái)表示。如下圖。8.3.2 8.3.2 堆排序堆排序(Heap Sort)(Heap Sort)133813386513274938659776132788樹形選擇排序示例樹形選擇排序示例 該方法的時(shí)間復(fù)雜度為O(nlog2n)。缺點(diǎn)是使用了較多的輔助空間，并且和“最大值”進(jìn)行了多余的比較。1964年Willioms提出了堆排序堆排序。 堆的定義：n個(gè)元素的序列k1,k2,kn當(dāng)且僅當(dāng)滿足如下關(guān)系時(shí)，稱之為堆。 ki k2iki k2i ki k2i+1 ki k2i+1( i = 1, 2, , n/2 ) 或 若將和此序列對(duì)應(yīng)的一維數(shù)組看成是一個(gè)完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點(diǎn)的值均不大于（或不小于）其左右孩子結(jié)點(diǎn)的值。由此，若序列 k1,k2,kn 是堆，則堆頂元素必為序列中n個(gè)元素的最小值（或最大值）。如果在輸出堆頂?shù)淖钚≈岛螅沟檬Ｓ鄋-1個(gè)元素的序列重又建成一個(gè)堆，則得到次小值。反復(fù)執(zhí)行便能得到所有記錄的有序序列，這個(gè)過程稱為堆排序。 現(xiàn)在剩下兩個(gè)問題： （1）如何由一個(gè)無(wú)序序列建成一個(gè)堆； （2）如何在輸出堆頂元素后，調(diào)整剩余元素為 一個(gè)新的堆。 在輸出堆頂元素后，用堆中最后一個(gè)元素替代，此時(shí)根結(jié)點(diǎn)的左右子樹均為堆，則僅需自上而下進(jìn)行調(diào)整即可。首先堆頂元素和其左右孩子的值比較，把最小的值（假設(shè)為左孩子結(jié)點(diǎn)）調(diào)到根結(jié)點(diǎn)的位置，由于左子樹的根結(jié)點(diǎn)發(fā)生了改變，因此需要對(duì)左子樹進(jìn)行上述一樣的調(diào)整，直至葉子結(jié)點(diǎn)。這個(gè)自堆頂至葉子的調(diào)整過程稱為篩選。 從一個(gè)無(wú)序序列建堆的過程就是一個(gè)反復(fù)篩選的過程。若將此無(wú)序序列看成是一個(gè)完全二叉樹，則最后一個(gè)非終端結(jié)點(diǎn)就是第n/2 個(gè)元素，因此篩選只需從第n/2 個(gè)元素起，篩選到第1個(gè)元素（即堆頂元素）。如下頁(yè)圖。例：初始序列為 26，5，77，1，61，11，59，15，48，1926057701611159154819（1）初始完全二叉樹26057701611159154819(2)調(diào)整序號(hào)為4的結(jié)點(diǎn) 26057748611159150119(3)調(diào)整序號(hào)為3的結(jié)點(diǎn) 26057748611159150119(4)調(diào)整序號(hào)為2的結(jié)點(diǎn) 26617748191159150105(5)調(diào)整序號(hào)為1的結(jié)點(diǎn) 77615948191126150105(6)調(diào)整序號(hào)為0的結(jié)點(diǎn) 05615948191126150177(7)結(jié)點(diǎn)77與結(jié)點(diǎn)5互換615915191126050177(8)重建堆48(9)結(jié)點(diǎn)61與結(jié)點(diǎn)1互換592615191101056177(10)重建堆4801591519112605617748(11)結(jié)點(diǎn)59與結(jié)點(diǎn)05互換052615191101596177(12)重建堆4848261505110159617719(12)結(jié)點(diǎn)48與結(jié)點(diǎn)1互換(13)重建堆0126150511485961771926111505014859617719(15)結(jié)點(diǎn)26與結(jié)點(diǎn)1互換(16)重建堆0111150526485961771919110105264859617715(17)結(jié)點(diǎn)19與結(jié)點(diǎn)5互換(18)重建堆0511011926485961771515110119264859617705(19)結(jié)點(diǎn)15與結(jié)點(diǎn)1互換(20)重建堆0111151926485961770511011519264859617705 堆排序適用于n值較大的情況。其比較次數(shù)為： 2n(log2n)。在最壞的情況下，時(shí)間復(fù)雜度也是O(nlogn)。且僅需一個(gè)記錄大小的輔助空間。 兩兩比較待排序記錄的排序碼，交換不滿足順序要求的偶對(duì)，直到全部為止。 8.4.1 8.4.1 起泡排序起泡排序 8.4.2 8.4.2 快速排序快速排序 設(shè)待排序記錄順序存放在R0,R1,R2,Rn-1中，依次比較（R0,R1），（ R1,R2）, (Rn-2,Rn-1),不滿足順序則交換，結(jié)果，最大者在Rn-1中。這叫一次起泡。此后，再對(duì)存放在R0,R1,R2,Rn-2中n-1個(gè)記錄作同樣處理,結(jié)果，最大者在Rn-2中。 。 n-1次起泡能完成排序。設(shè)置標(biāo)志noswap表示本次起泡是否有交換，若無(wú)交換，表示排序完成。8.4.1 8.4.1 起泡排序起泡排序38 49 65 76 13 27 49 97 49 38 65 97 76 13 27 49 38 49 65 13 27 49 76 97 38 49 13 27 49 65 76 97 38 13 27 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 初始 1 2 3 4 5 6 算法8.7 起泡排序算法void bubbleSort(SortObject * pvector) int i, j, noswap; RecordNode temp; for(i=0; in-1; i+)/* 做n-1次起泡 */ noswap=TRUE; for(j=0; jn-i-1; j+) /* 置交換標(biāo)志 */ if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; /* 交換記錄 */ pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; noswap=FALSE; if(noswap) break; /本趟起泡未發(fā)生記錄交換，算法結(jié)束 起泡排序的最壞時(shí)間復(fù)雜度為O(n2)，平均 時(shí)間復(fù)雜度為O(n2)。 起泡排序算法中增加一個(gè)輔助空間temp，輔助空間為S(n)=O(1)。 起泡排序是穩(wěn)定的。 快速排序是對(duì)冒泡排序的改進(jìn)，其基本思想是：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。 首先任意選取一個(gè)記錄作為樞軸（或支點(diǎn)）(Pivot)，然后按下述原則重新排列其一記錄：將所有關(guān)鍵字小于它的記錄都安置在它之前，將所有關(guān)鍵字大于它的記錄安置在它之后。于是以該樞軸記錄所在的位置i作分界線，將整個(gè)序列分成兩個(gè)子序列。這個(gè)過程稱為一趟快速排序。然后分別對(duì)于兩個(gè)子序列作同樣的操作，重復(fù)這個(gè)過程，直到子序列不可再分就完成了記錄的排序工作。一趟快速排序的具體做法是：附設(shè)兩個(gè)指針low和high,它們的初值分別是一個(gè)序列的第一個(gè)和最后一個(gè)記錄的位置，設(shè)樞軸記錄的關(guān)鍵字為pivotKey，在首先從high所指位置起向前搜索直到第一個(gè)關(guān)鍵字小于pivotKey的記錄和樞軸記錄交換，然后從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotKey的記錄和樞軸記錄互相交換，重復(fù)交替這兩步直到low=high為止。算法算法8.8 8.8 快速排序算法快速排序算法491386597761327492樞軸一般取第樞軸一般取第一個(gè)記錄，并把一個(gè)記錄，并把樞軸關(guān)鍵字放入樞軸關(guān)鍵字放入臨時(shí)變量中，空臨時(shí)變量中，空置樞軸所在位置置樞軸所在位置從高端找一個(gè)比從高端找一個(gè)比樞軸關(guān)鍵字小的樞軸關(guān)鍵字小的記錄放入當(dāng)前空記錄放入當(dāng)前空的低端位置的低端位置從低端找一個(gè)比樞軸關(guān)鍵字大的從低端找一個(gè)比樞軸關(guān)鍵字大的記錄放入當(dāng)前空的高端位置記錄放入當(dāng)前空的高端位置樞軸樞軸lowhigh臨時(shí)變量：臨時(shí)變量： pivotkey=491Low與與high標(biāo)識(shí)標(biāo)識(shí)記錄調(diào)整的低記錄調(diào)整的低端與高端位置端與高端位置highlow65high1397491Low =high樞軸應(yīng)樞軸應(yīng)到達(dá)的最終位置到達(dá)的最終位置27high交替進(jìn)行上述兩步交替進(jìn)行上述兩步記錄重新排列的記錄重新排列的策略：從表的兩策略：從表的兩側(cè)向中間夾側(cè)向中間夾lowhigh49 38 65 97 76 13 27 4927 38 13 49 76 97 65 4913 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 各趟排序結(jié)果算法算法8.8 快速排序算法快速排序算法void quickSort(SortObject * pvector, int l, int r) int i, j; RecordNode temp; if(l=r) return; /* 只有一個(gè)記錄或無(wú)記錄，則無(wú)須排序只有一個(gè)記錄或無(wú)記錄，則無(wú)須排序 */ i=l; j=r; temp=pvector-recordi; while(i!=j)/* 尋找尋找Rl的最終位置的最終位置 */ while( (pvector-recordj.key=temp.key) & (ji) ) j - -; /從右向左掃描，查找第從右向左掃描，查找第1個(gè)排序碼小于個(gè)排序碼小于temp.key的記錄的記錄 if(irecordi+= pvector-record j; while( (pvector-recordi.keyi) ) i+; /從左向右掃描，查找第從左向右掃描，查找第1個(gè)排序碼大于個(gè)排序碼大于temp.key的記錄的記錄 if(irecordj-= pvector-recordi; pvector-recordi=temp;/* 找到找到Rl的最終位置的最終位置 */ quickSort(pvector,l,i-1); /* 遞歸處理左區(qū)間遞歸處理左區(qū)間 */ quickSort(pvector,i+1,r);/* 遞歸處理右區(qū)間遞歸處理右區(qū)間 */算法分析： 快速排序的記錄移動(dòng)次數(shù)不大于比較次數(shù)，所以，快速排序的最壞時(shí)間復(fù)雜度應(yīng)為O(n2)，最好時(shí)間復(fù)雜度為O(nlog2n)。為了改善最壞情況下的時(shí)間性能，可采用“三者取中”的規(guī)則，即在每一趟劃分前，首先比較Rl.key、Rr.key和R.key的大小，取中間的記錄與Rl交換?？焖倥判虻钠骄鶗r(shí)間復(fù)雜度是T(n)=O(nlog2n)。 算法需要一個(gè)棧空間實(shí)現(xiàn)遞歸。棧的大小取決于遞歸調(diào)用的深度，最多不超過n，若每次都選較大的部分進(jìn)棧，處理較短的部分，則遞歸深度最多不超過log2n，所以快速排序的輔助空間為S(n)=O(log2n)。 快速排序是不穩(wěn)定的。 分配排序的思想是把排序碼分解成若干部分，然后通過對(duì)各個(gè)部分排序碼的分別排序，最終達(dá)到整個(gè)排序碼的排序。 8.5.1 8.5.1 概述概述 8.5.2 8.5.2 基數(shù)排序基數(shù)排序 多關(guān)鍵字的排序l假定撲克牌的次序?yàn)? 23A23A 23A23Al要將撲克牌排成上面的次序，通常采用的方法是先按花色分成4堆，并按花色的次序?qū)?堆排好，然后分別對(duì)每一堆按面值從小到大整理有序。這種方法稱為最高位優(yōu)先法MSD（most significant digit first）8.5.1 8.5.1 概述概述l也可以先按面值分成13堆，并按面值大小將13堆排好，然后再將這13堆按花色分成4堆，4堆牌按花色從小到大合在一起，同樣完成排序。這種方法稱為最低位優(yōu)先法LSD（lease significant digit first）。 一般情況下，假設(shè)文件F有n個(gè)記錄F=(R0，R1，Rn-1) 且每個(gè)記錄Ri的排序碼中含有d個(gè)部分(ki0, ki1, kid-1)，則文件F對(duì)排序碼(k0,k1,kd-1)有序是指 文件中任意兩個(gè)記錄Ri和Rj(0ijn-1)滿足詞典次序有序關(guān)系(ki0, ki1, kid-1) (kj0, kj1, kjd-1) 其中k0稱為最高位排序碼，kd-1稱為最低位排序碼。實(shí)現(xiàn)分配排序，有兩種方法 第一種是先對(duì)最高位排序碼k0排序，稱為高位優(yōu)先法。第二種是先對(duì)最低位排序碼kd-1排序，稱為低位優(yōu)先法。 低位優(yōu)先法比高位優(yōu)先法簡(jiǎn)單，高位優(yōu)先排序必須將文件逐層分割成若干子文件，然后各子文件獨(dú)立排序；低位優(yōu)先排序不必分成子堆，對(duì)每個(gè)排序碼都是整個(gè)文件參加排序，且可通過若干次“分配”和“收集”實(shí)現(xiàn)排序。但對(duì)Ki(0 = i = d-2)進(jìn)行排序時(shí)，只能用穩(wěn)定的排序方法。 下面將介紹的基數(shù)排序就是用排序碼低位優(yōu)先法的思想對(duì)排序碼進(jìn)行分解后排序的一種方法。 采用基數(shù)排序首先把每個(gè)排序碼看成是一個(gè)d元組Ki=(Ki0, Ki1, Kid-1) 其中每個(gè)Ki都是集合C0，C1，Cr-1 (C0C1Cr-1)中的值，即C0KijCr-1(0in-1, 0jd-1)，其中r稱為基數(shù)基數(shù)。排序時(shí)先按Kid-1從小到大將記錄分配到r個(gè)堆中，然后依次收集，再按Kid-2分配到r個(gè)堆中，如此反復(fù)，直到對(duì)Ki0分配、收集，得到的便是排好序的序列。 8.5.2 8.5.2 基數(shù)排序基數(shù)排序109278063930589184505269008083e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9930063083184505008278109589269063930083184505278008109589269e0 e1 e2 e3 e4 e5 e6 e7 e8 e9505008109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f9008505109930063269278083184259e0 e1 e2 e3 e4 e5 e6 e7 e8 e9008063083109184269278505589930f0 f1 f2 f3 f4 f5 f6 f7 f8 f9063008083109184269278505589930時(shí)間復(fù)雜度O(d*n)其中d為關(guān)鍵字的位數(shù)，n為關(guān)鍵字的個(gè)數(shù)。穩(wěn)定的排序方法。l基數(shù)排序算法中，時(shí)間耗費(fèi)主要在修改指針上。一趟排序的時(shí)間為O(r+n)?？偣惨M(jìn)行d趟排序，基數(shù)排序的時(shí)間復(fù)雜度是T(n)=O(d*(r+n)。當(dāng)n較大、d較小，特別是記錄的信息量較大時(shí)，基數(shù)排序非常有效。l基數(shù)排序中，每個(gè)記錄中增加了一個(gè)next字段，還增加了一個(gè)queue數(shù)組，故輔助空間為S(n)=O(n+r)。l基數(shù)排序是穩(wěn)定的。算法分析：算法算法8.9 8.9 基數(shù)排序算法基數(shù)排序算法 歸并的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)有序表。利用歸并的思想就可以實(shí)現(xiàn)排序。假設(shè)初始的序列含有n個(gè)記錄，可以看成n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，如此重復(fù)直到得到一個(gè)長(zhǎng)度為n的有序序列為止。這種排序方法稱為二路歸并排序。例題初始序列為25, 57, 48, 37, 12, 82, 75, 29, 16，請(qǐng)用二路歸并排序法排序。初始排序碼25 57 48 37 12 82 75 29 16 / / / /第一趟歸并后25 57 37 48 12 82 29 75 16 / /第二趟歸并后25 37 48 57 12 29 75 82 16 /第三趟歸并后12 25 29 37 48 57 75 82 16 /第四趟歸并后12 16 25 29 37 48 57 75 82排序后的結(jié)果為 12, 16, 25, 29, 37, 48, 57, 75, 82算法分析: 時(shí)間復(fù)雜度: O(nlog2n) 空間復(fù)雜度: 和待排記錄等量的空間. 二路歸并算法是穩(wěn)定的. 一般情況下很少用于內(nèi)部排序.算法算法8.10 8.10 兩組歸并算法兩組歸并算法算法算法8.11 8.11 一趟歸并算法一趟歸并算法算法算法8.12 8.12 二路歸并算法二路歸并算法算法算法7.11 7.11 兩組歸并算法兩組歸并算法void merge(RecordNode r,RecordNode r1,int low,int m,int high)void merge(RecordNode r,RecordNode r1,int low,int m,int high) / /* *rlowrlow到到rmrm和和rm+1rm+1到到rhightrhight是兩個(gè)有序文件是兩個(gè)有序文件 * */ / int i,j,k; int i,j,k; i=low; j=m+1; k=low; i=low; j=m+1; k=low; while( (i=m) & (j=high) ) while( (i=m) & (j=high) ) if(ri.key=rj.key) if(ri.key=rj.key) / /從兩個(gè)有序文件中的第一個(gè)記錄中選出小的記錄從兩個(gè)有序文件中的第一個(gè)記錄中選出小的記錄 r1k+=ri+;r1k+=ri+; else else r1k+=rj+; r1k+=rj+; while (i=m) r1k+=ri+; while (i=m) r1k+=ri+; / /* * 復(fù)制第一個(gè)文件的剩余記錄復(fù)制第一個(gè)文件的剩余記錄 * */ / while (j=high) r1k+=rj+; while (j=high) r1k+=rj+; / /* * 復(fù)制第二個(gè)文件的剩余記錄復(fù)制第二個(gè)文件的剩余記錄 * */ / 算法算法7.12 7.12 一趟歸并算法一趟歸并算法/ /* * 對(duì)對(duì)r r做一趟歸并，結(jié)果放在做一趟歸并，結(jié)果放在r1r1中中 * */ /void mergePass(RecordNode r,RecordNode r1,int n,int length)void mergePass(RecordNode r,RecordNode r1,int n,int length) / /* * length length為本趟歸并的有序子文件的長(zhǎng)度為本趟歸并的有序子文件的長(zhǎng)度 * */ / int i, j; int i, j; i=0; i=0; while(i+2 while(i+2* *length-1n)length-1n) merge(r,r1,i,i+length-1,i+2 merge(r,r1,i,i+length-1,i+2* *length-1);length-1); / /* * 歸并長(zhǎng)度為歸并長(zhǎng)度為lengthlength的兩個(gè)子文件的兩個(gè)子文件* */ / i+=2 i+=2* *length;length; if(i+length-1n-1) if(i+length-1n-1) / /* * 剩下兩個(gè)子文件，其中一個(gè)長(zhǎng)度小于剩下兩個(gè)子文件，其中一個(gè)長(zhǎng)度小于 length length * */ / merge(r,r1,i,i+length-1,n-1); merge(r,r1,i,i+length-1,n-1); else else for(j=i; jn; j+) for(j=i; jn; j+) / /* * 將最后一個(gè)子文件復(fù)制到數(shù)組將最后一個(gè)子文件復(fù)制到數(shù)組r1r1中中 * */ / r1j=rj; r1j=rj; 算法算法7.13 7.13 二路歸并算法二路歸并算法void mergeSort(SortObject void mergeSort(SortObject * * pvector) pvector) RecordNode recordMAXNUM; RecordNode recordMAXNUM; int length; int length; length=1; length=1; while(lengthn) while(lengthn) mergePass(pvector-record,record,pvector-n,length); mergePass(pvector-record,record,pvector-n,length); / /* * 一趟歸并，結(jié)果存放在數(shù)組一趟歸并，結(jié)果存放在數(shù)組r1r1中中* */ / length length* *=2;=2; mergePass(record,pvector-record,pvector-n,length); mergePass(record,pvector-record,pvector-n,length); / /* * 一趟歸并，結(jié)果存放在數(shù)組一趟歸并，結(jié)果存放在數(shù)組r r中中 * */ / length length* *=2;=2; l8.6.2 外排序（略） 排序方法最壞時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度 輔助空間 穩(wěn)定性直接插入排序O(n2) O(n2) O(1) 穩(wěn)定的二分法插入排序O(n2) O(n2) O(1) 穩(wěn)定的表插入排序O(n2) O(n2) O(n) 穩(wěn)定的Shell排序O(n1.3) O(n1.3) O(1) 不定的直接選擇排序O(n2) O(n2) O(1)不穩(wěn)定的堆排序O(nlog2n) O(nlog2n) O(1)不穩(wěn)定的起泡排序O(n2) O(n2) O(1) 穩(wěn)定的快速排序O(n2) O(nlog2n) O(log2n)不穩(wěn)定的基數(shù)排序O(d(n+r) O(d(n+r) O(r+n) 穩(wěn)定的歸并排序O(nlog2n) O(nlog2n) O(n) 穩(wěn)定的結(jié)論： （1）平均時(shí)間性能：以快速排序法最佳，但最壞情況下不如堆排序和歸并排序；在n較大時(shí)，歸并排序比堆排序快，但所需輔助空間最多。 （2）簡(jiǎn)單排序以直接插入排序最簡(jiǎn)單，當(dāng)下列中記錄“基本有序“或n值較小時(shí)，是最佳的排序方法。因此常和其他排序方法結(jié)合使用。 （3）基數(shù)排序最適用于n值很大而關(guān)鍵字較小的序列。若關(guān)鍵字也很大，而序列中大多數(shù)記錄的”最高位關(guān)鍵字”均不同，則也可以先按“最高位關(guān)鍵字”不同將序列分成若干個(gè)子序列，而后用直接插入排序。 （4）從穩(wěn)定性來(lái)看，基數(shù)排序是穩(wěn)定的排序方法，大部分時(shí)間復(fù)雜度為O(n2)的簡(jiǎn)單排序法都是穩(wěn)定的。然而，快速排序、堆排序和希爾排序等時(shí)間性能較好的排序都是不穩(wěn)定的。一般來(lái)說(shuō)，排序過程中的比較是在相鄰的兩個(gè)記錄關(guān)鍵字之間進(jìn)行的排序方法是穩(wěn)定的。大多數(shù)情況下排序是按記錄的主關(guān)鍵字進(jìn)行的，則所有的排序方法是否穩(wěn)定無(wú)關(guān)緊要。當(dāng)排序是按記錄的次關(guān)鍵字進(jìn)行時(shí)，則應(yīng)根據(jù)問題所需慎重選擇。 本章討論的大多數(shù)算法是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行的，因此在排序過程中要進(jìn)行大量的記錄的移動(dòng)。當(dāng)記錄很大（即每個(gè)記錄所占的空間很大）時(shí)，記錄移動(dòng)所耗費(fèi)的時(shí)間也很多，此時(shí)可采用靜態(tài)鏈表作存儲(chǔ)結(jié)構(gòu)，如表插入排序，鏈?zhǔn)交鶖?shù)排序，以修改指針代替移動(dòng)記錄。但有些方法如快速排序法是無(wú)法實(shí)現(xiàn)表排序的，在這種情況下，可以進(jìn)行“地址排序”，即另設(shè)一個(gè)向量指示需要記錄，同時(shí)在排序過程中不移動(dòng)記錄而移動(dòng)地址向量中相應(yīng)分量的內(nèi)容。lP278 復(fù)習(xí)題 1，2，3l 算法題2，3，4