c語言版習(xí)題數(shù)據(jù)結(jié)構(gòu)1

1、第十章 內(nèi)部排序10.1 概述10.2 插入排序 10.2.1 直接插入排序 10.2.3 shell排序10.3 交換排序（快速排序）10.4 選擇排序 10.4.1 簡單選擇排序 10.4.3 堆排序10.5 歸并排序10.6 基數(shù)排序10.7 各種排序方法的比較討論10.1 內(nèi)部排序概述排序(Sorting):將數(shù)據(jù)元素(或記錄)的一個任意序列,重新排列成一個按關(guān)鍵字有序的序列。排序方法的穩(wěn)定性：對關(guān)鍵字相同的數(shù)據(jù)元素，排序前后它們的領(lǐng)先關(guān)系保持不變，則稱該排序方法是穩(wěn)定的。反之，稱該排序方法是不穩(wěn)定的。內(nèi)部排序待排序記錄存放在計算機的內(nèi)存中進行排序。外部排序待排序記錄的數(shù)量很大，以致內(nèi)

2、存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序。排序的分類按排序過程依據(jù)的不同原則進行分類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序按工作量分類，可以分為三類：(1)簡單的排序方法,其時間復(fù)雜度為O(n2);(2)先進的排序方法,其時間復(fù)雜度為O(nlog2n);(3)基數(shù)排序，其時間復(fù)雜度為O(dn);排序的基本操作和記錄的存儲方式排序過程中需要的兩種基本操作：（1）比較關(guān)鍵字的大小；（2）將記錄從一個位置移至另一個位置。待排序記錄序列可有下列三種存儲方式：（1）記錄存放在一組連續(xù)的存儲單元中；類似于線性表的順序存儲結(jié)構(gòu)，記錄次序由存儲位置決定，實現(xiàn)排序需移動記錄。（2

3、）記錄存放在靜態(tài)鏈表中；記錄次序由指針指示，實現(xiàn)排序不需移動記錄，僅需修改指針。- 鏈排序（3）記錄本身存放在一組連續(xù)的存儲單元中，同時另設(shè)指示各個記錄存儲位置的地址向量，排序過程中不移動記錄本身，而移動地址向量中相應(yīng)記錄的地址。排序結(jié)束后再根據(jù)地址調(diào)整記錄的存儲位置。- 地址排序待排序記錄的數(shù)據(jù)類型#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key; InfoType otherinfo;RcdType;typedef struct RedType rMAXSIZE+1; int length;SqList;10.

4、2 插入排序10.2.1 直接插入排序例：序列為49，38，65，97，76，13，27，49 (49)，38，65，97，76，13，27，49 (38) (38，49)，65，97，76，13，27，49 (65) (38，49，65)，97，76，13，27，49 (97) (38，49，65，97)，76，13，27，49 (76) (38，49，65，76，97)，13，27，49 (13) (13，38，49，65，76，97)，27，49 (27) (13，27，38，49，65，76，97)，49 (49) (13，27，38，49，49，65，76，97)直接插入排序算法vo

5、id InsertSort(SqList &L) for(i=2; i=L.length; +i) if ( LT(L.ri.key, L.ri-1.key) ) L.r0 = L.ri; / 復(fù)制為哨兵 for(j=i-1; LT(L.r0.key, L.rj.key); -j) L.rj+1 = L.rj; / 記錄后移 L.rj+1 = L.r0; / InsertSort時間：最壞情形判斷與移動各接近 n(n+1)/2; 最好情形判斷n次，無移動；故時間復(fù)雜度：O(n2)空間：一個輔助空間10.2.2 Shell排序算法基本思想： 先將整個待排序記錄序列分割成若干子序列分別進行直接插入

6、排序，待整個序列“基本有序”時，再對全體記錄進行一次直接插入排序。算法復(fù)雜度：O(n3/2)Shell排序舉例（非穩(wěn)定的）二趟結(jié)果13，04，49，38，27，49，55，65，97，76增量取1：13，04，49，38，27，49，55，65，97，76三趟結(jié)果04，13，27，38，49，49，55，65，76，97一趟結(jié)果13，27，49，55，04，49，38，65，97，76增量取3：13 55 38 76 27 04 65 49 49 97例： 49，38，65，97，76，13，27，49，55，04增量取5： 49 13 38 27 65 49 97 55 76 0410.3

7、交換排序 1. 冒泡排序（其時間復(fù)雜度O(n2)）初始關(guān)鍵字第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后例： 49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 972. 快速排序- 對冒泡排序的一種改進基本思想： 通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)分別進行排序，以達到整個序列有序。快速排序舉例初始關(guān)鍵字

8、：49，38，65，97，76，13，27，49pivot key 49jji1次交換后：27，38，65，97，76，13， ，49iji2次交換后：27，38， ，97，76，13，65，49ijj3次交換后：27，38，13，97，76， ，65，49iji4次交換后：27，38，13， ，76，97，65，49jij一趟完成后：27，38，13，49，76，97，65，49快速排序分析快速排序的平均時間為T(n) = knlog(n)k為某個常數(shù)因子經(jīng)驗表明,在同數(shù)量級的排序方法中,快速排序的常數(shù)因子k最小.就平均時間而言,快速排序是最好的.若初始序列按關(guān)鍵字基本有序,快速排序蛻化為起

9、泡排序,其時間復(fù)雜度為O(n2)。改進的方法，用“三者取中”的法則選取樞軸記錄（pivotkey).快速排序舉例初始關(guān)鍵字：49，38，65，97，76，13，27，49pivot key 49jji1次交換后：27，38，65，97，76，13， ，49iji2次交換后：27，38， ，97，76，13，65，49ijj3次交換后：27，38，13，97，76， ，65，49iji4次交換后：27，38，13， ，76，97，65，49jij一趟完成后：27，38，13，49，76，97，65，49快速排序算法（一）int Partition(SqList &L, int low, int

10、high)L.r0 = L.rlow; / 用子表的第一記錄作樞軸記錄 pivotkey = L.rlow.key; while(lowhigh) while(low=pivotkey) -high; L.rlow = L.rhigh; / 將比pivotkey 小的記錄移到低端 while(lowhigh & L.rlow.key=pivotkey) +low; L.rhigh = L.rlow; / 將比pivotkey 大的記錄移到高端 L.rlow = l.r0; return low;快速排序算法（二）void Qsort(SqList &L, int low, int high)

11、if(lowhigh) pivotloc = Partition(L, low, high); Qsort(L, low, pivotloc-1); Qsort(L, pivotloc+1, high); / QSortvoid QuickSort(SqList &L) Qsort(L, 1, L.length); / QuickSort10.4 選擇排序 10.4.1. 簡單選擇排序（其時間復(fù)雜度O(n2)）基本思想： 每一趟在序列的后n-i+1(i=1,2,.,n-1)個記錄中選取關(guān)鍵字最小的記錄作為第i個記錄。void SelectSort(SqList &L) for(i=1; iL.

12、length; +i) j = SelectMinKey(L, i); / 在L.ri.length中選擇key最小 if(i != j) L.ri L.rj; / 與第i個記錄交換 / SelectSort初始關(guān)鍵字：49，38，65，97，76，13，27，49第一次交換：13，38，65，97，76，49，27，49ij10.4.3 堆排序堆的定義：n個元素的序列k1,k2,.,kn當(dāng)且僅當(dāng)滿足下列條件時，稱之為堆。ki = k2iki = k2i+1或( i = 1, 2, . , n/2 )堆舉例：96,83,27,38,11,09)12,36,24,85,47,30,53,9196

13、83381109271236854730245391完全二叉樹,且所有非葉結(jié)點的值均不大于(不小于)其左、右孩子結(jié)點的值實現(xiàn)堆要解決的問題（1）如何從一個無序序列建成一個堆？（2）如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？1236854730245391(a)9136854730245312(b)91368547302453(c)24368547913053(d)無序序列建成一個堆（從第n/2到1個元素） 49，38，65，97，76，13，27，494938497613652797(b)4938497665132797(c)49389776132749(a)654938497665

14、132797(d)1338497665274997(e)10.5 歸并排序(Merging Sort)將兩個或兩個以上的有序表組合成一個新的有序表2-路歸并舉例:初始關(guān)鍵字: 49 38 65 97 76 13 27一趟歸并后: 38 49 65 97 13 76 27二趟歸并后: 38 49 65 97 13 27 76 三趟歸并后: 13 27 38 49 65 76 97 2-路歸并算法void Merge(RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的SRi.m和SRm+1.n合并為有序的TRi.n for(j=m+1,k=i;

15、 i=m&j=n; +k) if LQ(SRi.key,SRj.key) TRk = SRi+; else TRk = SRj+; if(i=m) TRk.n = SRi.m; /復(fù)制剩余的SRi.m if(j=n) TRk.n = SRj.n; /復(fù)制剩余的SRj.n / Merge歸并算法的特點需要輔助空間: O(n)整個歸并需要 log2n 趟時間復(fù)雜度: O(n log2n)它是穩(wěn)定的排序方法思想可以推廣到 “多-路歸并“10.6 基數(shù)排序(Radix Sorting)不需要進行關(guān)鍵字之間的比較借助多關(guān)鍵字排序的思想對單關(guān)鍵字排序10.6.1 多關(guān)鍵字排序 2345678910JQKA

16、 2345678910JQKA2345678910JQKA2345678910JQKA花色 ()優(yōu)先于面值(23.109-063-930-589-184-505-269-008-0830132456789278109063930184505589269008083930-063-083-184-505-278-008-109-589-269930-063-083-184-505-278-008-109-589-2690132456789278109063930184505589269008184505-008-109-930-063-269-278-083-184-58901324567895

17、05008109930063269278083083589008-063-083-109-184-269-278-505-589-930基數(shù)排序分析(d個關(guān)鍵字的取值范圍rd）“收集”重復(fù)的次數(shù)為d;一輪“分配”的次數(shù)為n+rd;時間復(fù)雜度為O(d(n+rd);鏈?zhǔn)交鶖?shù)排序所需輔助存儲量為O(n)。10.7 各種排序方法的比較討論排序方法簡單排序Shell排序快速排序堆排序歸并排序基數(shù)排序平均時間O(n2)O(n3/2)O(nlogn)O(nlogn)O(nlogn)O(d(n+rd)最壞情況O(n2)O(n2)O(n2)O(nlogn)O(nlogn)O(d(n+rd)輔助存儲O(1)O(1)O(logn)O(1)O(n)O(rd)插入, 交換, 選擇, 歸