【文章內容簡介】 換 ： 第四次交換： 江蘇信息職業(yè)技術學院畢業(yè)論文 12 第五次交換： 第六次交換： 第七次交換： 13 第八次交換： 第九次交換： 全程交換完成，得到最小值為 3 并且輸出它。從序列中刪除 3 ，重新建立堆。以次循環(huán)，直到全部輸出完成為止。 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用 Heapify 實現(xiàn)的。堆排序的最 壞時間復雜度為 O(nlogn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 堆排序是不穩(wěn)定的，算法時間復雜度 O(nlogn)。 快速排序 基本原理 江蘇信息職業(yè)技術學院畢業(yè)論文 14 首先我們選擇一個中間值 middle （程序中我們可使用數(shù)組中間值），把比中問值小的放在其左邊，比中問值大的放在其右邊。由于這個排序算法較復雜，我們先給出其進行一次排序的程序框架。 在 待排序的個記錄中任意取一個記錄（通常取第一個記錄） 為區(qū)分標準，把所有小于該排序的記錄移到左邊，把所有大于該排 序碼的記錄移到右邊，中級放所選記錄，為一趟快速排序。然后對前后兩個子序列分別重新上述過程，直到所有記錄都排好序。 對任意給定的序列中某個元素，經(jīng)過一趟排序后，將原序列分割成兩個子序列 (Rp(0),Rp(1),?,R p(s1))和 (Rp(s+1),Rp(s+2),?,R p(n1))，其中前一個子序列中的所有元素的關鍵詞均小于或等于該元素的關鍵詞值 Kp(s)，后一個子序列中元素的關鍵詞均大于或等于 Kp(s)。稱該元素 Rp(s)為分割元素，子序列(Rp(0),Rp(1),?,R p(s1))為其低端序列， (Rp(0),Rp(1),?,R p(s1))為其高端序列。很明顯，以后只需對低端和高端序列分別進行快速排序，直到子序列為空或只有一個元素時結束，最后得到有序序列。 總之，每趟使表的第一個元素放在適當位置，將表兩分，再對 子表進行同樣的 遞歸劃分，直至劃分的子表長度為 1。 排序過程 假設要排序的數(shù)組是 A[1]?? A[N]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1） 設置兩個變量 I、 J，排序開始的時候 I=1， J=N； 2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給 X，即 X=A[1]； 3） 從 J開始向前搜索，即由后開始向前搜索（ J=J1），找到第一個小于 X的值，兩者交換； 4） 從 I開始向后搜索，即由前開始向后搜索（ I=I+1），找到第一個大于 X的值，兩者交換； 5） 重復第 4 步，直到 I=J； 例如：待排序的數(shù)組 A的值分別是： A[1] A[2] A[3] A[4] A[5] A[6] A[7]： 49 38 65 97 76 13 27 進行第一次交換后： 27 38 65 97 76 13 49 15 進行第二次交換后 : 27 38 49 97 76 13 65 進行第三次交換后： 27 38 13 97 76 49 65 進行第四次交換后： 27 38 13 49 76 97 65 此時再執(zhí)行第三步 的時候就發(fā)現(xiàn) I=J，從而結束一躺快速排序，那么經(jīng)過一躺快速排序之后的結果是： 27 38 13 49 76 97 65，即所以大于 49 的數(shù)全在 49的后面，所以小于 49的數(shù)全部在 49的前面。 快速排序就是遞歸調用此過程 —— 在以 49 為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列，根據(jù)這種思想對于上述數(shù)組 A的快速排序的全過程如 下 所示： 初始狀態(tài) : {49 38 65 97 76 13 27} 進行一次快速排序之后劃分為 :{27 38 13} 49 {76 97 65} 分別對前后兩部分進行快速排序 : {13} 27 {38}。{97} 76 {65} 如果每一次分劃操作后，左、右兩個子序列的長度基本相等，則快速排序的效率最高，其最好情況時間復雜度為 O(nlog2n)；反之，如果每次分劃操作所產(chǎn)生的兩個子序列，其中 之一為空序列，此時，快速排序效率最低，其最壞情況時間復雜度為 O(n2)。如果選擇左邊第一個元素為主元，則快速排序的最壞情況發(fā)生在原始序列正向有序或反向有序時?？焖倥判虻钠骄闆r時間復雜度為 O(nlog2n)。 江蘇信息職業(yè)技術學院畢業(yè)論文 16 第三 章 系統(tǒng)設計 數(shù)據(jù) 定義 輸入數(shù)據(jù)： 由于 大多數(shù)排序算法的時間 開銷主要是關鍵字之間的比較和記錄的移動， 算法的 執(zhí)行時間不僅依賴于問題的規(guī)模，還取決于輸入實例中數(shù)據(jù)的狀態(tài)。 所以對于輸入數(shù)據(jù)，我們采用由 用戶輸入記錄的個數(shù) （ 以關鍵字的數(shù)目分別為 20， 100， 500為例 ） ， 測試 數(shù)據(jù)由隨機數(shù)產(chǎn)生器 生成。 輸出數(shù)據(jù)： 產(chǎn)生的隨機數(shù)分別用 直接插入排序 ； 直接選擇排序；起 泡排序； Shell排序 ；快速排序； 堆排序 這些排序方法進行排序，輸出關鍵字的比較次數(shù)和移動次數(shù)。 程序流程圖 圖 程序流程圖 主程序 產(chǎn)生 1 組隨機數(shù) 起泡 排序 Shell排序 快速 排序 直接選擇排序 堆排序 記錄關鍵字的比較次數(shù)和移動次數(shù) 將隨機數(shù)保存在數(shù)組中 循環(huán) 20 次 輸出關鍵字的比較次數(shù)、移動次數(shù)的平均值 直接插入排序 17 數(shù)據(jù)結構設計 本程序中，考慮的內容就是待排序對象，排序的依據(jù)是關鍵字之間的大小比較，故在每個節(jié)點的類型定義中，至少得包含關鍵字 key 一項。不失一般性，這里就使用關鍵詞這一項，其他都省略，具體應用加上其他數(shù)據(jù)項即可。被排序對象 是由一個個節(jié)點夠成，一個排序對象包含一系列指向一串節(jié)點的指針，排序對象的長度。本程序功能簡單。 typedef struct { int key。 /*關鍵字 */ }RecordNode。 /*排序節(jié)點的類型 */ typedef struct { RecordNode *record。 int n。 /*排序對象的大小 */ }SortObject。 /*排序節(jié)點的類型 */ 系統(tǒng)的模塊劃分及模塊功能 實現(xiàn) 圖 系統(tǒng)模塊劃分圖 InsertSort Select Sort ShellSort BubbleSort Quick Sort HeapSort Sort Method Main Output Quick 江蘇信息職業(yè)技術學院畢業(yè)論文 18 各 排序模塊 功能實現(xiàn) A．直接插入排序 void InsertSort(SortObject *p,unsigned long *pare,unsigned long *exchange) { int i,j。 RecordNode temp。 SortObject *pvector。 if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL) { printf(OverFollow!)。 getchar()。 exit(1)。 } for(i=0。ipn。i++)/* 復制數(shù)組 */ pvectorrecord[i]=precord[i]。 pvectorn=pn。 *pare=0。 *exchange=0。 for(i=1。ipvectorn。i++) { temp=pvectorrecord[i]。 (*exchange)++。 j=i1。 while((pvectorrecord[j].key)amp。amp。(j=0)) { (*pare)++。 (*exchange)++。 19 pvectorrecord[j+1]=pvectorrecord[j]。 j。 } if(j!=(i1)) { pvectorrecord[j+1]=temp。 (*exchange)++。 } } free(pvector)。 } 當文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復雜度為 O(n)，最壞情況是文件初態(tài)為反序，相應的時間復雜度為 O(n2)，算法的平均時間復雜度是 O(n2)。算法的輔助空間復雜度是 O(1)，是一個就地排序。 void SelectSort(SortObject *p,unsigned long *pare,unsigned long *exchange) { int i,j,k。 RecordNode temp。 SortObject *pvector。 if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL) { printf(OverFollow!)。 getchar()。 exit(1)。 } for(i=0。ipn。i++)/*復制數(shù)組 */ 江蘇信息職業(yè)技術學院畢業(yè)論文 20 pvectorrecord[i]=precord[i]。 pvectorn=pn。 *pare=0。 *exchange=0。 for(i=0。ipvectorn1。i++) { k=i。 for(j=i+1。jpvectorn。j++) { (*pare)++。 if(pvectorrecord[j].keypvectorrecord[k].key) k=j。 } if(k!=i) { temp=pvectorrecord[i]。 pvectorrecord[i]=pvectorrecord[k]。 pvectorrecord[k]=temp。 ( *exchange)+=3。 } } free(pvector)。 } 選擇排序法的第一層循環(huán)從起始元素開始選到倒數(shù)第二個元素 ,主要是在每次進入的第二層循環(huán)之前 ,將外層循環(huán)的下標賦值給臨時變量 ,接下來的第二層循環(huán)中 ,如果發(fā)現(xiàn)有比這個最小位置處的元素更小的元素 ,則將那個更小的元素的下標賦給臨時變量 ,最后 ,在二層循環(huán)退出后 ,如果臨時變量改變 ,則說明 ,有比當前外層循環(huán)位置更小的元素 ,需要將這兩個元素交換 . 21 void BubbleSort(SortObject *p,unsigned long *pare,unsigned long *exchange) { int i,j,noswap。 RecordNode temp。 SortObject *pvector。 if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL) { printf(OverFollow!)。 getchar()。 exit(1)。 } for(i=0。ipn。i++)/* 復制數(shù)組 */ pvectorrecord[i]=precord[i]。 pvectorn=pn。 *pare=0。 *exchange=0。 for(i=0。ipvectorn1。i++) { noswap=1。 for(j=0。jpvectorni1。j++) { (*pare)++。 if(pvectorrecord[j+1].keypvectorrecord[j].key) { temp=