計算機(jī)應(yīng)用基礎(chǔ)教學(xué)課件排序

1、第 1 章 數(shù)據(jù)結(jié)構(gòu) 主要內(nèi)容1.1 基本數(shù)據(jù)結(jié)構(gòu)與算法 1.2 線性表 1.3 棧和隊列1.4 樹和二叉樹 1.5 查找1.6 排序ABCDEFG姓名 學(xué)號 成績 班級 李紅 9761059 95 機(jī)97.6 1065865 牛牛文庫文檔分享1.6 排序排序又稱分類，是計算機(jī)程序設(shè)計中一個重要運算，它的功能是將一組任意序列的數(shù)據(jù)元素，進(jìn)行按關(guān)鍵字由大到小的順序（降序）排列或按由小到大的順序（升序）排列。 排序的對象：這些數(shù)據(jù)元素可以是數(shù)值型，也可以為字符型。若為數(shù)值型，則按數(shù)值大小排列；若為字符型，則按其ASCII碼的順序排列。排序的依據(jù)：在實際應(yīng)用中，參加排序的數(shù)據(jù)元素有時不是單個數(shù)據(jù)項，

2、而是由多個數(shù)據(jù)項組成的記錄。此時排序應(yīng)按照關(guān)鍵字的大小進(jìn)行。所謂關(guān)鍵字是指記錄中的某個數(shù)據(jù)項，用它可以標(biāo)識一個記錄。若此關(guān)鍵字可以唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字；反之，把用以識別若干記錄的關(guān)鍵字稱為次關(guān)鍵字。 學(xué)號姓名系別住址電話981111李洪機(jī)械六舍5371111982111王剛電子四舍5372111983211王將計算機(jī)五舍5373211983212張強(qiáng)機(jī)械六舎5372221 牛牛文庫文檔分享排序的穩(wěn)定性：在待排序的記錄中，若存在多個關(guān)鍵在相同 的記錄，經(jīng)過排序后，這些具有相同關(guān)鍵在 的記錄之間的相對次序發(fā)生變化，則稱這種 排序方法是穩(wěn)定的；否則，是不穩(wěn)定的。排序的分類：內(nèi)部

3、排序與外部排序 內(nèi)部排序:整個排序過程完全在內(nèi)存中進(jìn)行. 外部排序:由于待排序記錄數(shù)據(jù)量太大,內(nèi)存無法容納 全部數(shù)據(jù),排序需要借助外部存儲設(shè)備才能 完成.排序算法評價： 算法執(zhí)行時間(最好、最差及平均情況)、需要附加空間大小1.6 排序 牛牛文庫文檔分享插入排序的基本思想：1.6.2 插入排序插入排序三種方法1. 直接排序: 認(rèn)可第1個記錄已排好序，然后將第2個到第n個記錄依次插入到前面已排好序的記錄組成的文件中。 2.折半插入排序: 折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。3.希爾排序: 將整個無序序列分割成若干個子序列分

4、別進(jìn)行直接插入排序. 將待排序文件中的記錄，逐個按其排序碼值的大小插入到已排好序的若干個記錄組成的文件中的適當(dāng)位置，保持新文件有序。 牛牛文庫文檔分享1.直接插入排序: 思路：認(rèn)可第1個記錄已排好序，然后將第2個到第n個記錄依次插入到前面已排好序的記錄組成的文件中。 具體過程(第i個記錄Ri插入到前面i-1個已排好序的記錄中) 將Ri的排序碼與前面已排好序的排序碼從右向左依次比較，找到Ri應(yīng)插入的位置；將該位置以后直到Ri-1各記錄順序后移,空出位置插入Ri。1.6.2 插入排序 牛牛文庫文檔分享直接插入排序:次數(shù)i r0 r1 r2 r3 r4 r5 r6 r7 r8 (49) 39 66

5、96 76 11 37 50 (39 49) 66 96 76 11 37 50i=239(39 49 66) 96 76 11 37 50i=366(39 49 66 96) 76 11 37 50i=496(39 49 66 76 96) 11 37 50i=576(11 39 49 66 76 96) 37 50i=611(11 37 39 49 66 76 96) 50i=737(11 37 39 49 50 66 76 96) i=850對于有n個數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次 牛牛文庫文檔分享./*對N個整數(shù)進(jìn)行升序排序*/ for(i=1;i=0; k-) /尋找插入

6、位置if(aiak) break; /插入到第k個位置的后面 temp=ai; for(j=i-1;jk; j-) /向后移動 aj+1=aj; aj+1=temp; 牛牛文庫文檔分享./*改進(jìn)前面的算法*/ for(i=1;i=0 & tempaj若降序排序，則： 牛牛文庫文檔分享1.直接插入排序: 時效分析最好情況:初始排序碼已經(jīng)有序。共比較n-1次，移動0次。最壞情況:待排序序列完全逆序。比較和移動均為n(n-1)/2次。平均情況:比較和移動次數(shù)均約為n2/4，時間復(fù)雜度為O(n2)。1.6.2 插入排序該算法適合于n 較小的情況，時間復(fù)雜度為O(n2). 牛牛文庫文檔分享2、折半插入排

7、序 折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。例：有6個記錄，前5 個已排序的基礎(chǔ)上，對第6個記錄排序。 15 27 36 53 69 42 low mid high ( 4236 ,后半) 15 27 36 53 69 42 low high mid ( 4253 ,前半 ) 15 27 36 53 69 42 high low (high tj, tk=1。(2)按增量序列個數(shù)k，對序列進(jìn)行k趟排序。(3)每趟排序，根據(jù)對應(yīng)的增量ti，將序列分割成若干長度為m的子序列，分別對各子表直接插入排序。增量ti逐次減小， tk=1

8、時，再對全部元素進(jìn)行一次直接插入排序即可完成。1.6.2 插入排序 牛牛文庫文檔分享舉例: 有一個含有14個數(shù)的序列,使用希而排序進(jìn)行升序排序 ( 39,80,76,41,13,29,50,78,30,11,100,7,41,86 )取增量：5，3，1h=539 80 76 41 13 29 50 78 30 11 100 7 41 86(R1,R6, R11) 39 29 100(R2,R7, R12) 80 50 7(R3,R8, R13 ) 76 78 41(R4,R9, R14) 41 30 86(R5,R10 ) 13 11則子序列：39，29，100，80，50，7，76，78，4

9、1，41，30，86，13，11R1, R2, R3, R4, R5, R6, R7, R8, R9, R10 R11, R12, R13, R14 牛牛文庫文檔分享h=539 80 76 41 13 29 50 78 30 11 100 7 41 86子序列：39，29，100，80，50，7，76，78，41，41，30，86，13，11R1, R2, R3, R4, R5, R6, R7, R8, R9, R10 R11, R12, R13, R14 29 39 100 7 50 80 41 76 78 30 41 86 11 13因此第一趟排序結(jié)果如下: 29 7 41 30 11 3

10、9 50 76 41 13 100 80 78 86對每個序列進(jìn)行直接插入排序: 牛牛文庫文檔分享h=3 29 7 41 30 11 39 50 76 41 13 100 80 78 8629 30 50 13 78 7 11 76 100 86 41 39 41 80分別對以上3個子序列,即29，30，50，13，78，7，11，76，100，86，41，39，41，80進(jìn)行直接插入排序,13 7 39 29 11 41 30 76 41 50 86 80 78 100(R1,R4,R7,R10,R13)(R2,R5,R8,R11,R14)(R3,R6,R9,R12) R1 R2 R3 R4

11、 R5 R6 R7 R8 R9 R10 R11 R12 R13 R1413 29 30 50 78 7 11 76 86 100 39 41 41 80第二趟最終結(jié)果：第一趟排序結(jié)果 牛牛文庫文檔分享13 7 39 29 11 41 30 76 41 50 86 80 78 100h=1 序列基本有序，對其進(jìn)行直接插入排序,第三趟最終結(jié)果：7 11 13 29 30 39 41 41 50 76 78 80 86 100第二趟最終結(jié)果： 牛牛文庫文檔分享3 .希爾排序特點：每一遍以不同間隔距離插入排序。h較大時移動數(shù)據(jù)元素是跳躍式進(jìn)行。子序列每一次比較可能移去多個逆序(直接插入排序每次比較只能

12、移去一個)。效率較高。最后一次排序(h=1)時，已基本有序，不需要多少移動。故其時間復(fù)雜度較直接插入排序低。數(shù)學(xué)難題： 如何選取增量序列才能有最好的排序效果，至今未完整解決。但注意：增量序列中除1外沒有公因子，且最后一個增量序列必須為1。時效分析: 很難。比較次數(shù)與移動次數(shù)依賴于增量序列的選取，特定情況下可以估計. 1.6.2 插入排序 牛牛文庫文檔分享 對待排序記錄兩兩比較排序碼，不滿足排序順序則交換。直到任何兩個記錄排序碼滿足排序要求?；舅悸方粨Q排序種類:冒泡排序快速排序 1.6.3 交換排序 牛牛文庫文檔分享1. 冒泡排序基本思想：通過相鄰元素的交換，逐步將線性表變成有序?；具^程：第

13、一趟冒泡排序：首先第一個元素與第二個元素比較，逆序則 交換；然后第二個元素與第三個元素比較；直到第n-1個元素與第n個元素比較為止。結(jié)果（關(guān)鍵字）最大的元素放在最后位置。第二趟冒泡排序：對前面n-1個元素進(jìn)行相同操作，結(jié)果 次大元素放在n-1位置上。第i趟冒泡排序：對前面n-i+1個元素進(jìn)行相同操作，結(jié) 果(n-i+1)中最大元素放在(n-i+1)位置上。趟數(shù)：最多n-1 結(jié)束條件：在某一趟排序中沒有進(jìn)行交換元素操作。1.6.3 交換排序 牛牛文庫文檔分享38 49 65 76 13 27 30 97第一趟38 49 65 13 27 30 76第二趟38 49 13 27 30 65第三趟3

14、8 13 27 30 49第四趟13 27 30 38第五趟13 27 30第六趟49 38 65 97 76 13 27 30初始關(guān)鍵字n=83849769713972797309713767676273013652765306513134949304927382738303813 27第七趟思想：小的浮起， 大的沉底。 牛牛文庫文檔分享舉例:將數(shù)列 ( 8, 6, 5, 7, 1 ) 升序排序初始86571第一趟65718第二趟56178第三趟51678第四趟15678初始已排好序(正序最好)，則只需進(jìn)行一趟排序,比較次數(shù)n-1，移動次數(shù)為0。逆序(最壞)，則需進(jìn)行n-1趟排序, 比較次數(shù)

15、為(1+2+3+n-1)=n(n-1)/2。 是穩(wěn)定的排序,時間復(fù)雜度為O(n2 ),空間復(fù)雜度是O(1) . 時效分析:程序代碼: 牛牛文庫文檔分享#define N 5int gradeN,temp;for(i=0;iN;i+) scanf(%d,&gradei);for(i=0;iN-1;i+) for(j=0;j gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; 讀入5個值保存在數(shù)組中1671469085 牛牛文庫文檔分享temp=46temp=71temp=161671469085i=0 第1趟 j=0 從頭開始

16、比較 j4條件不成立 j=1 j4條件成立9046 j=2 j4條件成立9071 j=3 j49016 j=4內(nèi)層循環(huán)終止90即：i=0 第1趟 時 grade0 和grade1比較 grade1 和grade2比較 grade2 和grade3比較 grade3 和grade4比較 最大值放到grade4中#define N 5for(i=0; iN-1; i+) for(j=0; j gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; 即，i=0 第1趟 時內(nèi)存循環(huán)for(j=0; jN-1-i; j+)變量j是從0到3

17、的 牛牛文庫文檔分享1671469085i=1 第2趟 j=0 從頭開始比較90469071901690#define N 5for(i=0; iN-1; i+) for(j=0; j gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; 內(nèi)存循環(huán)for( j=0; jN-1-i; j+)中 j的取值從0到2 grade0 和grade1比較 grade1 和grade2比較 grade2 和grade3比較找出次大值放到grade3中 牛牛文庫文檔分享1671469085i=1 第2趟90469071901690854685

18、71851685#define N 5for(i=0; iN-1; i+) for(j=0; j gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; 牛牛文庫文檔分享16714685i=2 第3趟9046907190169085468571851685717116#define N 5for(i=0; iN-1; i+) for(j=0; j gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; 牛牛文庫文檔分享16714685i=3 第4趟90469071

19、90169085468571851685717116#define N 5for(i=0; iN-1; i+) for(j=0; j gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; 461646 牛牛文庫文檔分享2. 快速排序基本思想： 通過一趟排序?qū)⒋庞涗浄指畛瑟毩刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再對前、后兩部分待排記錄重復(fù)上述過程，直到所有子表表長不超過1為止。 優(yōu)點： 通過兩個不相鄰元素交換，可以一次交換消除多個逆序，加快排序速度。 49 39 66 96 76 11 27 50 27

20、39 11 49 76 96 66 50 27 39 49 50 66 76 96 1.6.3 交換排序 牛牛文庫文檔分享2. 快速排序過程: 首先任選一個記錄K(通常選第一個記錄)作為樞軸(支點) 附設(shè)兩個指針i和j分別指向第一個記錄和最后一個記錄。(1) 指針j向前搜索逐個記錄與K比較,直到發(fā)現(xiàn)小于K的記錄為止，將其與樞軸記錄互相交換。(2)指針i向后搜索逐個記錄與K比較,直到發(fā)現(xiàn)大于K的記錄為止，將其與樞軸記錄互相交換。(3)重復(fù)(1) (2)直至i=j為止。完成一趟排序，完成一次分割(以K為分界線)，對前后兩個子表按上述原則再分割，直到所有子表的表長不超過1(為空)為止。 1.6.3

21、交換排序 牛牛文庫文檔分享27 39 11 76 96 66 504949 39 66 96 76 11 27 50 i第1次交換(向前,小的與樞軸交換)即27與49交換.第2次交換:(向后,大的與樞軸交換)即66與49換,27 39 66 96 76 11 50i49jj第3次交換:11與49換27 39 11 96 76 66 5049ji27 39 96 76 11 66 5049ji完成一趟排序:初始關(guān)鍵字第4次換:96與49換ijj27 39 11 49 76 96 66 50舉例: 將（49，39，66，96，76, 11，27，50）進(jìn)行一趟快速排序 分析: (取第一個數(shù)49為樞

22、軸,即K=49,空處是樞軸為49) 牛牛文庫文檔分享49 39 66 96 76 11 27 50 27 39 11 49 76 96 66 50一次劃分之后快速排序的全過程初始關(guān)鍵字分別進(jìn)行快速排序11 27 39 50 66 結(jié)束 結(jié)束 結(jié)束 50 66 76 96 結(jié)束 11 27 39 49 50 66 76 96有序序列時效分析: 平均時間復(fù)雜度最佳為O(nlog2n)。 最壞情況時間效率為O(n2)。 牛牛文庫文檔分享基本思想： 每次從待排序的記錄中選出關(guān)鍵字最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。選擇排序種類: 直接選擇排序和堆排序1.直接選擇排序( 以升序為

23、例)首先從所有n個待排序記錄中選擇關(guān)鍵字最小的記錄，與第1個記錄交換(第1遍進(jìn)行n-1次比較)。再從剩下的 n-1個記錄中選出關(guān)鍵字最小的記錄，與第2個記錄交換(第2遍進(jìn)行n-2次比較)。重復(fù)操作進(jìn)行n-1遍，直到待排序序列全部有序為止。1.6.4 選擇排序 牛牛文庫文檔分享1. 直接選擇排序 正序：移動次數(shù)為0逆序：移動次數(shù)為3(n-1)執(zhí)行n(n-1)/2次比較舉例:將（89，21，56，48，85，16，19，47）直接選擇排序原序列 89 21 56 48 85 16 19 47 i=1 16 21 56 48 85 89 19 47 i=2 16 19 56 48 85 89 21

24、47 i=3 16 19 21 48 85 89 56 47 i=4 16 19 21 47 85 89 56 48 i=5 16 19 21 46 48 89 56 85 i=6 16 19 21 46 48 56 89 85 i=7 16 19 21 46 48 56 85 89 最后結(jié)果 進(jìn)行n-1=7次選擇1.6.4 選擇排序 時效分析: 牛牛文庫文檔分享選擇法排序 for (i=0; iN-1; i+) k = i; for (j=i+1; j ak) k = j; if( k!= i) temp=ai; ai=ak; ak=temp; 牛牛文庫文檔分享例初始： 49 38 65 9

25、7 76 13 27 kji=11349一趟： 13 38 65 97 76 49 27 i=22738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj從小到大排序 牛牛文庫文檔分享2.堆排序堆定義：n個元素的序列K1，K2，Kn，當(dāng)且僅當(dāng)滿足下列關(guān) 系時，稱為堆。 kik2i kik2i+1 kik2i kik2i+1 小根堆 或大根堆堆結(jié)構(gòu)(完全二叉樹表示)：將序

26、列對應(yīng)的一維數(shù)組看成一個完全二叉樹。在堆中,堆頂元素必為序列中n個元素的最小值(或最大值)。 小根堆251556103070255630701510 大根堆其中:（i=1，2，n/2）1.6.4 選擇排序 牛牛文庫文檔分享首先包括n個元素的序列建堆,輸出堆頂最小值。得到n個元素中最小元素。然后再對剩下n-1個元素重建堆,輸出堆頂元素。得到n個元素中次小元素。反復(fù)執(zhí)行(直到剩下子序列為空)，便得到一個有序列。2.堆排序排序過程: 兩個問題:實現(xiàn)堆排序需解決 (1)如何將n個元素的無序序列建成一個堆。(2)輸出堆頂元素后，調(diào)整剩余元素成為一個新堆。 輸出堆頂元素后，以堆中最后一個元素代替之。此時根

27、結(jié)點左、右子樹均為堆，僅需自上而下調(diào)整即可。 1.6.4 選擇排序方法：將根結(jié)點與左、右子樹根結(jié)點比較，若不滿足堆條件，則較小值與根結(jié)點交換。順序：從完全二叉樹最后一個非終端結(jié)點(第n/2個元素)開始，直到根結(jié)點(第一個元素)為止，對每一個結(jié)點，調(diào)整建堆。 牛牛文庫文檔分享舉例:一個無序序列(49,39,66,96,76,11,27,50)建小根堆的過程 1. 從第一個非葉子結(jié)點(序號=n/2=8/2=4,即圖中值為96的結(jié)點開始篩選,篩選 原則是保證父結(jié)點的值要小于或等于葉子接點 4939966676112750無序序列4939506676112796第4個結(jié)點96被篩選后狀態(tài)4939501

28、176662796第3個結(jié)點66被篩選后狀態(tài) 4939501176662796第2個結(jié)點39被篩選后狀態(tài) 牛牛文庫文檔分享 目前的堆中,堆頂元素11為最小值,輸出后,重新對n-1個元素重新建一個新堆, 新堆中的堆頂是剩余的n-1個元素中的最小值,n個元素中的次最小值.1139504976662796 49 被篩選后建成的堆11395027766649964939501176662796 第2個結(jié)點篩選完畢該處理第1個結(jié)點 牛牛文庫文檔分享舉例:輸出堆頂元素并建新堆過程 堆113950277666499611與96交換后情形輸出堆頂元素之后,以堆中最后一個元素替代之,此時根結(jié)點的左、右子樹均為堆

29、,僅需自上至下進(jìn)行調(diào)整即可。 1139502776664996113950967666492727與96交換后情形1139504976669627 調(diào)整后新堆,27為新堆中的最小值 牛牛文庫文檔分享 27395049766696輸出27, 用96替代 1111 2796504976663996與39換50964976663911 2796與50換39504976669627 調(diào)整后新堆,27為新堆中的最小值11調(diào)整后新堆,39為新堆中的最小值 牛牛文庫文檔分享繼續(xù)此過程 調(diào)整后新堆,39為新堆中的最小值50964976663911 2739509649766611 27輸出堆頂元素（堆頂元素和

30、樹中最后一個結(jié)點對調(diào)）重建堆（因為除了堆頂?shù)母Y(jié)點，左右子樹已經(jīng)是堆， 自上而下進(jìn)行調(diào)整即可）反復(fù)執(zhí)行直到剩下子序列為空（便得到一個有序列）堆排序的時效分析: 最壞情況下，時間復(fù)雜度為O (nlog2n)。僅需一個記錄大小供交換用的輔助存儲空間，適合規(guī)模較大的線性表。 牛牛文庫文檔分享插入排序交換排序 選擇排序直接插入排序希爾排序冒泡排序快速排序直接選擇排序堆排序適用于n較小情況,或表中每個元素與其最終位置不遠(yuǎn), 記錄本身信息量較大時若適用于數(shù)據(jù)元素初始狀態(tài)基本有序 適用于n較大情況,是目前基于內(nèi)部排序的方法中最好的適用于n較小情況,且記錄本身信息量較大時適用于n較大情況,最壞情況下,比較次數(shù)

31、n(n-1)/2最壞情況下,時間復(fù)雜度是O(n1.5)最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,比較次數(shù)n(n-1)/2最壞情況下,比較次數(shù)n log2n排序小結(jié) 牛牛文庫文檔分享查找與排序補(bǔ)充習(xí)題講解1. 鏈表適用于_查找. A . 順序 B. 二分法 C. 順序,也能二分法 D. 隨機(jī)2. 對長度為n的線性表進(jìn)行順序查找,在最壞情況下所需要 的比較次數(shù)為_. A. log2n B. n/2 C. n D. n+1 （05年4月）3. 已知一個有序表為(13、18、24、35、47、50、62、83、 90、115、134），當(dāng)使用二分法查找90的元素時，查找 成功的比較次數(shù)為_. A. 1 B. 2 C. 3 D. 94. 在排序算法中，兩兩比較待排序的記錄，當(dāng)發(fā)現(xiàn)不滿足 順序要求時，變更他們的相對位置，這就是_排序。 A. 希爾排序 B. 交換排