數(shù)據(jù)結(jié)構(gòu)授課教案-第9章內(nèi)部排序.doc

山東輕工業(yè)學(xué)院教師授課教案課程名稱：數(shù)據(jù)結(jié)構(gòu)（計科）課程代碼：0301306學(xué) 分：4.5課程類別：必修開課單位:信息科學(xué)與技術(shù)學(xué)院授課班級：授課教師：楊春花 山東輕工業(yè)學(xué)院教務(wù)處制授課時間年 月 日 星期 第 節(jié)年 月 日 星期 第 節(jié)年 月 日 星期 第 節(jié)授課內(nèi)容概要第九章 內(nèi)部排序第一節(jié) 概述排序的定義、穩(wěn)定性、分類和排序表的存儲結(jié)構(gòu)表示。第二節(jié) 插入排序直接插入排序的思想、算法和分析；希爾排序的思想、算法和分析。第三節(jié) 交換排序冒泡排序的思想、算法和分析；快速排序的思想、算法和分析。第四節(jié) 選擇排序簡單選擇排序的思想、算法和分析；樹形選擇排序的思想；堆的定義、篩選法建堆的過程、堆排序的算法和分析。第五節(jié) 歸并排序歸并排序的思想、算法和分析。第六節(jié) 基數(shù)排序多關(guān)鍵字排序和鏈?zhǔn)交鶖?shù)排序。第七節(jié) 各種內(nèi)部排序方法的比較討論各種內(nèi)部排序方法的比較，內(nèi)部排序的時間復(fù)雜度的下界。目的要求目的： 掌握內(nèi)部排序的基本方法基本要求：理解二路歸并排序、堆排序、基數(shù)排序的思想和算法，理解各種排序方法的特點；掌握排序的基本概念，掌握直接插入排序、希爾排序、簡單選擇排序、冒泡排序、快速排序的思想和算法。重 點希爾排序、冒泡排序、堆排序、快速排序、二路歸并排序和基數(shù)排序。難點堆排序、快速排序、二路歸并排序和基數(shù)排序。作業(yè)布置習(xí)題10參考書1. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版), 嚴(yán)蔚敏，清華大學(xué)出版社，2002。3. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語言描述，(美)Sartaj Sahni著，汪詩林等譯，機械工業(yè)出版社，2002。課 型理論課學(xué)時分配復(fù) 習(xí) 分鐘主要教具投影、黑板講 授 分鐘教學(xué)方法講解、提問、示例指 導(dǎo) 分鐘教學(xué)手段板書、課件總 結(jié) 分鐘備注共8學(xué)時，其中2學(xué)時為習(xí)題課注：課型一欄填寫理論課、實驗課、習(xí)題課等授 課 內(nèi) 容備 注第10章 排序10.1 概述為了便于查找，通常希望計算機中的數(shù)據(jù)表是按關(guān)鍵碼有序的。如有序表的折半查找，查找效率較高。還有，二叉排序樹、B-樹和B+樹的構(gòu)造過程就是一個排序過程。排序(sorting)是計算機程序設(shè)計中的一種重要操作，其功能是對一個數(shù)據(jù)元素集合或序列重新排列成一個按關(guān)鍵碼有序的序列。1.排序的定義（1）排序的定義：設(shè)R1, R2, , Rn是由n個記錄組成的文件，K1, K2, , Kn是排序碼集合，所謂排序是將記錄按排序碼遞增（或遞減）的排列。排序碼可以是主關(guān)鍵碼，也可以是次關(guān)鍵碼。（2）穩(wěn)定性假設(shè)Ki=Kj(1i,j n,ij)，且在排序前的序列中Ri領(lǐng)先于Rj(即ij)，若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的，否則是不穩(wěn)定的。（3）排序的分類：待排序的記錄在排序過程中全部存放在內(nèi)存的稱為內(nèi)排序，如果排序過程中需要使用外存的稱為外排序。 按排序原則，排序分為： 插入排序； 選擇排序； 交換排序 分配排序 歸并排序 外部排序 按排序所需的工作量，排序分為： 簡單排序方法，其時間復(fù)雜度為O(n2)； 先進(jìn)的排序方法，其時間復(fù)雜度為O(nlogn)； 基數(shù)排序，其時間復(fù)雜度為O(dn)；（4）排序中的基本操作： 比較關(guān)鍵碼大小 移動記錄（5）對于待排序的記錄序列，有三種常見的存儲表示方法。 向量結(jié)構(gòu)，即將待排序的記錄存放在一組地址連續(xù)的存儲單元中。 鏈表結(jié)構(gòu)。 記錄向量與地址向量結(jié)合，即將待排序記錄存放在一組地址連續(xù)的存儲單元中，同時另設(shè)一個指示各個記錄位置的地址向量。 為簡單起見，數(shù)據(jù)的存儲結(jié)構(gòu)采取向量的存儲結(jié)構(gòu)：#define n 20 /記錄數(shù)typedef int keytype;typedef struct keytype key; datatype other; rectype; rectype rn+1; （6）排序算法的評價： 算法的執(zhí)行時間 算法執(zhí)行時所需的附加空間10.2插入排序基本原理：每步將一個待排序的對象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對象適當(dāng)位置上，直到對象全部插入為止。10.2.1直接插入排序1直接插入排序的基本思想先假定第1個記錄為有序序列，然后從第2條記錄開始，依次將記錄插入到前面已經(jīng)有序的序列中，直至全部記錄有序。一般情況下，第i趟直接插入排序：將ri插入到已經(jīng)有序的序列r1.i-1中，使其變成有序序列r1.i。整個排序進(jìn)行n-1趟插入。2示例：初始：49 38 65 97 76 13 27 493算法：void InsertSort( rectype R,int n) int i,j; for (i=2;in;i+) R0Ri; for (ji-1; R0.keyRj.key;j-) Rj+1 Rj; Rj+1 R0 4算法分析： 空間效率：只需要一個記錄的輔助空間。 時間效率：比較記錄的次數(shù)為： 最?。簄-1次；最大:(n+2)(n-1)/2次移動記錄的次數(shù)：最小：2(n-1) 最大:(n+4)(n-1)/2平均情況：O(n2)10.2.2折半插入排序1、折半插入排序：將直接插入排序的查找過程改用折半查找。由此實現(xiàn)的排序稱為二分法插入排序。10.2.3希爾排序(Shells Sort)1、希爾排序：shell排序又稱縮小增量排序(Diminishing Increment Sort)。先將整個待排記錄序列分割成若干個子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序“時，再對全體記錄進(jìn)行一次直接插入排序，就可以完成整個的排序工作。利用下面兩點：當(dāng)n很小時，直接插入排序的效率較高；當(dāng)待排記錄序列基本有序時，直接插入排序的效率也較高。shell排序?qū)χ苯硬迦肱判蛩惴ㄟM(jìn)行改進(jìn)。例：原始序列 49 38 65 97 13 76 27 49void shellSort(rectype r,int n,int d,int k) for (l=0;lk;l+) dkdl;for (i=dk+1;i0&Rj.keyr0.key);j-=dk) rj+dkrj;Rj+dkr0; 2、算法分析：Shell排序的平均比較次數(shù)和平均移動次數(shù)都為O(n1.3)左右Shell排序算法中增加了一個輔助空間。Shell排序是不穩(wěn)定的。 10.3 交換排序交換排序基本思想：兩兩比較待排序記錄的排序碼，交換不滿足排序要求的偶對，直到全部有序。10.3.1冒泡排序(Bubble Sort)1、基本思想：設(shè)待排序記錄順序存放在R1,R2,R3,Rn中:依次比較（R1,R2），（ R2,R3）, (Rn-1,Rn),不滿足順序則交換，結(jié)果，最大者在Rn中。這叫一次起泡。此后，再對存放在R1,R2,R3,Rn-1中n-1個記錄作同樣處理,結(jié)果，最大者在Rn-1中。 。 n-1次起泡能完成排序。設(shè)置標(biāo)志noswap表示本次起泡是否有交換，若無交換，表示排序完成。2、示例：3、算法：void bubbleSort(rectypeR,int n) i=1;flag=1;for (i=1;in & flag;i+)flag0;for (j=1;jRj+1.key) tempRj+1; Rj+1=Rj; Rjtemp; flag1;4、算法分析：起泡排序的最壞時間復(fù)雜度為O(n2)，平均時間復(fù)雜度為O(n2)。起泡排序算法中增加一個輔助空間temp，輔助空間為S(n)=O(1)。起泡排序是穩(wěn)定的。10.3.2快速排序(Quick Sort)1、基本思想：快速排序的基本思想是：從待排序記錄序列中選取一個記錄（通常選取第一個記錄）作為“樞軸”，通過一趟排序（一次劃分）將待排記錄分割成獨立的兩部分，其中一部分記錄的關(guān)鍵字比樞軸小，另一部分記錄的關(guān)鍵字比樞軸大。然后則可分別對這兩部分記錄繼續(xù)進(jìn)行劃分，以達(dá)到整個序列有序。1、基本思想：一趟快速排序（一次劃分）的具體做法是：附設(shè)兩個指針low和high,它們的初值分別是一個序列的第一個和最后一個記錄的位置，設(shè)樞軸記錄的關(guān)鍵字為pivotKey，在首先從high所指位置起向前搜索直到第一個關(guān)鍵字小于pivotKey的記錄和樞軸記錄交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大于pivotKey的記錄和樞軸記錄互相交換，重復(fù)交替這兩步直到low=high為止。2、示例： 設(shè)記錄的關(guān)鍵碼序列為： 49 38 65 97 76 13 27 49對其進(jìn)行快速排序。3、算法：int Partition(rectypeR,int n, int low,int high) pivotkey=Rlow.key;while(lowhigh)while( (low=pivotkey) -high;rlow=rhigh; while( (lowhigh)&(Rlow.key=pivotkey) +low;rhigh=rlow;rlow=pivotkey;return low;void QSort(rectype R,int n, int low,int high) if (lowhigh) pivotloc=Partition(R,n,low,high);QSort(R,low, pivotloc-1);QSort(R, pivotloc+1,high);void QuickSort(rectype R,int n) QSort(R,n,1,n);4、算法分析：最壞情況下，即當(dāng)初始序列已經(jīng)有序時，快速排序退化為起泡排序，為O(n2)。最好時間復(fù)雜度為O(nlog2n)。平均時間復(fù)雜度是T(n)=O(nlog2n)。算法需要一個棧空間實現(xiàn)遞歸。棧的大小取決于遞歸調(diào)用的深度，最多不超過n，理想情況下不超過log2n。所以快速排序的輔助空間最壞為S(n)=O(n)，最好為S(n)=O(log2n) ?？焖倥判蚴遣环€(wěn)定的。10.4選擇排序選擇排序（Selection Sort）的基本思想是：每一趟在n-i+1（i=1，2，n-1）個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。 10.4.1簡單選擇排序 (Simple Selection Sort)1、基本思想：第i趟簡單選擇排序是指通過n-i次關(guān)鍵字的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄進(jìn)行交換。共需進(jìn)行i-1趟比較，直到所有記錄排序完成為止。 2、示例：3、算法：void SelectSort(rectype R ,int n) for (i=1;i=n-1;i+) k=i;for (j=i+1;j=n;j+)if (Rj.keyRk.key) k=j;if (k!=i) temp=Ri;Ri=Rk;Rk=temp;4、算法分析：直接選擇排序的比較次數(shù)與文件初始狀態(tài)無關(guān)。直接選擇排序的時間復(fù)雜度： 移動：最好：0 最壞：3（n-1) 比較：n(n-1)/2 總的時間復(fù)雜度：O(n2)穩(wěn)定性：不穩(wěn)定10.4.2樹形選擇排序 (Tree Selection Sort)1 基本思想：簡單選擇排序的主要操作是比較，要提高它的速度必須減少比較的次數(shù)。而實際上如果能利用以前的比較結(jié)果則可以提高排序速度。樹形選擇排序(Tree Selection Sort)，又稱錦標(biāo)賽排序(Tournament sort),其方法是：首先對n個記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在n/2個較小者之間再進(jìn)行兩兩比較，如此重復(fù)直到選出最小關(guān)鍵字的記錄為止。然后對剩下的記錄作同樣的操作，選出具有次小關(guān)鍵字的記錄。這個過程可以用一個完全二叉樹來表示。2 示例：3 算法分析：在樹型選擇排序中，含有n個葉子節(jié)點的完全二叉樹的深度為log2n+1，則在樹型選擇排序中，每選擇一個小關(guān)鍵字需要進(jìn)行 log2n 次比較，因此其時間復(fù)雜度為O(nlog2n)。移動記錄次數(shù)不超過比較次數(shù)，故總的算法時間復(fù)雜度為O(nlog2n)。缺點是使用了較多的輔助空間（n-1），并且和“最大值”進(jìn)行了多余的比較。10.4.3堆排序 (Heap Sort)1 堆的定義：堆排序是對樹型選擇排序的進(jìn)一步改進(jìn)。采用堆排序時，只需要一個記錄大小的輔助空間。1964年Willioms提出了堆排序。堆的定義：n個元素的序列k1,k2,kn當(dāng)且僅當(dāng)滿足如下關(guān)系時，稱之為堆。ki k2iki k2i ki k2i+1 ki k2i+1(i=1,2, ,n/2 )若將和此序列對應(yīng)的一維數(shù)組看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不小于（或不大于）其左右孩子結(jié)點的值。2 堆排序的基本思想：若序列 k1,k2,kn 是堆，則堆頂元素必為序列中n個元素的最大值（或最小值）。如果在輸出堆頂?shù)淖畲笾岛?，使得剩余n-1個元素的序列重又建成一個堆，則得到次大值。反復(fù)執(zhí)行便能得到所有記錄的有序序列，這個過程稱為堆排序。 現(xiàn)在剩下兩個問題：（1）如何由一個無序序列建成一個堆；（2）如何在輸出堆頂元素后，調(diào)整剩余元素為一個新的堆。問題1:當(dāng)堆頂元素改變時，如何重建堆? “篩選”法調(diào)整成堆。 問題2:如何由一個任意序列建初堆？一個任意序列看成是對應(yīng)的完全二叉樹，由于葉結(jié)點可以視為單元素的堆，因而可以反復(fù)利用“篩選”法，自底向上逐層把所有子樹調(diào)整為堆，直到將整個完全二叉樹調(diào)整為堆。 對無序序列49,38,65,97,76,13,27,49建堆示例：問題3:如何利用堆進(jìn)行排序？ 進(jìn)行堆排序的步驟：將待排序記錄按照堆的定義建初堆，并輸出堆頂元素；調(diào)整剩余的記錄序列，利用篩選法將前n-i個元素重新篩選建成為一個新堆，再輸出堆頂元素；重復(fù)執(zhí)行步驟n-1次進(jìn)行篩選, 新篩選成的堆會越來越小，而新堆后面的有序關(guān)鍵字會越來越多，最后使待排序記錄序列成為一個有序的序列，這個過程稱之為堆排序。 例：初始序列為 26，5，77，1，61，11，59，15，48，193 算法：void Sift(rectype R, int s; int m)/篩選算法temp=Rs;for(j=2*s;j=m;j*=2) if (jm)&(Rj.key=Rj.key) break;Rs=Rj;s=j;Rs=temp;/堆排序算法void HeapSort(rectype R,int n)for (i=n/2;i=1;i-)/初始建堆Sift(R,i,n);for (i=n;i1;i-) temp=R1; R1=Ri;Ri=temp;Sift(R,1,i-1);4 算法分析：初始建堆比較次數(shù)為：O(n)排序中比較次數(shù)為：O(n*log2n)。移動次數(shù)小于比較次數(shù)。在最壞的情況下，時間復(fù)雜度也是O(nlogn)。且僅需一個記錄大小的輔助空間。堆排序適用于n值較大的情況。堆排序是不穩(wěn)定的排序方法。10.5 歸并排序1 基本思想：歸并的含義是將兩個或兩個以上的有序表合并成一個有序表。利用歸并的思想就可以實現(xiàn)排序。假設(shè)初始的序列含有n個記錄，可以看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復(fù)直到得到一個長度為n的有序序列為止。這種排序方法稱為二路歸并排序。2 示例：void Merge(rectype R,rectype R1, int low,int mid, int high)i=low; j=mid+1; k=low;while (i=mid)&(j=high)if (Ri.key=Rj.key) R1k+=Ri+;else R1k+=Rj+;while (j=mid) R1k+=Ri+;while (j=high) R1k+=Rj+;void MSort(rectype R,rectype R1, int s,int t) if (s=t) r1s=rs;elsem=(s+t)/2;MSort(R,R2,s,m);MSort(R,R2,m+1,t);Merge(r2,r1,s,m,t);void MergeSort(rectype R,int n)MSort(r,r,1,n);時間復(fù)雜度: O(nlog2n)空間復(fù)雜度: 和待排記錄等量的空間.二路歸并算法是穩(wěn)定的.一般情況下很少用于內(nèi)部排序.10.6分配排序分配類排序則利用分配和收集兩種基本操作，基數(shù)類排序就是典型的分配類排序。 分配排序的思想是把排序碼分解成若干部分，然后通過對各個部分排序碼的分別排序，最終達(dá)到整個排序碼的排序。 10.6.1概述一般情況下，假設(shè)文件F有n個記錄F=(R0，R1，Rn-1)且每個記錄Ri的排序碼中含有d個部分(ki0, ki1, kid-1)，則文件F對排序碼(k0,k1,kd-1)有序是指文件中任意兩個記錄Ri和Rj(0ijn-1)滿足詞典次序有序關(guān)系(ki0, ki1, kid-1) (kj0, kj1, kjd-1)其中k0稱為最高位排序碼，kd-1稱為最低位排序碼。實現(xiàn)分配排序，有兩種方法第一種是先對最高位排序碼k0排序，稱為最高位優(yōu)先法（Most Significant Digit first）。第二種是先對最低位排序碼kd-1排序，稱為最低位優(yōu)先法（Least Significant Digit first） 。 例如：我們可以將一副撲克牌的排序過程看成由花色和面值兩個關(guān)鍵字進(jìn)行排序的問題。若規(guī)定花色和面值的順序如下：花色：梅花 方塊 紅桃 黑桃面值：A2310JQK并進(jìn)一步規(guī)定花色的優(yōu)先級高于面值，則一副撲克牌從小到大的順序為：梅花A，梅花2，梅花K；方塊A，方塊2，方塊K；紅桃A，紅桃2，紅桃K；黑桃A，黑桃2，黑桃K。最高位優(yōu)先：先按花色分成有序的四類，然后再按面值對每一類從小到大排序。最低位優(yōu)先：先按面值從小到大把牌擺成13疊（每疊4張牌），然后將每疊牌按面值的次序收集到一起，再對這些牌按花色擺成4疊，每疊有13張牌，最后把這4疊牌按花色的次序收集到一起，于是就得到了有序序列。低位優(yōu)先法比高位優(yōu)先法簡單，高位優(yōu)先排序必須將文件逐層分割成若干子文件，然后各子文件獨立排序；低位優(yōu)先排序不必分成子堆，對每個排序碼都是整個文件參加排序，且可通過若干次“分配”和“收集”實現(xiàn)排序。但對Ki(0 = i = d-2)進(jìn)行排序時，只能用穩(wěn)定的排序方法。下面將介紹的基數(shù)排序就是用排序碼低位優(yōu)先法的思想對排序碼進(jìn)行分解后排序的一種方法。10.6.2鏈?zhǔn)交鶖?shù)排序 采用基數(shù)排序首先把每個排序碼看成是一個d元組Ki=(Ki0, Ki1, Kid-1)其中每個Ki都是集合C0，C1，Cr-1 (C0C1Cr-1)中的值，即C0KijCr-1(0in-1, 0jd-1)，其中r稱為