【正文】 ?概述 ?插入排序 ?快速排序 ?選擇排序 ?歸并排序 ?小結(jié) 第十章 內(nèi)部排序 概 述 ?排序 ： 將一組雜亂無章的記錄按一定的規(guī)律順次排列起來 。 ?關(guān)鍵字 (key): 通常數(shù)據(jù)記錄有多個 屬性域 ， 即多個數(shù)據(jù)成員組成 ， 其中有一個屬性域可用來區(qū)分記錄 ， 作為排序依據(jù) 。該域即為關(guān)鍵字 。 ? 主關(guān)鍵字 : 如果在待排序記錄序列中各個記錄的關(guān)鍵字互不相同，這種關(guān)鍵字即主關(guān)鍵字。按照主關(guān)鍵字進(jìn)行排序，排序的結(jié)果是唯一的。 ? 次關(guān)鍵字 :待排序記錄序列中有些記錄的關(guān)鍵字可能相同，這種關(guān)鍵字稱為次關(guān)鍵字。按照次關(guān)鍵字進(jìn)行排序，排序的結(jié)果可能不唯一。 ? 排序算法的穩(wěn)定性 : 如果在記錄序列中有兩個記錄 R[i]和 R[j]，它們的關(guān)鍵字 k[i] == k[j]，且在排序之前，記錄 R[i]排在 R[j]前面。如果在排序之后，記錄 R[i]仍在記錄 R[j]的前面，則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。 ? 內(nèi)排序與外排序 : 內(nèi)排序是指在排序期間數(shù)據(jù)記錄全部存放在內(nèi)存的排序；外排序是指在排序期間全部記錄個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。 ? 排序的時間開銷 : 排序的時間開銷是衡量算法好壞的最重要的標(biāo)志。 排序的時間開銷可用算法執(zhí)行中的記錄比較次數(shù) 與 記錄移動次數(shù) 來衡量 。各節(jié)給出算法運(yùn)行時間代價的大略估算一般都 按平均情況 進(jìn)行估算。對于那些 受記錄關(guān)鍵字序列初始排列及記錄個數(shù)影響較大的 ， 需要 按最好情況 和 最壞情況 進(jìn)行估算 。 ? 算法執(zhí)行時所需的附加存儲 : 評價算法好壞的另一標(biāo)準(zhǔn)。 ? 待排序記錄的存儲方式 ： ? 以一維數(shù)組作為存儲結(jié)構(gòu)，排序時必須實(shí)際移動記錄； ? 以鏈表 (動態(tài)鏈表或靜態(tài)鏈表 )作為存儲結(jié)構(gòu)，排序時不用物理移動記錄，只需修改指針； ? 有的排序方法難于在鏈表上實(shí)現(xiàn)，且需要避免排序過程中的記錄移動，可將待排序記錄本身存儲在一組地址連續(xù)的存儲單元內(nèi)，同時附設(shè)一個指示記錄存儲位置的地址向量，排序過程中不移動記錄，而移動地址向量中這些記錄的地址。 待排序記錄的數(shù)據(jù)類型說明： define MAXSIZE 20 typedef int KeyType。 typedef struct{ KeyType key。 InfoType otherinfo。 }RedType。 typedef struct{ RedType r[MAXSIZE]。 int length。 }SqList。 插入排序 (Insert Sorting) ? 直接插入排序的基本思想是：當(dāng)插入第 i (i ? 1) 個記錄時，前面的 R[1], R[2], …, R[ i1]已經(jīng)排好序。這時，用 R[i]的關(guān)鍵字與 R[i1], R[i2], … 的關(guān)鍵字順序進(jìn)行比較，找到插入位置即將 R[i]插入，原來位置上的記錄向后順移。 基本方法 ：每步將一個待排序的記錄，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組記錄的適當(dāng)位置上，直到記錄全部插入為止。 直接插入排序 (Insert Sort) 各趟排序結(jié)果 21 25 49 25* 16 08 1 2 3 4 5 6 1 2 3 4 5 6 temp 21 25 49 25* 16 08 25 i = 2 1 2 3 4 5 6 temp 21 25 49 25* 16 08 49 i = 3 21 25 49 25* 16 08 1 2 3 4 5 6 temp i = 4 25* 1 2 3 4 5 6 temp 21 25 49 25* 16 08 i = 5 16 1 2 3 4 5 6 temp 21 25 49 25* 16 08 i = 6 08 21 25 49 25* 16 08 1 2 3 4 5 6 i = 5 時的排序過程 完成 16 16 1 2 3 4 5 6 temp 21 25 49 25* 08 16 i = 5 j = 4 49 16 1 2 3 4 5 6 temp 21 25 49 25* 08 16 i = 5 j = 3 25* 16 21 25 49 25* 08 1 2 3 4 5 6 16 i = 5 j = 2 25 16 1 2 3 4 5 6 temp 21 49 25* 08 16 25 i = 5 j = 1 1 2 3 4 5 6 temp 21 25 49 25* 08 16 21 i = 5 j = 0 16 對順序表直接插入排序的算法： void InsertSort( SqList amp。L ) { int i, j。 for( i=2。 i=。 ++i ) if ([i].key [i1].key) // ,需將 [i]插入有序子表 { [0]=[i]。 // 復(fù)制為哨兵 [i]= [i1]。 for(j=i2。 [0].key[j].key。 j ) [j+1]=[j]。 // 記錄后移 [j+1]=[0]。 // 插入到正確位置 } } – 保存記錄 [i]的副本； – 監(jiān)視下標(biāo) j是否越界，自動控制循環(huán)結(jié)束 說明：監(jiān)視哨 [0]的作用： ? 直接插入排序的算法簡潔 ， 容易實(shí)現(xiàn) 。 從時間來看 ， 排序的基本操作為：比較兩個記錄的大小和移動記錄 。 其中： ? 最小比較次數(shù)： Cmin = n1 = O(n) ? 最大比較次數(shù)： Cmax =(2+3+… +n)=(n+2)(n1)/2 = O(n2 ) ? 最小移動次數(shù)： Mmin = 0 ? 最大移動次數(shù)： Mmax = (2+1 + 3+1 + … + n+1) = O(n2) ? 若待排序記錄序列中出現(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)約為 n2/4。因此，直接插入排序的時間復(fù)雜度為 o(n2)。 算法分析 ： ? 關(guān)鍵字比較次數(shù)和記錄移動次數(shù)與記錄關(guān)鍵字的初始排列有關(guān)。 ? 從空間看，直接插入排序算法只需一個記錄的輔助空間。 ?直接插入排序是一種穩(wěn)定的排序方法。 折半插入排序 (Binary Insertsort) ?基本思想 ： – 設(shè)在順序表中有一 個記錄序列 R[1], R[2], …, R[ n]。其中， R[1], R[2], …, R[ i1] 是已經(jīng)排好序的記錄。 – 在插入 R[i] 時，利用 折半搜索法 尋找 R[i] 的插入位置。 ? 折半插入排序的算法 : void BInsertSort(SqList amp。L) { int i, j, m, low, high。 for( i=2。 i=。 ++i ){ [0]=[i]。 // 將 [i]暫存到 [0] low=1。 high=i1。 while( low = high ){ // 在 r[low..high]中折半查找有序插入的位置 m = (low+high)/2。 // 折半