武漢軟件工程職業(yè)學(xué)院《數(shù)據(jù)結(jié)構(gòu)講義》第21講 排序.doc

第六章 排序第二十一講 排序1掌握排序的基本概念。2掌握內(nèi)部排序中的插入排序方法。 教學(xué)重點(diǎn)： 內(nèi)部排序中的插入排序方法 教學(xué)難點(diǎn)： 內(nèi)部排序中的插入排序方法 授課內(nèi)容6.1排序的基本概念排序（sorting）又稱分類，是計算機(jī)程序設(shè)計中的一個重要操作，即把一批任意序列的數(shù)據(jù)元素（或記錄），重新排列成一個按關(guān)鍵字有序的序列。通過排序可以提高數(shù)據(jù)表的直觀性，并為以后查詢提供方便，提高查找效率。排序的應(yīng)用領(lǐng)域十分慣犯，因此在很多領(lǐng)域有廣泛應(yīng)用。電話簿、病歷、情報、檔案、圖書館和各種詞典的目錄表（或目錄卡）等都離不開排序。為了進(jìn)一步理解排序，在此給出一個比較確切的排序定義：假設(shè)含d個記錄的序列為 R1 ,R2 ,Rd (6.1.1)其相應(yīng)的關(guān)鍵字序列為 K1 ,K2 ,Kd 需確定1，2，,d的一種排列p1,p2,pd,使其響應(yīng)的關(guān)鍵字滿足下列的非遞減（或非遞增）關(guān)系： Kp1Kp2Kpd (6.1.2)即使式（6.1.1）的序列成為一個按關(guān)鍵字有序的序列 Rp1 ,Rp2 , ,Rpd (6.1.3)這樣一種操作成為排序。在待排序的記錄中若關(guān)鍵字值是唯一的（即Ki是主關(guān)鍵字），則任何一組記錄經(jīng)排序后得到的結(jié)果是唯一的；在待排序的記錄中若有兩個或兩個以上關(guān)鍵字值相同的記錄，則排序的結(jié)果不唯一。在用某種方法排序之后，這些關(guān)鍵字相同的記錄相對先后次序不變，即當(dāng)Ki=Kj(1id,1jd,i)且ij,若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中Rj領(lǐng)先于Ri，則稱所用的排序方法是不穩(wěn)定的。排序的方法有多種，若按排序過程中所涉及的存儲器不用，可獎排序方法分為兩大類：一類是內(nèi)部排序，即將待排記錄調(diào)入計算機(jī)的內(nèi)存中進(jìn)行的排序過程，其排序方法包括插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等。另一類是外部排序，即待排序記錄的數(shù)量很大，以致內(nèi)存不能依次容納全部記錄，在排序過程中尚需對外存訪問的排序過程。數(shù)據(jù)結(jié)構(gòu)定義為：#define MAXSIZE 30typedef struct int key; dataType oth; RcdType; RcdType rMAXSIZE+1;62 內(nèi)部排序 621 插入排序 1直接插入排序 直接插入排序（straight insertion sort）是一種最簡單的插入排序方法。它的基本操作是將一個記錄插入到一個長度為n（假設(shè)）的有序表中，使之仍保持有序，從而得到一個新的長度為n+1的有序表。如同玩撲克牌的人抓牌一樣，將抓到的牌插入到手重已排好的牌的一個適當(dāng)位子上。 算法思路：設(shè)有彝族關(guān)鍵字K1,K2,Kn；認(rèn)為Kl就是一個有序序列；讓K2插入上述表長為1的有序序列中，使之成為一個表長為2的有序序列；讓K3插入上述表長為2的有序序列中，使之成為一個表長為3的有序序列；依此類推，最后讓Kn插入到表廠為n-1的有序序列中，得到一個表長為n的有序序列。void InsertSort(RcdType r ,int n)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0.keyrj.key) rj+1=rj;j-; rj+1=r0; 2，折半插入排序當(dāng)用直接插入排序進(jìn)行到某一趟比較時，對于ri.key來講，前邊i-1個記錄已經(jīng)按關(guān)鍵字排序。此時可不用直接插入排序的方法，而改用折半插入排序。算法思路：與直接插入排序相近，只是在進(jìn)行比較時，ri.key首先與已排好序的中間記錄進(jìn)行比較，然后根據(jù)比較結(jié)果來確定ri.key繼續(xù)與中間記錄的前面記錄比較，還是與中間記錄的后面記錄比較，找出應(yīng)插入的位置，然后插入。算法如下：void BinSort(RcdType r ,int n ) for (i=2;i=n;i+)r0=ri;low=1;high=i-1;while(low=high) mid=(low+high)/2; if(r0.key=low;j-) rj+1=rj;rlow=r0; 3.希爾排序希爾排序（Shell sort）也稱“縮小增量排序”。它的做法不是每次一個元素挨一個元素的比較。而是先將整個待排序記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄看承是一組，然后在各組內(nèi)進(jìn)行插入排序；接著取d2(d2=1),即所有記錄成為一個組為止。希爾排序?qū)υ隽啃蛄械倪x擇沒有嚴(yán)格規(guī)定，一般選d1約為n/2,d2為d1/2,d3為d2/2,di=1。void ShellSo