課件數(shù)據(jù)結(jié)構(gòu)chapter

1、數(shù) 據(jù) 結(jié) 構(gòu) DATA STRUCTURE, DS 授課教師：郭 艷授課班級: 191131-2中國地質(zhì)大學(xué)計算機學(xué)院2014年秋上堂課要點回顧圖的應(yīng)用三：拓?fù)渑判騿栴}提出AOV網(wǎng)和拓?fù)渑判虻亩x算法 借助?；蜿犃袌D采用鄰接矩陣結(jié)構(gòu)O(n2)，采用鄰接表O(n+e)圖的應(yīng)用四：關(guān)鍵路徑兩個問題的提出AOE網(wǎng)和關(guān)鍵路徑的定義事件vj的最早發(fā)生時間Ve(j)計算事件vj的最遲發(fā)生時間Vl(j)計算活動ai的最早開始時間e(i)計算活動ai的最遲開始時間l(i)計算關(guān)鍵活動第 十七 次 課閱讀： 朱戰(zhàn)立，第228-240頁作業(yè)16數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容9.1 引言三種O(n2)的簡單排序算法9.2.1

2、直接插入排序 9.3.1 直接選擇排序9.4.1 冒泡排序9.2.2 希爾排序O(n3/2)9.3.2 堆排序O(nlogn) 9.4.2 快速排序O(nlogn)9.5 歸并排序O(nlogn)9.6 基數(shù)排序O(nlogn)9.7 排序算法性能比較Chapter 9 內(nèi)部排序9.1 引言排序（Sorting）記錄( record)是進行排序的基本單位。文件是記錄的集合。關(guān)鍵字( key )是唯一確定記錄的一個或多個域。設(shè)有一含n個記錄的文件R=r1, r2, , rn, 其對應(yīng)的關(guān)鍵字為 K=k1, k2, , kn，將此n個記錄按其關(guān)鍵字大小遞增（或遞減）的次序排列起來，成為一個有序的文

3、件R=r1, r2, ，rn，相應(yīng)關(guān)鍵字為K =k1, k2, ，kn, 這樣一種運算稱為排序。如果k1k2kn稱為不減序。如果k1k2kn 稱為不增序。正序序列：待排序序列正好符合排序要求。，逆序序列：把待排序序列逆轉(zhuǎn)過來，正好符合排序要求排序的類型內(nèi)部排序(internal sorting)：整個排序過程中所有的記錄都可以直接存放在內(nèi)存中 外部排序(external sorting)：內(nèi)存無法容納所有記錄，排序過程中還需要訪問外存 排序算法的衡量標(biāo)準(zhǔn)穩(wěn)定性(stability)“穩(wěn)定的”(stable)排序算法 ：如果存在多個具有相同關(guān)鍵字的記錄，經(jīng)過排序后這些記錄的相對次序仍然保持不變的

4、排序算法。例： 15，18，18，10，70，13，44 10，13，15，18，18，44，70 穩(wěn)定的 10，13，15，18，18，44，70 不穩(wěn)定的 穩(wěn)定的排序方法有：直接插入、冒泡、歸并、基數(shù)不穩(wěn)定的排序方法有：希爾、選擇（直接選擇、堆）、快速排序復(fù)雜度(complexity)時間代價：記錄的比較次數(shù)和記錄的交換次數(shù) 空間代價 如不作特別說明，記錄數(shù)據(jù)類型均為如下定義的DataType類型，且為了方便討論，設(shè)記錄的關(guān)鍵字類型為整型。采用一維數(shù)組描述待排序文件。 typedef int KeyType; typedef struct KeyType key; /*關(guān)鍵字域*/ /*其

5、它數(shù)據(jù)域*/ DataType;DataType a100;/待排序文件void swap (DataType a , int i, int j)/交換ai和ajDataType tmp = ai; ai = aj; aj = tmp;9.2 插入排序9.2.1 直接插入排序基本思想 依次將每個記錄插入到一個已排好序的子文件的合適位置中，插入后的文件仍然有序。 例： 8, 3, 2, 5, 9, 4, 6 假設(shè)前面幾個記錄已按關(guān)鍵字遞增的次序有序： 2, 3, 5, 8, 9 4 , 6 現(xiàn)將4插入以得到一個新的有序文件， 49，48，45 應(yīng)插在第3與5之間， 得到新的文件：2, 3, 4,

6、 5, 8, 9 6 i=1：(3) 3 8 2 5 9 4 6i=2：(2) 2 3 8 5 9 4 6i=3：(5) 2 3 5 8 9 4 6i=4：(9) 2 3 5 8 9 4 6i=5：(4) 2 3 4 5 8 9 6i=6：(6) 2 3 4 5 6 8 9 完成！i例：初始關(guān)鍵字： 8 3 2 5 9 4 6【直接插入排序算法】 void InsertSort(DataType a ,int n) /*用直接插入排序法對a0an-1排序*/ int i,j; DataType temp; /臨時變量 for(i=0;i-1&temp.keyn-1，每次比較aj和asmall：

7、 若aj.keyasmall.key，則small=j；循環(huán)退出后，如果small i, 則交換ai和asmall。例：465513429417570ijsmall=0jjjjjjsmall=2small=6smalli，交換5 55 13 42 94 1746 705 13 55 42 94 1746 705 13 17 42 94 5546 705 13 17 42 94 5546 705 13 17 42 46 5594 705 13 17 42 46 5594 705 13 17 42 46 5570 94 完成！【直接選擇排序算法】 void SelectSort(DataType

8、a ,int n) int i,j,small; for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(aj.keyasmall.key) small=j; if(small!=i) swap(a,i,small); 算法分析 不穩(wěn)定的排序算法 輔助空間：O(1) 時間： (1) 比較次數(shù) (2) 記錄移動次數(shù) 正序Mmin=0， 逆序Mmax=3(n-1) 總的時間復(fù)雜度仍為O(n2) 9.4 “交換”排序9.4.1 冒泡排序 基本思想不停地比較相鄰的兩個記錄，如果不滿足排序要求，就交換相鄰記錄，直到第n-1個記錄與第n個記錄進行比較、交換后為止，完成一

9、趟冒泡排序，使得關(guān)鍵字最大的記錄被安置在最后一個位置上。 然后，對前n-1個記錄進行同樣的操作，直到進行了n-1趟。改進避免不必要的比較。例如檢查每次冒泡過程中是否發(fā)生過交換，如果沒有，則表明整個數(shù)組已經(jīng)排好序了，排序結(jié)束。例： 初值：44 55 22 33 99 11 66 77第一趟排序之后：44 22 33 55 11 66 77 99第二趟排序之后：22 33 44 11 55 66 77 99第三趟排序之后：22 33 11 44 55 66 77 99第四趟排序之后：22 11 33 44 55 66 77 99第五趟排序之后：11 22 33 44 55 66 77 99第六趟排

10、序之后：11 22 33 44 55 66 77 99 完成！【改進的冒泡排序算法】 void BubbleSort(DataType a ,int n) /*用冒泡排序法對a0an-1排序*/ int i, j, flag=1; DataType temp; for(i=1;in&flag=1;i+) /共n-1趟 flag=0; for(j=0;jaj+1.key) flag=1; swap(a,j,j+1); 算法分析 穩(wěn)定的排序算法 輔助空間：O(1) 時間： (1) 比較次數(shù)最好（正序）要執(zhí)行1趟， 最小比較次數(shù)為n-1次。最壞（逆序）要執(zhí)行n-1趟，最大比較次數(shù)為： (2) 移動次

11、數(shù) 最小：不移動，為0。 最大：每次比較都移動3次，比較次數(shù)為最大移動量為 總的時間復(fù)雜度為O(n2)。三種簡單排序算法的比較直接插入排序直接選擇排序冒泡排序關(guān)鍵字比較次數(shù)記錄移動次數(shù)關(guān)鍵字比較次數(shù)記錄移動次數(shù)關(guān)鍵字比較次數(shù)記錄移動次數(shù)最好(正序)O(n）O(n)O(n2)0O(n)0最壞(逆序)O(n2)O(n2)O(n2)O(n)O(n2)O(n2)平均值O(n2)O(n2)O(n2)O(n)O(n2)O(n2)平均時間復(fù)雜度O(n2)O(n2)O(n2)空間復(fù)雜度O(1)O(1)O(1)三種簡單排序算法的特點 以上幾種排序方法（直接插入排序、直接選擇排序、冒泡排序）的共同特點是：以顯示或

12、者非顯示的方法對相鄰的元素進行比較和交換。 理論上可以證明：通過交換相鄰元素進行排序的任何算法的平均時間需要O（n2）。Data Structures and Algorithm Analysis in C. (Mark Allen Weiss.) 迫切需要更好的算法，以Donald Shell名字命名的希爾排序成為沖破二次時間屏障的第一批算法。 9.2.2 Shell排序直接插入排序的兩個性質(zhì)在最好情況下（即序列本身已是有序）時間代價為O(n)對于短序列，直接插入排序比較有效Shell排序有效地利用了直接插入排序的這兩個性質(zhì)9.2.2 Shell排序算法思想：先將序列轉(zhuǎn)化為若干小序列，在這些

13、小序列內(nèi)進行直接插入排序；通過逐漸擴大小序列的規(guī)模，從而逐漸減少小序列個數(shù)，使得待排序序列逐漸處于更有序的狀態(tài)；最后對整個序列進行掃尾直接插入排序，從而完成排序。 9.2.2 Shell排序（“縮小增量排序法”）技巧： 子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列。讓增量dk逐趟縮短，直到dk1為止。 “增量”的選擇： (1) 增量每次除以2遞減：d1=(2)2k-1，2k -1 -1，7，3，1 (3) 都取奇數(shù)： 如 17,15,13,11,9,7,5,3,1 (4) di之間互素：如 17,13,11,7,5, 3, 2, 1, di+1=例：記錄數(shù)n=

14、8，進行希爾排序初始： 465513429417570d2=2461754294551370第一趟排序結(jié)果：1755513d1=4第二趟排序結(jié)果：517134246559470d3=1513174246557094第三趟排序結(jié)果：void ShellInsertSort(DateType a,int n, int k, int span)/ span表示增量，將第k組增量為span的序列直接插入排序。int i, j; DataType tmp;/臨時變量for ( i = k; i = -1 & tmp.key=aj.key) a j+span = a j;j=j span ; a j+sp

15、an = tmp;void ShellSort(DateType a ,int n, int d , int numOfD )int m,span;/注意：增量每次遞減for (m=0; mnumOfD; m+)span=dm;for(k=0;k0;span=/2,i+) di=span;return i-1;main()int a8=46,55,13,42,94,17,5,70,n=8,d8, numOfD, i; numOfD =D(d,n); ShellSort(a, n, d , numOfD );for(i=0;in;i+) coutai“ “;希爾排序算法分析不穩(wěn)定的排序算法空間代價：O(1)時間代價：開始時dk 的值較大，子序列中的對象