李瑜波數(shù)據(jù)結(jié)構(gòu)中的排序算法操作論文

1、四川大學(xué)軟件工程碩士數(shù)據(jù)結(jié)構(gòu)論文論文題目: 數(shù)據(jù)結(jié)構(gòu)中的排序算法操作姓名：_李瑜波_學(xué)號：_2012年3月16日數(shù)據(jù)結(jié)構(gòu)中的排序算法操作經(jīng)濟學(xué)院 （李瑜波）摘要：本文通過對數(shù)據(jù)結(jié)構(gòu)中排序算法深入研究,實現(xiàn)了排序算法中的直接插入排序、快速排序和簡單選擇排序操作，進一步加深了對數(shù)據(jù)結(jié)構(gòu)中排序算法的理解，得到的算法可以應(yīng)用到以后的編程實踐中。最后給出了各個算法時間復(fù)雜度、空間復(fù)雜度和算法穩(wěn)定性的分析。關(guān)鍵詞：排序 時間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 The Algorithms of sorting in data structure Absract: This paper gives a deep e

2、xploration of sorting in data structure, implem-ents the Straight insertion_sort Quick_sort and Simple selection_sort of it. The algorithm we get could be used in the later programming experience. The last of the paper gives time complexity space complexity and stability of every algorithms.Keywords

3、: sorting time complexity space complexity stability1.引言排序是日常生活和工作中的一個常見問題，其目的是將一組原本無序的數(shù)據(jù)元素（或記錄）序列，按照人們所需要的順序，排列成有規(guī)律的按關(guān)鍵字有序的序列。在現(xiàn)實生活中，人們要用到排序。如：學(xué)生成績往往需要按照成績高低或按學(xué)號從前到后排序；在圖書館眾多的圖書中，需要按照各個學(xué)科將書籍歸類；排隊時從高到低的順序排隊等問題。同樣，排序也是計算機程序設(shè)計中的一個非常重要的操作，在計算機軟件設(shè)計中占有極其重要的地位。本文將對排序算法中直接插入排序、快速排序和簡單選擇排序三種算法的實現(xiàn)做一些研究。2. 算法

4、的實現(xiàn)2.1 數(shù)據(jù)結(jié)構(gòu)描述本文研究的待排序的記錄采用順序存儲結(jié)構(gòu)，設(shè)記錄的關(guān)鍵字均為整數(shù)。待排序的記錄的數(shù)據(jù)類型為： #define MAXSIZE 20 / 順序表最大長度的假定值typedef int KeyType; / 不妨設(shè)關(guān)鍵字類型為整型typedef struct KeyType key; / 關(guān)鍵字域 InfoType otherinfo; / 其他域RedType; / 記錄類型typedef struct RedType rMAXSIZE+1;/r0閑置或用作監(jiān)視哨單元 int length; / 順序表長度SqList; / 順序表類型2.2 函數(shù)功能的描述 假設(shè)待排序的

5、記錄的關(guān)鍵字序列為：49,38,65,97,76,13,27,49，排序以后的記錄按關(guān)鍵字非遞減有序 直接插入排序的基本思想：每次將待排序的一個記錄按其關(guān)鍵字大小插入到已經(jīng)排好序的子序列中，直到所有的記錄都插入完為止。直接插入排序的過程如圖2.1所示：初始關(guān)鍵字 （49） 38 65 97 76 13 27 49i=2: (38) (38 49) 65 97 76 13 27 49i=3: (38) (38 49 65) 97 76 13 27 49i=4: (38) (38 49 65 97) 76 13 27 49i=5: (76) (38 49 65 76 97) 13 27 49i=6

6、: (13) (13 38 49 65 76 97) 27 49i=7: (27) (13 27 38 49 65 76 97) 49i=8: (49) (13 27 38 49 49 65 76 97) 監(jiān)視哨L.r0圖2.1 快速排序的基本思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠值挠涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序以達到整個序列有序。整個排序過程采用遞歸方式，一趟快速排序過程如圖2.2(a)圖所示： pivotkey初始關(guān)鍵字 49 38 65 97 76 13 27 49 i j j 進行1次移動后 27 38 65 97 76

7、 13 49 i i j 進行2次移動后 27 38 97 76 13 65 49 i j j 進行3次移動后 27 38 13 97 76 65 49 i i j 進行4次移動后 27 38 13 76 97 65 49 i j j 完成一趟排序 27 38 13 49 76 97 65 49圖 2.2(a)排序的全過程如圖2.2(b)所示：初始狀態(tài) 49 38 65 97 76 13 27 49一次劃分之后 27 38 13 49 76 97 65 49分別進行快速排序13 27 38 結(jié)束 結(jié)束 49 65 76 97 49 65 結(jié)束 結(jié)束有序序列 13 27 38 49 49 65

8、76 97圖 2.2(b) 簡單選擇排序的基本思想：每一趟在n-i+1(i=1,2,n-1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個記錄，并和第i(0<i<n+1)個記錄交換。簡單選擇排序的過程如圖2.3所示：4938659776132749第1趟 13 38659776492749第2趟1327659776493849第3趟1327389776496549第4趟1327384976976549第5趟1327384949976576第6趟1327384949659776第7趟1327384949657697圖2.32.3 算法實現(xiàn) 直接插入排序算法中，第i趟進行的操作為：

9、在含有i-1個記錄的有序子序列r1i-1中插入一個記錄ri后，變成含有i個記錄的有序子序列r1.i；并且為了在查找插入位置的過程中避免數(shù)組下標出界，在r0處設(shè)置監(jiān)視哨，在自i-1起往前搜索的過程中，可以同時后移記錄。算法1 直接插入排序算法Step1:從第二個記錄起逐個進行關(guān)鍵字與前面關(guān)鍵字的比較并判斷是否把該記錄作為哨兵 for ( i=2; i<=L.length; +i ) if(LT(L.ri.key, L.ri-1.key) L.r0 = L.ri; /若“<”，將L.ri復(fù)制為哨兵Step2:在進行關(guān)鍵字比較的同時后移記錄 for ( j=i-1; LT( L.r0.k

10、ey, L.rj.key ); -j ) L.rj+1 = L.rj; /記錄后移Step3:把記錄插入到正確的位置 L.rj+1 = L.r0; /插入到正確位置快速排序算法中，一趟快速排序的具體作法為：附設(shè)兩個指針low和high，他們的初值分別為low和high，設(shè)樞軸的關(guān)鍵字為pivokey，則首先從high所指位置起向前搜索找到第一個關(guān)鍵字小于pivokey的記錄和樞軸記錄相互交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大于的pivokey記錄和樞軸記錄相互交換，重復(fù)這兩步直至low=high為止。算法2.1 一趟快速排序算法Step1:選取一個記錄作為樞軸，并把關(guān)鍵字附給

11、pivokey L.r0 = L.rlow; /用子表的第一個記錄作樞軸記錄pivotkey = L.rlow.key; /樞軸記錄的關(guān)鍵字Step2: 從high所指位置起向前搜索找到第一個關(guān)鍵字小于pivokey的記錄和樞軸記錄相互交換,同時把比樞軸小的記錄移到低端 while (low<high && L.rhigh.key>=pivotkey) -high; L.rlow = L.rhigh； /將比樞軸記錄小的記錄移到低端Step3: 從low所指位置起向前搜索找到第一個關(guān)鍵字大于pivokey的記錄和樞軸記錄相互交換,同時把比樞軸小的記錄移到高端 whi

12、le (low<high && L.rlow.key<=pivotkey) +low; L.rhigh = L.rlow /將比樞軸記錄大的記錄移到高端Step4: 當low=high時，把樞軸記錄移到位，并且返回樞軸位置L.rlow = L.r0 /樞軸記錄到位return low /返回樞軸位置算法2.2 遞歸快速排序算法Step1:通過調(diào)用QSort函數(shù)把整個順序表一分為二QSort( L, 1, L.length );Step2:把子表再一分為二，然后分別對低子表和高子表進行劃分pivotloc = Partition( L, low, high );/將L

13、.rlow.high一分為二QSort( L, low, pivotloc-1 ); /對低子表遞歸排序QSort( L, pivotloc+1, high ); /對高子表遞歸排序 簡單選擇排序中，第i趟進行的操作為：從第i+1個記錄到第n個記錄中選一個關(guān)鍵字最小的記錄，然后與第i個記錄進行交換。算法3 簡單選擇排序算法Step1:從個i+1記錄開始從中選一個關(guān)鍵字最小的記錄 for ( i=1; i<L.length; +i ) / i 為選擇區(qū)間下界 j = i; / j 指向當前的初始記錄 for ( k=i+1; k<=L.length; +k ) if ( L.rk.k

14、ey<L.rj.key ) j = k; /讓j指向當前最小的記錄Step2:將找到的最小的記錄與第i個記錄交換if ( i != j ) L.ri«L.rj; /與第個i記錄交換3. 算法分析 3.1直接插入排序從時間復(fù)雜度方面來看：當初始記錄的關(guān)鍵字序列按非遞減有序時，所需進行的關(guān)鍵字間的比較次數(shù)達到最小值n-1，記錄不需移動；反之當初始記錄的關(guān)鍵字序列按非遞增有序時，總的比較次數(shù)達到最大值(n+2)(n-1)/2,記錄移動的次數(shù)也達到最大值(n+4)(n-1)/2。而初始記錄是隨機的，則取上述最大值和最小值的平均值作為直接插入排序的時所需進行關(guān)鍵字間的比較次數(shù)和移動記錄的

15、次數(shù)，約為n2/4。由此，直接插入排序的時間復(fù)雜度為O(n2)。從空間復(fù)雜度方面來看：直接插入排序僅需要一個記錄的附加空間，所以其空間復(fù)雜度為O(1)。從排序的穩(wěn)定性方面來看：直接插入排序算法是一種穩(wěn)定的排序算法。 3.2 快速排序 從時間復(fù)雜度方面來看：最好的情況是每次劃分得到的兩個子序列的長度大致相等，在這種情況下排序過程所需要的比較次數(shù)為O(n·log2n)，最壞的情況是，每次劃分得到的子序列有一個為空，而另一個長度為n-1,此時需要進行n-1趟快速排序，整個過程的比較次數(shù)為：n(n-1)/2。由于快速排序過程中記錄移動的次數(shù)不會超過關(guān)鍵字的比較次數(shù)，因此，快速排序最好的時間復(fù)

16、雜度為O(n·log2n)，最壞的時間復(fù)雜度為O(n2)。 從空間復(fù)雜度方面來看：快速排序算法需要遞歸調(diào)用，系統(tǒng)內(nèi)部需要用一個棧來保存參數(shù)。當每次劃分均勻時，棧的最大深度為ëlog2 nû +1，若每次劃分極不平衡時，棧的最大深度為n。所以最好的情況下空間復(fù)雜度為O(log2n)，最壞情況下的空間復(fù)雜度為O(n)，就平均而言，空間復(fù)雜度為O(log2n)。 從排序的穩(wěn)定性方面來看：快速排序算法是不穩(wěn)定的。 3.3簡單選擇排序從時間復(fù)雜度方面來看：在一趟排序中關(guān)鍵字的比較次數(shù)為n-1次，在第二趟排序中關(guān)鍵字的比較次數(shù)為n-2次，第i趟排序中關(guān)鍵字的比較次數(shù)為n-i次，總的比較次數(shù)為n(n-1)/2。而在各次排序中，記錄的移動次數(shù)最好的情況是該記錄正好處于合適的位置上，不需要移動，此時移動次數(shù)為0次，最壞的情況需要交換記錄的位置，此時的移動次數(shù)為3次，所以總的移動次數(shù)最好為0次，最壞為3(n-1)次，由此可知，簡單選擇排序的時間復(fù)雜度為O(n2)。從空間復(fù)雜度方面來看：簡單選擇排序在交換記錄時需要一個記錄大小的緩