計(jì)算機(jī)應(yīng)用基礎(chǔ)課件16排序

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

2、據(jù)項(xiàng)組成的記錄。此時(shí)排序應(yīng)按照關(guān)鍵字的大小進(jìn)行。所謂關(guān)鍵字是指記錄中的某個(gè)數(shù)據(jù)項(xiàng)，用它可以標(biāo)識一個(gè)記錄。若此關(guān)鍵字可以唯一地標(biāo)識一個(gè)記錄，則稱此關(guān)鍵字為主關(guān)鍵字；反之，把用以識別若干記錄的關(guān)鍵字稱為次關(guān)鍵字。,排序的穩(wěn)定性：在待排序的記錄中，若存在多個(gè)關(guān)鍵在相同 的記錄，經(jīng)過排序后，這些具有相同關(guān)鍵在 的記錄之間的相對次序發(fā)生變化，則稱這種 排序方法是穩(wěn)定的；否則，是不穩(wěn)定的。 排序的分類：內(nèi)部排序與外部排序 內(nèi)部排序:整個(gè)排序過程完全在內(nèi)存中進(jìn)行. 外部排序:由于待排序記錄數(shù)據(jù)量太大,內(nèi)存無法容納 全部數(shù)據(jù),排序需要借助外部存儲設(shè)備才能 完成. 排序算法評價(jià)： 算法執(zhí)行時(shí)間(最好、最差及平均

3、情況)、需要附加空間大小,1.6 排序,插入排序的基本思想：,1.6.2 插入排序,插入排序三種方法 1. 直接排序: 認(rèn)可第1個(gè)記錄已排好序，然后將第2個(gè)到第n個(gè)記錄依次插入到前面已排好序的記錄組成的文件中。 2.折半插入排序: 折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。 3.希爾排序: 將整個(gè)無序序列分割成若干個(gè)子序列分別進(jìn)行直接插入排序.,將待排序文件中的記錄，逐個(gè)按其排序碼值的大小插入到已排好序的若干個(gè)記錄組成的文件中的適當(dāng)位置，保持新文件有序。,1.直接插入排序: 思路：認(rèn)可第1個(gè)記錄已排好序，然后將第2個(gè)到第n個(gè)記

4、錄依次插入到前面已排好序的記錄組成的文件中。 具體過程(第i個(gè)記錄Ri插入到前面i-1個(gè)已排好序的記錄中) 將Ri的排序碼與前面已排好序的排序碼從右向左依次比較，找到Ri應(yīng)插入的位置；將該位置以后直到Ri-1各記錄順序后移,空出位置插入Ri。,1.6.2 插入排序,直接插入排序:,次數(shù)i r0 r1 r2 r3 r4 r5 r6 r7 r8 (49) 39 66 96 76 11 37 50,(39 49) 66 96 76 11 37 50,i=2,39,(39 49 66) 96 76 11 37 50,i=3,66,(39 49 66 96) 76 11 37 50,i=4,96,(39

5、 49 66 76 96) 11 37 50,i=5,76,(11 39 49 66 76 96) 37 50,i=6,11,(11 37 39 49 66 76 96) 50,i=7,37,(11 37 39 49 50 66 76 96),i=8,50,對于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次,. /*對N個(gè)整數(shù)進(jìn)行升序排序*/ for(i=1;i=0; k-) /尋找插入位置if(aiak) break; /插入到第k個(gè)位置的后面 temp=ai; for(j=i-1;jk; j-) /向后移動(dòng) aj+1=aj; aj+1=temp; ,. /*改進(jìn)前面的算法*/ for(i

6、=1;i=0 ,tempaj,若降序排序，則：,1.直接插入排序: 時(shí)效分析,最好情況:初始排序碼已經(jīng)有序。共比較n-1次，移動(dòng)0次。,最壞情況:待排序序列完全逆序。比較和移動(dòng)均為n(n-1)/2次。,平均情況:比較和移動(dòng)次數(shù)均約為n2/4，時(shí)間復(fù)雜度為O(n2)。,1.6.2 插入排序,該算法適合于n 較小的情況，時(shí)間復(fù)雜度為O(n2).,2、折半插入排序 折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。,折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變，其時(shí)間復(fù)雜度與直接插入排序相同為O(n2)。,1.6.2 插入排序,

7、3 .希爾排序,基本思想：將整個(gè)無序序列分割成若干個(gè)子序列分別進(jìn) 行直接插入排序,待整個(gè)序列中的記錄”基本 有序”時(shí),再對全體記錄進(jìn)行一次直接插入排序。 子序列分割：選定兩個(gè)元素之間距離h，將所有間隔為h的元素 分成一組(將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子系列),具體實(shí)現(xiàn):,(1)選擇一個(gè)增量序列t1 ，t2， ，tk,其中ti tj, tk=1。 (2)按增量序列個(gè)數(shù)k，對序列進(jìn)行k趟排序。 (3)每趟排序，根據(jù)對應(yīng)的增量ti，將序列分割成若干長度為m的子序列，分別對各子表直接插入排序。增量ti逐次減小， tk=1時(shí)，再對全部元素進(jìn)行一次直接插入排序即可完成。,1.6.2 插入排序,舉例: 有

8、一個(gè)含有14個(gè)數(shù)的序列,使用希而排序進(jìn)行升序排序 ( 39,80,76,41,13,29,50,78,30,11,100,7,41,86 ) 取增量：5，3，1,h=5,39 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，41，41，30，86，13，11,R1, R2, R3, R4, R5,

9、R6, R7, R8, R9, R10 R11, R12, R13, R14,h=5,39 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，11,R1, 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 39 50 76 41 13 100 80 78 86,對每個(gè)序列進(jìn)行直接插入排

10、序:,h=3,29 7 41 30 11 39 50 76 41 13 100 80 78 86,29 30 50 13 78,7 11 76 100 86,41 39 41 80,分別對以上3個(gè)子序列,即 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 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14,13 2

11、9 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 100,h=1 序列基本有序，對其進(jìn)行直接插入排序, 第三趟最終結(jié)果：,7 11 13 29 30 39 41 41 50 76 78 80 86 100,第二趟最終結(jié)果：,3 .希爾排序,特點(diǎn)：每一遍以不同間隔距離插入排序。h較大時(shí)移動(dòng)數(shù)據(jù)元素是跳躍式進(jìn)行。子序列每一次比較可能移去多個(gè)逆序(直接插入排序每次比較只能移去一個(gè))。效率較高。最后一次排序(h=1)時(shí)，已基本有序，不需要多少移動(dòng)。故其時(shí)間復(fù)雜度較直接

12、插入排序低。 數(shù)學(xué)難題： 如何選取增量序列才能有最好的排序效果，至今未完整解決。但注意：增量序列中除1外沒有公因子，且最后一個(gè)增量序列必須為1。 時(shí)效分析: 很難。比較次數(shù)與移動(dòng)次數(shù)依賴于增量序列的選取，特定情況下可以估計(jì).,1.6.2 插入排序,對待排序記錄兩兩比較排序碼，不滿足排序順序則交換。直到任何兩個(gè)記錄排序碼滿足排序要求。,基本思路,交換排序種類:,冒泡排序 快速排序,1.6.3 交換排序,1. 冒泡排序 基本思想：通過相鄰元素的交換，逐步將線性表變成有序。 基本過程： 第一趟冒泡排序：首先第一個(gè)元素與第二個(gè)元素比較，逆序則 交換；然后第二個(gè)元素與第三個(gè)元素比較；直到第n-1個(gè)元素與

13、第n個(gè)元素比較為止。結(jié)果（關(guān)鍵字）最大的元素放在最后位置。 第二趟冒泡排序：對前面n-1個(gè)元素進(jìn)行相同操作，結(jié)果 次大元素放在n-1位置上。 第i趟冒泡排序：對前面n-i+1個(gè)元素進(jìn)行相同操作，結(jié) 果(n-i+1)中最大元素放在(n-i+1)位置上。,趟數(shù)： 最多n-1,結(jié)束條件： 在某一趟排序中沒有進(jìn)行交換元素操作。,1.6.3 交換排序,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,思想：小的浮起， 大的沉底。,舉例:將數(shù)列 ( 8,

14、 6, 5, 7, 1 ) 升序排序,初始 8 6 5 7 1,第一趟 6 5 7 1 8,第二趟 5 6 1 7 8,第三趟 5 1 6 7 8,第四趟 1 5 6 7 8,初始已排好序(正序最好)，則只需進(jìn)行一趟排序,比較次數(shù)n-1，移動(dòng)次數(shù)為0。 逆序(最壞)，則需進(jìn)行n-1趟排序, 比較次數(shù)為(1+2+3+n-1)=n(n-1)/2。 是穩(wěn)定的排序,時(shí)間復(fù)雜度為O(n2 ),空間復(fù)雜度是O(1) .,時(shí)效分析:,程序代碼:,#define N 5 int gradeN,temp; for(i=0;i gradej+1) temp = gradej+1; gradej+1 = grade

15、j; gradej = temp; ,讀入5個(gè)值保存在數(shù)組中,16,71,46,90,85,temp=46,temp=71,temp=16,16,71,46,90,85,i=0 第1趟,j=0 從頭開始比較,j4,條件不成立,j=1,j4,條件成立,90,46,j=2,j4,條件成立,90,71,j=3,j4,90,16,j=4,內(nèi)層循環(huán)終止,90,即：i=0 第1趟 時(shí) grade0 和grade1比較 grade1 和grade2比較 grade2 和grade3比較 grade3 和grade4比較 最大值放到grade4中,#define N 5 for(i=0; i gradej+1

16、) temp = gradej+1; gradej+1 = gradej; gradej = temp; ,即，i=0 第1趟 時(shí) 內(nèi)存循環(huán) for(j=0; jN-1-i; j+) 變量j是從0到3的,16,71,46,90,85,i=1 第2趟,j=0 從頭開始比較,90,46,90,71,90,16,90,#define N 5 for(i=0; i 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比較 grade

17、1 和grade2比較 grade2 和grade3比較 找出次大值放到grade3中,16,71,46,90,85,i=1 第2趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,#define N 5 for(i=0; i gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; ,16,71,46,85,i=2 第3趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,71,71,16,#define N 5 for(i=0; i gradej+1) te

18、mp = gradej+1; gradej+1 = gradej; gradej = temp; ,16,71,46,85,i=3 第4趟,90,46,90,71,90,16,90,85,46,85,71,85,16,85,71,71,16,#define N 5 for(i=0; i gradej+1) temp = gradej+1; gradej+1 = gradej; gradej = temp; ,46,16,46,2. 快速排序,基本思想： 通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再對前、后兩部分待排記錄重復(fù)上述過程，直到所有子表表

19、長不超過1為止。,優(yōu)點(diǎn)： 通過兩個(gè)不相鄰元素交換，可以一次交換消除多個(gè)逆序，加快排序速度。,49 39 66 96 76 11 27 50,27 39 11 49 76 96 66 50 ,27 39 49 50 66 76 96,1.6.3 交換排序,2. 快速排序,過程:,首先任選一個(gè)記錄K(通常選第一個(gè)記錄)作為樞軸(支點(diǎn)) 附設(shè)兩個(gè)指針i和j分別指向第一個(gè)記錄和最后一個(gè)記錄。 (1) 指針j向前搜索逐個(gè)記錄與K比較,直到發(fā)現(xiàn)小于K的記錄為止，將其與樞軸記錄互相交換。 (2)指針i向后搜索逐個(gè)記錄與K比較,直到發(fā)現(xiàn)大于K的記錄為止，將其與樞軸記錄互相交換。 (3)重復(fù)(1) (2)直至i

20、=j為止。完成一趟排序，完成一次分割(以K為分界線)，對前后兩個(gè)子表按上述原則再分割，直到所有子表的表長不超過1(為空)為止。,1.6.3 交換排序,49 39 66 96 76 11 27 50,第1次交換(向前,小的與樞軸交換)即27與49交換.,第2次交換:(向后,大的與樞軸交換)即66與49換,第3次交換:11與49換,完成一趟排序:,初始關(guān)鍵字,第4次換:96與49換,27 39 11 49 76 96 66 50,舉例: 將（49，39，66，96，76, 11，27，50）進(jìn)行一趟快速排序 分析: (取第一個(gè)數(shù)49為樞軸,即K=49,空處是樞軸為49),49 39 66 96 7

21、6 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,有序序列,時(shí)效分析: 平均時(shí)間復(fù)雜度最佳為O(nlog2n)。 最壞情況時(shí)間效率為O(n2)。,基本思想： 每次從待排序的記錄中選出關(guān)鍵字最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。 選擇排序種類: 直接選擇排序和堆排序,1.直接選擇排序( 以升序?yàn)槔? 首先從所有n個(gè)待排序記錄中選擇關(guān)鍵字最小的記錄，與第1個(gè)記錄交換(第

22、1遍進(jìn)行n-1次比較)。 再從剩下的 n-1個(gè)記錄中選出關(guān)鍵字最小的記錄，與第2個(gè)記錄交換(第2遍進(jìn)行n-2次比較)。 重復(fù)操作進(jìn)行n-1遍，直到待排序序列全部有序?yàn)橹埂?1.6.4 選擇排序,1. 直接選擇排序,正序：移動(dòng)次數(shù)為0 逆序：移動(dòng)次數(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,最后結(jié)果 進(jìn)行n-1=7次選擇,1.6.4 選擇排序,時(shí)效分析:,選擇法排序 for (i=0; i ak) k = j; if( k!= i) temp=ai; ai=ak; a

23、k=temp; ,例,初始： 49 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,從小到大排序,2.堆排序 堆定義：n個(gè)元素的序列K1，K2，Kn，當(dāng)且僅當(dāng)滿足下列關(guān) 系時(shí)，稱為堆。,kik2i kik2i+1,kik2i kik2i+1,小根堆 或,大根堆,堆結(jié)構(gòu)(完全二叉樹表示)：將序列對應(yīng)的一維數(shù)組看成一個(gè)完全二叉樹。,在堆中,堆頂元素必為序列中n個(gè)元素的最小值(或最大值)。,小根堆,大根堆,其中:（i=1，2，n/2）,1.6.4 選擇排序,首先包括n

24、個(gè)元素的序列建堆,輸出堆頂最小值。得到n個(gè) 元素中最小元素。 然后再對剩下n-1個(gè)元素重建堆,輸出堆頂元素。得到n個(gè) 元素中次小元素。 反復(fù)執(zhí)行(直到剩下子序列為空)，便得到一個(gè)有序列。,2.堆排序,排序過程:,兩個(gè)問題:實(shí)現(xiàn)堆排序需解決,(1)如何將n個(gè)元素的無序序列建成一個(gè)堆。,(2)輸出堆頂元素后，調(diào)整剩余元素成為一個(gè)新堆。,輸出堆頂元素后，以堆中最后一個(gè)元素代替之。此時(shí)根結(jié)點(diǎn)左、右子樹均為堆，僅需自上而下調(diào)整即可。,1.6.4 選擇排序,方法：將根結(jié)點(diǎn)與左、右子樹根結(jié)點(diǎn)比較，若不滿足堆條件，則較小值與根結(jié)點(diǎn)交換。 順序：從完全二叉樹最后一個(gè)非終端結(jié)點(diǎn)(第n/2個(gè)元素)開始，直到根結(jié)點(diǎn)(

25、第一個(gè)元素)為止，對每一個(gè)結(jié)點(diǎn)，調(diào)整建堆。,舉例:一個(gè)無序序列(49,39,66,96,76,11,27,50)建小根堆的過程 1. 從第一個(gè)非葉子結(jié)點(diǎn)(序號=n/2=8/2=4,即圖中值為96的結(jié)點(diǎn)開始篩選,篩選 原則是保證父結(jié)點(diǎn)的值要小于或等于葉子接點(diǎn),第4個(gè)結(jié)點(diǎn)96被篩選后狀態(tài),第3個(gè)結(jié)點(diǎn)66被篩選后狀態(tài),目前的堆中,堆頂元素11為最小值,輸出后,重新對n-1個(gè)元素重新建一個(gè)新堆, 新堆中的堆頂是剩余的n-1個(gè)元素中的最小值,n個(gè)元素中的次最小值.,49 被篩選后建成的堆,該處理第1個(gè)結(jié)點(diǎn),舉例:輸出堆頂元素并建新堆過程,堆,11,11與96交換后情形,輸出堆頂元素之后,以堆中最后一個(gè)元

26、素替代之,此時(shí)根結(jié)點(diǎn)的左、右子樹均為堆,僅需自上至下進(jìn)行調(diào)整即可。,11,27與96交換后情形,11,調(diào)整后新堆,27為新堆中的最小值,27,輸出27, 用96替代,11,96與39換,11,27,96與50換,調(diào)整后新堆,27為新堆中的最小值,11,調(diào)整后新堆,39為新堆中的最小值,繼續(xù)此過程,調(diào)整后新堆,39為新堆中的最小值,11,27,39,11,27,輸出堆頂元素（堆頂元素和樹中最后一個(gè)結(jié)點(diǎn)對調(diào)） 重建堆（因?yàn)槌硕秧數(shù)母Y(jié)點(diǎn)，左右子樹已經(jīng)是堆， 自上而下進(jìn)行調(diào)整即可） 反復(fù)執(zhí)行 直到剩下子序列為空（便得到一個(gè)有序列）,堆排序的時(shí)效分析: 最壞情況下，時(shí)間復(fù)雜度為O (nlog2n)。

27、僅需一個(gè)記錄大小供交換用的輔助存儲空間，適合規(guī)模較大的線性表。,排序小結(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. 已知一個(gè)有序表為(13、18、24、35、47、50、62、83、 90、115、134），當(dāng)使用二分法查找90的元素時(shí)，查找 成功的比較次數(shù)為_. A. 1 B. 2 C. 3 D. 9 4. 在排序算法中，兩兩比較待排序的記錄，當(dāng)發(fā)現(xiàn)不滿足 順序要求時(shí)，變更他們的相對位置，這就是_排序。 A. 希爾排序 B. 交換排序 C. 插入排序 D. 選擇排序,ACBB,5. 設(shè)待排序關(guān)鍵碼序列為（33、18、9、25、67、82、53、 95、12、70），要按關(guān)鍵碼值遞增的順序排序，采取以 第一個(gè)關(guān)鍵碼為分界元素的快速排序法，第一趟排