數(shù)據(jù)結(jié)構(gòu)-排序ppt課件

1、第第1010章章 排序排序一、根本概念一、根本概念排序：將文件中的記錄按照關(guān)鍵字值遞排序：將文件中的記錄按照關(guān)鍵字值遞增或遞減的順序陳列起來。增或遞減的順序陳列起來。排序的穩(wěn)定與不穩(wěn)定：假設(shè)關(guān)鍵字一樣排序的穩(wěn)定與不穩(wěn)定：假設(shè)關(guān)鍵字一樣的記錄在排序后先后順序依然不變，那的記錄在排序后先后順序依然不變，那么稱所用的排序方法是穩(wěn)定的，否那么么稱所用的排序方法是穩(wěn)定的，否那么就是不穩(wěn)定的。就是不穩(wěn)定的。內(nèi)部排序：全部在內(nèi)存中進(jìn)展的排序內(nèi)部排序：全部在內(nèi)存中進(jìn)展的排序外部排序：排序中需運(yùn)用內(nèi)存與外存外部排序：排序中需運(yùn)用內(nèi)存與外存內(nèi)部排序：插入排序，交換排序，選擇內(nèi)部排序：插入排序，交換排序，選擇排序，

2、歸并排序，基數(shù)排序等。排序，歸并排序，基數(shù)排序等。內(nèi)部排序與存儲(chǔ)構(gòu)造：1一維數(shù)組作為存儲(chǔ)構(gòu)造：對(duì)記錄進(jìn)展物理重排；2以鏈表作為存儲(chǔ)構(gòu)造：無須挪動(dòng)記錄，僅需修正指針即可；3建立索引表輔助排序排序算法的評(píng)價(jià)規(guī)范：1時(shí)間；2執(zhí)行算法所需的附加空間；3算法復(fù)雜度。主要是時(shí)間代價(jià)：算法的比較次數(shù)和挪動(dòng)次數(shù)。注：簡(jiǎn)單的排序方法，時(shí)間復(fù)雜度O(n2); 先進(jìn)的排序方法，時(shí)間復(fù)雜度O(nlogn)；基數(shù)排序，時(shí)間復(fù)雜度O(dn)。以數(shù)組作為文件的存儲(chǔ)構(gòu)造#define MAXSIZE 100 typedef struct KeyType key; InfoType otherinfo; RecType; ty

3、pedef struct RecType rMAXSIZE+1;/r0閑置或作為哨兵單元 int length;SqList;如：以某課程考試成果為關(guān)鍵字的排序二、插入排序二、插入排序(Insertion Sort)(Insertion Sort)定義：將待排序記錄分為有序區(qū)和無序定義：將待排序記錄分為有序區(qū)和無序區(qū)，每次將無序區(qū)中的第一個(gè)記錄按其關(guān)鍵區(qū)，每次將無序區(qū)中的第一個(gè)記錄按其關(guān)鍵字值的大小插入到有序區(qū)中的適當(dāng)位置，直字值的大小插入到有序區(qū)中的適當(dāng)位置，直到無序區(qū)記錄全部插入為止。到無序區(qū)記錄全部插入為止。1 1 直接插入排序直接插入排序方法：在插入第方法：在插入第i i個(gè)記錄時(shí)，個(gè)記

4、錄時(shí)，R1,R2,R1,R2,，Ri-1Ri-1已排好序，將關(guān)鍵字已排好序，將關(guān)鍵字kiki依次與關(guān)鍵字依次與關(guān)鍵字ki-ki-1,ki-2, ,k11,ki-2, ,k1進(jìn)展比較，從而找到應(yīng)該進(jìn)展比較，從而找到應(yīng)該插入的位置，然后將記錄插入的位置，然后將記錄RiRi插入。插入。對(duì)R1Rn進(jìn)展排序，R0為監(jiān)視哨 47 33 61 82 72 11 25 47 47 33 61 82 72 11 25 47 33 33 47 61 82 72 11 25 47 /334733 33 47 61 82 72 11 25 4733 33 47 61 82 72 11 25 4772 33 47 61

5、 72 82 11 25 4711 33 47 61 72 8282 25 47 /1182 11 33 47 61 7272 82 25 47 /117211 33 47 6161 72 82 25 47 /1161 11 33 4747 61 72 82 25 47 /114711 3333 47 61 72 82 25 47 /113311 11 33 47 61 72 82 25 47 /終了11的插入排序25 11 25 33 47 61 72 82 47 / 47 11 25 33 47 47 61 72 82 中間過程中間過程算法：void InsertSort(SqList &

6、L) for(i=2;i=L.length;i+) if(L.ri.keyL.ri-1.key)/需將L.ri插入有序子表 L.r0=L.ri; L.ri=L.ri-1; for(j=i-2;L.r0.keyL.rj.key;j-) L.rj+1=L.rj; /記錄后移 L.rj+1=L.r0; /插入到正確位置 時(shí)間復(fù)雜度O(n2)，穩(wěn)定2 2、希爾排序、希爾排序Shells methodShells method“減少增量排序減少增量排序(Diminishing Increment Sort)(Diminishing Increment Sort) 根本思想：先將整個(gè)待排記錄序列分割成為根

7、本思想：先將整個(gè)待排記錄序列分割成為假設(shè)干子序列分別進(jìn)展直接插入排序，待整個(gè)序假設(shè)干子序列分別進(jìn)展直接插入排序，待整個(gè)序列中的記錄列中的記錄“根本有序時(shí)，再對(duì)全體記錄進(jìn)展根本有序時(shí)，再對(duì)全體記錄進(jìn)展一次直接插入排序。一次直接插入排序。 步驟：步驟：對(duì)整個(gè)待排記錄序列，按間隔對(duì)整個(gè)待排記錄序列，按間隔d1d1分組，組內(nèi)排序分組，組內(nèi)排序取取d2 d1d2 0 m0 、Ri+dRi+d* *m m ( i+d( i+d* *m=n )m=n )同組同組void ShellInsert(SqList &L, int dk) for(i=dk+1;i=L.length;i+) if(L.ri.key0

8、&L.r0.keyL.rj.key;j-=dk) L.rj+dk=L.rj; /記錄后移 L.rj+dk=L.r0; /插入到正確位置 void ShellSort(SqList &L, int d, int t) /d為增量序列數(shù)組，t為增量數(shù) for(k=0;k147 33 61 82 72 11假設(shè)中間數(shù)介于47 和11之間，必然減少逆轉(zhuǎn)數(shù)不穩(wěn)定三、選擇排序三、選擇排序Selection SortSelection Sort 根本思想：每一趟在待排序的記錄中選根本思想：每一趟在待排序的記錄中選出關(guān)鍵字最小的記錄，依次放在已排序的記出關(guān)鍵字最小的記錄，依次放在已排序的記錄序列的最后，直至全

9、部記錄排完為止。錄序列的最后，直至全部記錄排完為止。 1. 1. 簡(jiǎn)單項(xiàng)選擇擇排序簡(jiǎn)單項(xiàng)選擇擇排序 第一趟排序：在無序區(qū)第一趟排序：在無序區(qū)R1RnR1Rn中中選出關(guān)鍵字最小的記錄，將它與選出關(guān)鍵字最小的記錄，將它與R1R1交換；交換； 第二趟排序：在無序區(qū)第二趟排序：在無序區(qū)R2RnR2Rn中中選出關(guān)鍵字最小的記錄，將它與選出關(guān)鍵字最小的記錄，將它與R2R2交換；交換； 第第i i趟排序：趟排序： R1Ri-1 R1Ri-1已是有序已是有序區(qū)，在當(dāng)前無序區(qū)區(qū)，在當(dāng)前無序區(qū)RiRnRiRn中選出關(guān)鍵中選出關(guān)鍵字最小的記錄字最小的記錄RkRk，將它與，將它與RiRi交換；交換； 進(jìn)展進(jìn)展n-1n

10、-1趟排序后，整個(gè)文件就是遞趟排序后，整個(gè)文件就是遞增有序的。增有序的。49 38 65 97 76 13 27 4913 38 65 97 76 49 27 4913 27 65 97 76 49 38 4913 27 38 97 76 49 65 4913 27 38 49 76 97 65 4913 27 38 49 49 97 65 7613 27 38 49 49 65 97 7613 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 算法流程：1 for i=1 to n-1 j=i for k=i+1 to n if (RjRk) then

11、 j=k end(k) if(ji) then ri與rj互換End(i)return void SelectSort(SqList &L) int i,j,k; RecType temp; for(i=1;iL.length;i+) j=i; for (k=i+1; kL.rk.key) j = k; if(j i) temp=L.ri; L.ri=L.rj; L.rj=temp; 時(shí)間復(fù)雜度O(n2)，穩(wěn)定堆：n個(gè)元素的序列k1,k2,kn，當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆。時(shí)間復(fù)雜度O(nlogn)，不穩(wěn)定把堆看作一棵完全二叉樹，一切非終端結(jié)點(diǎn)的值均不大于或不少于其左右孩子結(jié)點(diǎn)的值。堆頂

12、元素是堆序列的最小值最大值堆排序：輸出堆頂最小值最大值后，使得剩余的元素序列重又建成一個(gè)堆，得到次小值次大值。如此反復(fù)執(zhí)行得到一個(gè)有序序列的過程。堆排序步驟： 1.從無序序列構(gòu)建初始堆 2.反復(fù)挑選輸出有序序列 第1步其實(shí)也是一個(gè)反復(fù)挑選的過程，因此挑選是堆排序的關(guān)鍵 挑選過程 構(gòu)建初始堆 四、交換排序四、交換排序根本思想：兩兩比較待排序記錄的關(guān)鍵根本思想：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄逆序時(shí)即進(jìn)展交換，直至字，發(fā)現(xiàn)兩個(gè)記錄逆序時(shí)即進(jìn)展交換，直至沒有逆序的記錄為止。沒有逆序的記錄為止。1 1 起泡排序起泡排序Bubble methodBubble method根本思想：經(jīng)過對(duì)相鄰關(guān)鍵

13、字的比較和交根本思想：經(jīng)過對(duì)相鄰關(guān)鍵字的比較和交換，使全部記錄陳列有序。換，使全部記錄陳列有序。過程：每?jī)蓚€(gè)相鄰的關(guān)鍵字進(jìn)展比較，假過程：每?jī)蓚€(gè)相鄰的關(guān)鍵字進(jìn)展比較，假設(shè)為逆序，那么將兩記錄交換位置，反復(fù)設(shè)為逆序，那么將兩記錄交換位置，反復(fù)進(jìn)展這一操作。如此一趟排序后，可將關(guān)進(jìn)展這一操作。如此一趟排序后，可將關(guān)鍵字最大的記錄安排在最后一個(gè)記錄的位鍵字最大的記錄安排在最后一個(gè)記錄的位置上，然后對(duì)前置上，然后對(duì)前n-1n-1個(gè)記錄反復(fù)同樣操作，個(gè)記錄反復(fù)同樣操作，再將次小關(guān)鍵字安排再倒數(shù)第二個(gè)記錄的再將次小關(guān)鍵字安排再倒數(shù)第二個(gè)記錄的位置上。反復(fù)進(jìn)展，直至某一趟沒有記錄位置上。反復(fù)進(jìn)展，直至某一趟

14、沒有記錄交換完成排序。交換完成排序。473361827211254733476172112547823347611125477282334711254761728233112547476172821125334747617282112533474761728211253347476172821125334747617282設(shè)置指示變量，以判別每次掃描時(shí)能否有記錄交換 void BubbleSort(SqList &L) int i, j, flag; RecType temp; for (i=L.length; i1; i-) flag = TRUE; for(j=1; jL.rj+1.key

15、) temp=L.rj+1; L.rj+1=L.rj; L.rj=temp; flag=FALSE; if (flag) break; 時(shí)間復(fù)雜度O(n2)，穩(wěn)定2 2 快速排序快速排序Quick SortQuick Sort根本思想：經(jīng)過一趟排序?qū)⒃杏涗浄殖蓛筛舅枷耄航?jīng)過一趟排序?qū)⒃杏涗浄殖蓛刹糠?，然后分別對(duì)這兩部分進(jìn)展排序以到達(dá)最后部分，然后分別對(duì)這兩部分進(jìn)展排序以到達(dá)最后一切記錄有序。即在當(dāng)前無序子區(qū)一切記錄有序。即在當(dāng)前無序子區(qū)R1RhR1Rh中任中任取一個(gè)記錄作為比較的基準(zhǔn)，用此基準(zhǔn)將當(dāng)前無取一個(gè)記錄作為比較的基準(zhǔn)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序子區(qū)：序區(qū)劃分為左

16、右兩個(gè)較小的無序子區(qū)： R1Ri-1R1Ri-1和和Ri+1RhRi+1Rh，左邊無序子區(qū)記錄，左邊無序子區(qū)記錄關(guān)鍵字均小于或等于基準(zhǔn)關(guān)鍵字，右邊那么大于關(guān)鍵字均小于或等于基準(zhǔn)關(guān)鍵字，右邊那么大于或等于基準(zhǔn)關(guān)鍵字。反復(fù)進(jìn)展，直至無序子區(qū)記或等于基準(zhǔn)關(guān)鍵字。反復(fù)進(jìn)展，直至無序子區(qū)記錄已排好序?yàn)橹?。錄已排好序?yàn)橹埂?對(duì)當(dāng)前無序子區(qū)對(duì)當(dāng)前無序子區(qū)R1Rh進(jìn)展劃分的方法：設(shè)進(jìn)展劃分的方法：設(shè)置兩個(gè)指示器置兩個(gè)指示器i和和j，它們的初值分別為：，它們的初值分別為：i=1,j=h。設(shè)基準(zhǔn)設(shè)基準(zhǔn)temp為無序子區(qū)中的第一個(gè)記錄為無序子區(qū)中的第一個(gè)記錄Ri(即即R1)。將。將j自自h起向左掃描，直至找到第一個(gè)

17、關(guān)鍵起向左掃描，直至找到第一個(gè)關(guān)鍵字小于字小于temp.key的記錄的記錄Rj，將，將Rj移至移至i所指的位所指的位置上；然后，令置上；然后，令i自自i+1起向右掃描，直至找到第一起向右掃描，直至找到第一個(gè)關(guān)鍵字大于個(gè)關(guān)鍵字大于temp.key的記錄的記錄Ri，將，將Ri移至移至j所所指的位置上；接著令指的位置上；接著令j自自j-1起向左掃描，如此交替起向左掃描，如此交替改動(dòng)掃描方向，從兩端各自往中間靠攏，直至改動(dòng)掃描方向，從兩端各自往中間靠攏，直至i=j時(shí)，時(shí)，i便是基準(zhǔn)便是基準(zhǔn)x的最終位置，將的最終位置，將x放在此位置上就放在此位置上就完成了一次劃分。完成了一次劃分。O(nlogn)，不穩(wěn)

18、定49 38 65 97 76 13 27 49ij49 38 65 97 76 13 27 49ij27 38 65 97 76 13 49 49ij27 38 65 97 76 13 49 49ij27 38 49 97 76 13 65 49ij49 38 65 97 76 13 27 49ij49 38 65 97 76 13 27 49ij27 38 65 97 76 13 49ij27 38 65 97 76 13 49ij27 38 97 76 13 65 49ij/一趟快速排序int partition( SqList& L,int low,int high)L.r0 = L.rlo