舊參考課件1314學年春季ch19排序

1、 排序是指將一組數(shù)據(jù)元素按某個數(shù)據(jù)項值的大小排列成排序是指將一組數(shù)據(jù)元素按某個數(shù)據(jù)項值的大小排列成一個有序序列的過程。一個有序序列的過程。 排序是計算機程序設計中經(jīng)常使用的一種重要操作，是排序是計算機程序設計中經(jīng)常使用的一種重要操作，是組織數(shù)據(jù)和處理數(shù)據(jù)的最基本最重要的運算之一。組織數(shù)據(jù)和處理數(shù)據(jù)的最基本最重要的運算之一。 排序被廣泛應用于數(shù)據(jù)處理、情報檢索、商業(yè)金融等許排序被廣泛應用于數(shù)據(jù)處理、情報檢索、商業(yè)金融等許多領域。多領域。 第第1919章章 排序排序19.1 基本概念19.2 插入排序19.3 交換排序19.4 選擇排序19.5 歸并排序19.6 分配排序（基數(shù)排序）1 1記錄、關

2、鍵碼和排序表：記錄、關鍵碼和排序表： 記錄：記錄： 數(shù)據(jù)元素數(shù)據(jù)元素 關鍵碼（或排序碼）：作為排序依據(jù)的數(shù)據(jù)項稱關鍵碼（或排序碼）：作為排序依據(jù)的數(shù)據(jù)項稱為數(shù)據(jù)元素的關鍵碼。為數(shù)據(jù)元素的關鍵碼。 排序表：若干個（排序表：若干個（n n個）排序紀錄組成的集合。個）排序紀錄組成的集合。 排序表也稱成為文件，主要操作是排序。排序表也稱成為文件，主要操作是排序。2 2非遞減序列、遞減序列、非遞增序列、遞增有序非遞減序列、遞減序列、非遞增序列、遞增有序3 3穩(wěn)定排序和非穩(wěn)定排序穩(wěn)定排序和非穩(wěn)定排序 穩(wěn)定排序穩(wěn)定排序 ：記錄的相對位置在排序前后不發(fā)生：記錄的相對位置在排序前后不發(fā)生變化變化 不穩(wěn)定排序：不

3、穩(wěn)定排序：4 4內(nèi)部排序和外部排序內(nèi)部排序和外部排序 待排序的表完全放在內(nèi)存中稱為內(nèi)排序待排序的表完全放在內(nèi)存中稱為內(nèi)排序5 5對排序方法的評價對排序方法的評價 空間性能：除排序表以外的內(nèi)存占用情況。空間性能：除排序表以外的內(nèi)存占用情況。 時間性能：比較關鍵碼的次數(shù)，數(shù)據(jù)移動的次數(shù)。時間性能：比較關鍵碼的次數(shù)，數(shù)據(jù)移動的次數(shù)。 它們往往是排序表規(guī)模（它們往往是排序表規(guī)模（n n）的函數(shù)）的函數(shù)第第1919章章 排序排序19.1 基本概念19.2 插入排序19.3 交換排序 19.4 選擇排序19.5 歸并排序19.6 分配排序（基數(shù)排序） 1 1 直接插入排序直接插入排序 2 2 折半插入排序

4、折半插入排序 3 3 * *表插入排序表插入排序 3 3 希爾排序希爾排序 插入排序的基本思想是：每次將一個待排序的記錄，插入排序的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子表的適當位按其關鍵字大小插入到前面已經(jīng)排好序的子表的適當位置，直到全部記錄插入完成，整個表有序為止。置，直到全部記錄插入完成，整個表有序為止。19.2.1 19.2.1 直接插入排序直接插入排序 直接插入排序是一種簡單的插直接插入排序是一種簡單的插入排序方法，基本思想為：在入排序方法，基本思想為：在R1R1至至Ri-1Ri-1長度為長度為i-1i-1的子表已經(jīng)有序的情的子表已經(jīng)有序的情況下，

5、將況下，將RiRi插入，得到插入，得到R1R1至至RiRi長長度為度為i i 的子表有序，這樣通過的子表有序，這樣通過n-1n-1趟趟（i=2.ni=2.n）之后，）之后，R1R1至至RnRn有序。有序。例如，對于以下序列（為簡便起見，每一個記錄只例如，對于以下序列（為簡便起見，每一個記錄只列出其排序碼，用排序碼代表記錄）：列出其排序碼，用排序碼代表記錄）： 10 18 20 36 60 25 30 18 12 56 10 18 20 36 60 25 30 18 12 56 其中，前其中，前5 5個記錄組成的子序列是有序的，這時個記錄組成的子序列是有序的，這時要將第要將第6 6個記錄插入到前

6、個記錄插入到前5 5個記錄組成的有序子序列個記錄組成的有序子序列中去，得到一個含有中去，得到一個含有6 6個記錄的新有序序列。完成這個記錄的新有序序列。完成這個插入首先需要找到插入位置：個插入首先需要找到插入位置：202536202536，因此，因此2525應插入到記錄應插入到記錄2020和記錄和記錄3636之間，從而得到以下新序之間，從而得到以下新序列：列： 10 18 20 25 36 60 30 18 12 56 10 18 20 25 36 60 30 18 12 56 這就是一趟直接插入排序的過程。這就是一趟直接插入排序的過程。 直接插入排序：僅有一個記錄的表總是有序的，因此，對直接

7、插入排序：僅有一個記錄的表總是有序的，因此，對n n個記錄個記錄的表，可從第二個記錄開始直到第的表，可從第二個記錄開始直到第n n個記錄，逐個向有序表中進行插入操個記錄，逐個向有序表中進行插入操作，從而得到作，從而得到n n個記錄按關鍵碼有序的表。個記錄按關鍵碼有序的表。 R0 R1 R2 R3 R4 R5 R6 R7 R8 R19 R10 R0 R1 R2 R3 R4 R5 R6 R7 R8 R19 R10初始初始: 36 20 18 10 60 25 30 18 12 56: 36 20 18 10 60 25 30 18 12 56i=2 i=2 ：(20) ( 20 36) 18 10

8、 60 25 30 18 12 56(20) ( 20 36) 18 10 60 25 30 18 12 56 i=3 i=3 ：(18) ( 18 20 36) 10 60 25 30 18 12 56 (18) ( 18 20 36) 10 60 25 30 18 12 56 i=4 i=4 ：(10) (10 18 20 36 ) 60 25 30 18 12 56(10) (10 18 20 36 ) 60 25 30 18 12 56i=7 i=7 ：(30) (10 18 20 25 30 36 60) 18 12 56(30) (10 18 20 25 30 36 60) 18

9、12 56i=8 i=8 ：(18) (10 18 18 20 25 30 36 60) 12 56(18) (10 18 18 20 25 30 36 60) 12 56【算法【算法19-119-1】直接插入排序】直接插入排序void _InsertSort(datatype R , int n) void _InsertSort(datatype R , int n) / /* *對排序表對排序表R1.RnR1.Rn進行直接插入排序，進行直接插入排序，n n是記錄的個是記錄的個數(shù)數(shù)* */ / for(i=2; i=n; i+) for(i=2; i=n; i+) if (Ri.keyRi

10、-1.key) if (Ri.keyRi-1.key) R0=Ri; / R0=Ri; /* *將將RiRi插入插入R1. Ri-1R1. Ri-1中，中，R0R0為監(jiān)測哨為監(jiān)測哨* */ / for(j=i-1; R0.keyRj.key; j-) for(j=i-1; R0.keyRj.key; j-)Rj+1=Rj; Rj+1=Rj; / /* *后移記錄后移記錄* */ / Rj+1=R0; Rj+1=R0; / /* *插入到合適位置插入到合適位置* */ / 性能分析性能分析 空間性能：僅用了一個輔助單元空間性能：僅用了一個輔助單元R0R0作為監(jiān)視哨，作為監(jiān)視哨，空間復雜度為空間復

11、雜度為O(1)O(1)。 時間性能：向有序表中逐個插入記錄的操作，進時間性能：向有序表中逐個插入記錄的操作，進行了行了n n1 1趟，每趟操作分為比較關鍵碼和移動記錄，趟，每趟操作分為比較關鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于初始序列的排而比較的次數(shù)和移動記錄的次數(shù)取決于初始序列的排列情況列情況 。分三種情況討論：。分三種情況討論：)1(2111nnjnjnnnjnj2)1(21)2(11(2) (2) 最壞情況下：最壞情況下： 即第即第j j趟操作，插入記錄需要同前面的趟操作，插入記錄需要同前面的j j個記錄進行個記錄進行j j次次關鍵碼比較，移動記錄的次數(shù)為關鍵碼比較，移動記

12、錄的次數(shù)為j+2j+2次。次。(1)(1)最好情況下：最好情況下：(2)(2)即待排序列已按關鍵碼有序，每趟操作只需即待排序列已按關鍵碼有序，每趟操作只需1 1次比較，次比較，0 0次移動。即：次移動。即：(3)(3) 總比較次數(shù)總比較次數(shù)= n-1= n-1次次(4)(4) 總移動次數(shù)總移動次數(shù)= 0= 0次次(3)(3)平均情況下：平均情況下： 即第即第j j趟操作，插入記錄大約同前面的趟操作，插入記錄大約同前面的j/2j/2個記錄進行關鍵個記錄進行關鍵碼比較，移動記錄的次數(shù)為碼比較，移動記錄的次數(shù)為j/2+2j/2+2次。次。 21141)1(412nnnjnj211412)1(41)2

13、2(nnnnjnj 由此，直接插入排序的時間復雜度為O(n2)。 直接插入排序是一個穩(wěn)定的排序方法。 直接插入排序也可以在鏈式結(jié)構(gòu)上實現(xiàn)。 19.2.2 19.2.2 折半插入排序折半插入排序 直接插入排序的基本操作是向有序表直接插入排序的基本操作是向有序表中插入一個記錄，在直接插入排序中，插入中插入一個記錄，在直接插入排序中，插入位置的確定是通過對有序表中關鍵碼的順序位置的確定是通過對有序表中關鍵碼的順序比較得到的。比較得到的。 既然是在有序表中確定插入位置，因此在既然是在有序表中確定插入位置，因此在尋找尋找RiRi的插入位置時，就可以采用折半查的插入位置時，就可以采用折半查找的方法，用折半

14、查找方法查找找的方法，用折半查找方法查找RiRi的插入的插入位置，再將位置，再將RiRi插入進去，使得插入進去，使得RiRi到到RiRi有序，這種方法就是折半插入排序。有序，這種方法就是折半插入排序。【算法19-2】折半插入排序算法void B_InsertSort(datatype R , int n) /* 對排序表R1.Rn作折半插入排序, n是記錄的個數(shù)*/ for(i=2; i=n; i+) R0=Ri; /* 保存待插入元素 */ low=1; high=i1; /* 設置初始區(qū)間 */ while(lowRmid.key) low=mid+1; /* 插入位置在高半?yún)^(qū)中 */ e

15、lse high=mid-1; /* 插入位置在低半?yún)^(qū)中 */ for(j=i-1;j=high+1;j-) /* high+1為插入位置 */ Rj+1=Rj; /* 后移元素，留出插入空位 */ Rhigh+1=R0; /* 將元素插入 */ 時間效率時間效率 確定插入位置所進行的折半查找，定位一個關確定插入位置所進行的折半查找，定位一個關鍵碼的位置需要比較次數(shù)至多為鍵碼的位置需要比較次數(shù)至多為 次，次，所以比較次數(shù)時間復雜度為所以比較次數(shù)時間復雜度為O (nlog2n)O (nlog2n)。 相對直接插入排序，折半插入排序只能減少關相對直接插入排序，折半插入排序只能減少關鍵字間的比較次數(shù)

16、，而移動記錄的次數(shù)和直接插入鍵字間的比較次數(shù)，而移動記錄的次數(shù)和直接插入排序相同，故時間復雜度仍為排序相同，故時間復雜度仍為O(n2)O(n2)。 折半插入排序是一個穩(wěn)定的排序方法。折半插入排序是一個穩(wěn)定的排序方法。 折半插入排序只適合于順序存儲的排序表。折半插入排序只適合于順序存儲的排序表。) 1(log2n19.2.3 19.2.3 希爾排序希爾排序 又稱為又稱為“縮小增量排序縮小增量排序”是是19511951年年由由D.L.ShellD.L.Shell提出來的提出來的 基本思想：先選取一個小于基本思想：先選取一個小于n n的整數(shù)的整數(shù)didi（稱之為步長），然后把排序表中的（稱之為步長）

17、，然后把排序表中的n n個記錄個記錄分為分為didi個組，從第一個記錄開始，間隔為個組，從第一個記錄開始，間隔為didi的記錄為同一組，各組內(nèi)進行直接插入排序，的記錄為同一組，各組內(nèi)進行直接插入排序，一趟之后，間隔一趟之后，間隔didi的記錄有序，隨著有序性的記錄有序，隨著有序性的改善，減小步長的改善，減小步長didi（排序子表變大），重（排序子表變大），重復進行，直到復進行，直到di=1di=1（全部記錄成為一個排序（全部記錄成為一個排序表），使得間隔為表），使得間隔為1 1的記錄有序，也就使整體的記錄有序，也就使整體達到了有序。達到了有序。 步長為步長為1 1時就是前面講的直接插入排序。時

18、就是前面講的直接插入排序。 例：例： 排序列表為：排序列表為： 319,80,76,41,13,219,50,78,30,11,100,7,41,86319,80,76,41,13,219,50,78,30,11,100,7,41,86 步長因子分別取步長因子分別取5 5、3 3、1 1，則排序過程如下：，則排序過程如下：319807641132195078301110074186P=5間隔為5的子序列分別為：319，219，100，80，50，7，76，78，41，41，30，86，13，11。第一趟排序結(jié)果，使得間隔為第一趟排序結(jié)果，使得間隔為5 5的字表有序：的字表有序： 2197413

19、01131950764113100807886P=3子序列分別為子序列分別為:219,30,50,13,78:219,30,50,13,78，7,11,76,100,867,11,76,100,86，41,319,41,8041,319,41,80。第二趟排序結(jié)果：。第二趟排序結(jié)果： 137319219114130764150868078100P=1此時，序列此時，序列“基本有序基本有序”，對其進行直接插入排序，得到最，對其進行直接插入排序，得到最終結(jié)果：終結(jié)果： 711132193031941415076788086100【算法【算法19-419-4】希爾排序的算法】希爾排序的算法void

20、ShellSort(datatype R , int n, int d , int t) void ShellSort(datatype R , int n, int d , int t) / /* *按增量序列按增量序列d0, d1 dtd0, d1 dt11對排序表對排序表R1.RnR1.Rn進行希爾排序進行希爾排序* */ /int i,j,k,h; int i,j,k,h; for(k=0; kt; k+) for(k=0; kt; k+) h=dk; h=dk; / /* *本趟的增量本趟的增量* */ / for(i=h+1; i=n; i+) for(i=h+1; i=n; i+

21、) if(Ri.keyRi-h.key) / if(Ri.key0&R0.key0&R0.keyRj.key; j=jh)h) Rj+h=Rj; Rj+h=Rj; / /* *記錄后移記錄后移* */ / Rj+h=R0; Rj+h=R0; / /* *插入到正確位置插入到正確位置* */ / 時效分析時效分析 希爾排序時效分析很難，關鍵碼的比較次數(shù)與記希爾排序時效分析很難，關鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取，特定情況下錄移動次數(shù)依賴于步長因子序列的選取，特定情況下可以準確估算出關鍵碼的比較次數(shù)和記錄的移動次數(shù)。可以準確估算出關鍵碼的比較次數(shù)和記錄的移動次數(shù)

22、。目前還沒有人給出選取最好的步長因子序列的方法。目前還沒有人給出選取最好的步長因子序列的方法。 步長因子序列可以有各種取法，有取奇數(shù)的，也步長因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：步長因子中除有取質(zhì)數(shù)的，但需要注意：步長因子中除1 1外沒有公外沒有公因子，且最后一個步長因子必須為因子，且最后一個步長因子必須為1 1。 希爾排序方法是一個不穩(wěn)定的排序方法。希爾排序方法是一個不穩(wěn)定的排序方法。第第1919章章 排序排序19.1 基本概念19.2 插入排序19.3 交換排序 19.4 選擇排序19.5 歸并排序19.6 分配排序（基數(shù)排序） 交換排序的基本思想是：通過排序表中

23、兩個記錄關鍵交換排序的基本思想是：通過排序表中兩個記錄關鍵碼的比較，若與排序要求相逆，則將二者進行交換，直至碼的比較，若與排序要求相逆，則將二者進行交換，直至沒有反序的記錄為止。沒有反序的記錄為止。 交換排序的特點是：排序碼值較小記錄的向序列的一交換排序的特點是：排序碼值較小記錄的向序列的一端移動，排序碼值較大記錄的向序列的另一端移動。端移動，排序碼值較大記錄的向序列的另一端移動。19.3.1 19.3.1 冒泡排序冒泡排序19.3.2 19.3.2 快速排序快速排序19.3.1 19.3.1 冒泡排序冒泡排序 設排序表為設排序表為R1.RnR1.Rn，對，對n n個記錄的排序表進行冒泡排序個

24、記錄的排序表進行冒泡排序(Bubble Sort)(Bubble Sort)的過程是：的過程是： 第第1 1趟，從第趟，從第1 1個記錄開始到第個記錄開始到第n n個記錄，對個記錄，對n n1 1對相鄰的兩對相鄰的兩個記錄關鍵字進行比較，若與排序要求相逆，則將二者交換。個記錄關鍵字進行比較，若與排序要求相逆，則將二者交換。 一趟之后，具有最大關鍵字的記錄交換到了一趟之后，具有最大關鍵字的記錄交換到了RnRn， 第第2 2趟，從第趟，從第1 1個記錄開始到第個記錄開始到第n n1 1個記錄繼續(xù)進行第二趟冒個記錄繼續(xù)進行第二趟冒泡。泡。 兩趟之后，具有次最大關鍵字的記錄交換到了兩趟之后，具有次最大

25、關鍵字的記錄交換到了RnRn11， 如此重復，如此重復，n n1 1趟后，在趟后，在R1.RnR1.Rn中，中，n n個記錄按關鍵碼有個記錄按關鍵碼有序。序。 冒泡排序最多進行冒泡排序最多進行 n n1 1趟，在某趟的兩兩比較過程中，如果趟，在某趟的兩兩比較過程中，如果一次交換都未發(fā)生，表明已經(jīng)有序，則排序提前結(jié)束。一次交換都未發(fā)生，表明已經(jīng)有序，則排序提前結(jié)束?！舅惴?9-5】冒泡排序算法 void Bubble_Sort (datetype R , int n) /*對排序表R1.Rn進行冒泡排序，n是記錄個數(shù)*/ int i, j; int swap; /*交換標志變量*/ for(i=

26、1; in1; i+) swap=0; for(j=1; jRj+1.key) R0=Rj+1; Rj=Rj+1; Rj+1=R0; swap=1; /*置交換標志*/ if(swap=0) break; 效率分析效率分析空間效率：僅用了一個輔助單元?？臻g效率：僅用了一個輔助單元。時間效率：總共要進行時間效率：總共要進行n-1n-1趟冒泡，對趟冒泡，對j j個記錄的表個記錄的表進行一趟冒泡需要進行一趟冒泡需要j-1j-1次關鍵碼比較。次關鍵碼比較。 )1(21)1(2nnjnj移動次數(shù)：最好情況下：待排序列已有序，不需移動。最壞情況下：每次比較后均要進行三次移動。)1(23)1(32nnjnj

27、19.3.2 19.3.2 快速排序快速排序1 1、快速排序的思想、快速排序的思想 快速排序是通過比較關鍵碼、交換記錄，快速排序是通過比較關鍵碼、交換記錄，以某個記錄為界以某個記錄為界( (該記錄稱為支點，通常取第該記錄稱為支點，通常取第一個元素一個元素) )，將待排序列分成兩部分。其中，將待排序列分成兩部分。其中，一部分所有記錄的關鍵碼大于等于支點記錄一部分所有記錄的關鍵碼大于等于支點記錄的關鍵碼，另一部分所有記錄的關鍵碼小于的關鍵碼，另一部分所有記錄的關鍵碼小于支點記錄的關鍵碼。支點記錄的關鍵碼。 我們將待排序列按關鍵碼以支點記錄分我們將待排序列按關鍵碼以支點記錄分成兩部分的過程，稱為一次

28、（趟）劃分。成兩部分的過程，稱為一次（趟）劃分。 對各部分不斷劃分，直到每一步分只剩對各部分不斷劃分，直到每一步分只剩一個元素，整個序列則按關鍵碼有序。一個元素，整個序列則按關鍵碼有序。2 2、一次劃分示例、一次劃分示例【例【例19-519-5】對排序表：】對排序表：419,14,38,74,196,65, 8, 419,14,38,74,196,65, 8, 419, 55, 27419, 55, 27進行劃分。進行劃分。劃分過程如圖劃分過程如圖19-519-5所示。所示。設初始狀態(tài)設初始狀態(tài): : 419 14 38 74 196 65 419 14 38 74 196 65 8 419

29、55 27 8 419 55 27 14 38 74 196 65 8 14 38 74 196 65 8 419 55 27 419 55 27 low low highhigh從從highhigh向前搜索小于向前搜索小于419419的記錄，找到后將其調(diào)整到的記錄，找到后將其調(diào)整到lowlow位置，得到結(jié)果：位置，得到結(jié)果： 27 14 38 74 196 65 8 27 14 38 74 196 65 8 419 55 419 55 low low highhigh從從lowlow向后搜索大于向后搜索大于419419的記錄，找到后將其調(diào)整到的記錄，找到后將其調(diào)整到highhigh位置，得到

30、結(jié)果：位置，得到結(jié)果： 27 14 38 27 14 38 196 65 8 196 65 8 419 55 74 419 55 74 low low highhigh 再從再從highhigh向前搜索小于向前搜索小于419419的記錄，找到后將其調(diào)整到的記錄，找到后將其調(diào)整到lowlow位置，得到結(jié)果位置，得到結(jié)果： 27 14 38 8 196 65 27 14 38 8 196 65 419 55 74 419 55 74 low high low high 再從再從lowlow向后搜索大于向后搜索大于419419的記錄，找到后將其調(diào)整到的記錄，找到后將其調(diào)整到highhigh位置，得到

31、結(jié)位置，得到結(jié)果：果： 27 14 38 8 27 14 38 8 65 196 419 55 74 65 196 419 55 74 low high low high 再繼續(xù)，得到結(jié)果：再繼續(xù)，得到結(jié)果： 27 14 38 8 27 14 38 8 65 196 419 55 74 65 196 419 55 74 low= high low= high 當當low=highlow=high，劃分結(jié)束，填入支點記錄：，劃分結(jié)束，填入支點記錄： 27 14 38 8 419 65 196 419 55 74 27 14 38 8 419 65 196 419 55 743 3、快速排序一次劃

32、分算法、快速排序一次劃分算法【算法【算法19-619-6】劃分算法】劃分算法int Partition(datatype R , int low, int high) int Partition(datatype R , int low, int high) / /* *以以RlowRlow為支點對為支點對Rlow. .R highRlow. .R high進行劃分，進行劃分，返回支點記錄最終的位置返回支點記錄最終的位置* */ / R0=Rlow; R0=Rlow; / /* *暫存支點記錄暫存支點記錄* */ / while(lowhigh) while(lowhigh) / /* *從表

33、的兩端交替地向中從表的兩端交替地向中間掃描間掃描* */ / while(low=R0.key) while(low=R0.key) High-;High-; if(lowhigh) Rlow=Rhigh; low+; if(lowhigh) Rlow=Rhigh; low+; / /* *將比支點小將比支點小的交換到前面的交換到前面* */ / while(lowhigh&Rlow.keyR0.key) while(lowhigh&Rlow.keyR0.key) low+;low+; if(lowhigh) Rhigh=Rlow; high if(lowhigh) Rhigh

34、=Rlow; high ; ; / /* *將比支點大將比支點大的交換到后面的交換到后面* */ / Rlow=R0; Rlow=R0; / /* *支點記錄到位支點記錄到位* */ / return low; return low; / /* *返回支點記錄所在位置返回支點記錄所在位置* */ / 4 4、快速排序、快速排序 經(jīng)過劃分之后，支點則到了最終排好序的位置經(jīng)過劃分之后，支點則到了最終排好序的位置上，再分別對支點前后的兩組繼續(xù)劃分下去，直到每上，再分別對支點前后的兩組繼續(xù)劃分下去，直到每一組只有一個記錄為止，則是最后的有序序列，這就一組只有一個記錄為止，則是最后的有序序列，這就是快速

35、排序。是快速排序。 快速排序過程就是反復劃分的過程，算法如下：【算法19-7】快速排序算法void Quick_Sort(datatype R , int s, int t) /*對Rs.Rt進行快速排序*/ if( st ) i = Partition(R, s, t) /*將表一分為二*/ Quick_Sort(R, s, i1); /*對支點前端子表遞歸排序*/ Quick_Sort(R, i+1, t); /*對支點后端子表遞歸排序*/ 38741968419275541965145 5、效率分析、效率分析 最壞情況下：即每次劃分，只得到一個子序列，時效為O(n2)。 快速排序是通常被

36、認為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。 但若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取支點記錄，即將排序區(qū)間的兩個端點與中點三個記錄關鍵碼居中的作為支點記錄。 快速排序是一個不穩(wěn)定的排序方法（如：2，2，1） 。第第1919章章 排序排序19.1 基本概念19.2 插入排序19.3 交換排序 19.4 選擇排序19.5 歸并排序19.6 分配排序（基數(shù)排序）排序結(jié)束。排序結(jié)束。選擇排序需要選擇排序需要n-1趟。趟。 根據(jù)選擇最小關鍵碼記錄的方式不同，選擇排序根據(jù)選擇最小關鍵碼記錄的方式不同，選擇排序又有多種方法，在

37、本節(jié)中我們重點講兩種選擇排序：又有多種方法，在本節(jié)中我們重點講兩種選擇排序：19.4.1 19.4.1 簡單選擇排序簡單選擇排序19.4.3 19.4.3 堆排序堆排序19.4.1 19.4.1 簡單選擇排序簡單選擇排序 特點：每次選擇的過程是順序進行的。特點：每次選擇的過程是順序進行的。1 1、基本思想：、基本思想： 第第1 1趟，從第趟，從第1 1個到第個到第n n個記錄中選擇關鍵碼最小的個記錄中選擇關鍵碼最小的記錄與第記錄與第1 1個記錄交換；個記錄交換； 第第2 2趟，從第趟，從第2 2個到第個到第n n個記錄中選擇關鍵碼最小的個記錄中選擇關鍵碼最小的記錄與第記錄與第2 2個記錄交換；

38、個記錄交換； 第第i i趟，趟， 從第從第i i個到第個到第n n個記錄中選擇關鍵碼最小個記錄中選擇關鍵碼最小的記錄與第的記錄與第i i個記錄交換個記錄交換; ;直到第直到第n-1n-1趟，從最后兩個記錄中選擇較小的記錄放趟，從最后兩個記錄中選擇較小的記錄放置在第置在第n-1 n-1 位置。排序結(jié)束。位置。排序結(jié)束。2 2、示例：、示例：設排序表：設排序表：419 14 38 74 196 65 419 419 14 38 74 196 65 419 8 55 278 55 27第第1 1趟之后：趟之后：8 14 38 74 8 14 38 74 55 2755 27第第2 2趟之后：趟之后：

39、8 14 38 74 8 14 38 74 55 2755 27 （在本位就不用交換）（在本位就不用交換）第第3 3趟之后：趟之后：8 14 27 74 8 14 27 74 55 38 55 38 第第4 4趟之后：趟之后：8 14 27 419 196 65 8 14 27 419 196 65 74 419 55 38 74 419 55 38 。第第1919趟之后：趟之后： 8 14 27 38 419 8 14 27 38 419 419 55 65 74 196 419 55 65 74 196 3 3、算法實現(xiàn)、算法實現(xiàn)【算法【算法19-819-8】簡單選擇排序】簡單選擇排序vo

40、id Select_Sort(datatype R ,int n)void Select_Sort(datatype R ,int n) / /* *對排序表對排序表R1.RnR1.Rn進行冒泡排序，進行冒泡排序，n n是記錄是記錄個數(shù)個數(shù)* */ / for(i=1;in;i+) for(i=1;in;i+) / /* * 作作n-1n-1趟選取趟選取 * */ / k=i; k=i; / /* * 在在i i開始的開始的n-i+1n-i+1個記錄中個記錄中選關鍵碼最小的記錄選關鍵碼最小的記錄 * */ /for(j=i+1; j=n; j+) for(j=i+1; j=n; j+) if(

41、Rj.keyRk.key) if(Rj.keyRk.key) k=j; k=j;/ /* * k k中存放關鍵碼最小中存放關鍵碼最小記錄的下標記錄的下標 * */ / if (i!=k) / if (i!=k) /* * 關鍵碼最小的記錄與第關鍵碼最小的記錄與第i i個記錄交換個記錄交換 * */ / R0=Rk; Rk=Ri; R0=Rk; Rk=Ri; Ri=R0 ; Ri=R0 ; 注意注意i,j,ki,j,k的意義：的意義： i i：控制趟循環(huán)；：控制趟循環(huán)； j: j: 控制每趟中從第控制每趟中從第i i個元素到第個元素到第n n個元素選擇最小值的循環(huán)；個元素選擇最小值的循環(huán)； k:

42、 k: 用來指向本趟中到當前為止找到用來指向本趟中到當前為止找到的最小元素。的最小元素。4 4、性能分析：、性能分析： 從算法中可看出，簡單選擇排序移動從算法中可看出，簡單選擇排序移動記錄的次數(shù)較少，記錄的次數(shù)較少，最多數(shù)據(jù)移動最多數(shù)據(jù)移動3(n-1)3(n-1)次，最少次，最少0 0次。次。但關鍵碼的比較次數(shù)：但關鍵碼的比較次數(shù)： 第第1 1趟趟 (n-1) (n-1)次，次， 第第2 2趟趟 (n-2) (n-2)次，次， 第第i i趟趟 (n-i) (n-i)次次, ,（i=1i=1，2 2，n-1)n-1)依然是依然是 (n (n* *(n+1)/2(n+1)/2，所以時間復雜度仍，所

43、以時間復雜度仍為為O(n2)O(n2)。 19.4.3 19.4.3 堆排序堆排序 繼承了前面的工作繼承了前面的工作 簡單選擇排序的思想簡單，易于實現(xiàn)，但其時間性能沒有優(yōu)勢，這是因為在每趟的選擇中，沒有把前面選擇過程中的一些有用信息繼承下來，因此每趟選擇都是順序的一一進行，如果某一趟的選擇能夠把前面有用的一些信息繼承下來，則定會減少本趟的比較次數(shù)，提高排序效率，堆排序就做到了這一點。如：序列 12,36,24,85,47,30,53,191是一個小頂堆； 序列 191,47,85,24,36,53,30,16是一個大頂堆。 1.1.堆的定義堆的定義 設有設有n n個元素的序列個元素的序列 R1

44、 R1，R2R2，RnRn，當且僅，當且僅當滿足下述關系之一時，稱之為堆。當滿足下述關系之一時，稱之為堆。前者稱為小頂堆，后者稱為大頂堆。前者稱為小頂堆，后者稱為大頂堆。kik2ik2i+1kik2ik2i+1或其中i=1,2,n/2 在完全二叉樹上，雙親和左右孩子之間的編號就是i和2i、2i+1的關系。因此一個序列可以和一棵完全二叉樹對應起來，用雙親其左、右孩子之間的關系可以直觀的分析是否符合堆的特性。 如果該序列是一個堆，則對應的這棵完全二叉樹的特點是：所有分支結(jié)點的值均不小于 (或不大于)其子女的值，即每棵子樹根結(jié)點的值是最大(或最小)的。堆特點：堆頂元素是整個序列中最大(或最小)的元素

45、。8516364730532419147191243653308516大頂堆：191，47，85，24，36，53，30，162 2堆排序堆排序 堆特點：堆頂元素是整個序列中最大堆特點：堆頂元素是整個序列中最大( (或最或最小小) )的元素。的元素。 若將排序表按關鍵碼建成堆，堆頂元素就是選若將排序表按關鍵碼建成堆，堆頂元素就是選擇出的最大元素（或最?。@樣就得到擇出的最大元素（或最?。@樣就得到n n個元素中個元素中的第一個的元素。的第一個的元素。 然后，再對剩下的然后，再對剩下的n-1n-1個元素建成堆，得到個元素建成堆，得到n n個個元素中關鍵碼次大元素中關鍵碼次大 ( (或次小或次

46、小) )的元素。以此類推，如的元素。以此類推，如此反復，直到進行此反復，直到進行n-1n-1次后，排序結(jié)束，便得到一個次后，排序結(jié)束，便得到一個按關鍵碼有序的序列。稱這個過程為堆排序。按關鍵碼有序的序列。稱這個過程為堆排序。 因此，實現(xiàn)堆排序需解決兩個問題：因此，實現(xiàn)堆排序需解決兩個問題： 1. 1. 如何將如何將n n個元素的排序序列按關鍵碼建成堆（初始堆）；個元素的排序序列按關鍵碼建成堆（初始堆）； 2. 2. 怎樣將剩余的怎樣將剩余的n-1n-1個元素按其關鍵碼調(diào)整為一個新堆。個元素按其關鍵碼調(diào)整為一個新堆。19147243653308516a.初始堆輸出堆頂元素,再將最后一個元素放入堆

47、頂(為了操作簡便，將堆頂元素R1與Rn交換)。b.堆被破壞調(diào)整：根結(jié)點與左右子女較大者比較，若比根小，交換。c.右子樹不滿足堆，繼續(xù)調(diào)整 。d.到了葉子結(jié)點，調(diào)整結(jié)束，堆建成。858547471630531911647243653308519185472436533016191R1與Rn-1交換，堆被破壞。對R1與Rn-2調(diào)整。僅需調(diào)整一次，堆建成 。堆調(diào)整結(jié)束。858547471630531918530474716855319185534747168530191第二個問題的背景：第二個問題的背景： 輸出堆頂元素后，將堆底元素送入堆頂（或?qū)⒍秧斣剌敵龆秧斣睾?，將堆底元素送入堆頂（或?qū)⒍秧斣?/p>

48、素與堆底元素交換），堆可能被破壞。與堆底元素交換），堆可能被破壞。 破壞的情況僅是根結(jié)點和其左右孩子之間可能不滿足堆的破壞的情況僅是根結(jié)點和其左右孩子之間可能不滿足堆的特性，而其左右子樹仍然是局部的堆。特性，而其左右子樹仍然是局部的堆。 在這種情況下，將其在這種情況下，將其R1 RiR1 Ri整理成堆。整理成堆。 （i=n-1.1)i=n-1.1)調(diào)整方法：調(diào)整方法： 將根結(jié)點與左、右孩子中較小將根結(jié)點與左、右孩子中較小( (大頂堆為較大大頂堆為較大) )的進行交的進行交換。若與左孩子交換，則左子樹堆可能被破壞，且僅左子樹換。若與左孩子交換，則左子樹堆可能被破壞，且僅左子樹的根結(jié)點處不滿足堆的

49、性質(zhì)；若與右孩子交換，則右子樹堆的根結(jié)點處不滿足堆的性質(zhì)；若與右孩子交換，則右子樹堆可能被破壞，且僅右子樹的根結(jié)點處不滿足堆的性質(zhì)。繼續(xù)可能被破壞，且僅右子樹的根結(jié)點處不滿足堆的性質(zhì)。繼續(xù)對不滿足堆性質(zhì)的子樹進行上述操作，直到滿足了堆性質(zhì)或?qū)Σ粷M足堆性質(zhì)的子樹進行上述操作，直到滿足了堆性質(zhì)或者到葉子結(jié)點，堆被建成。者到葉子結(jié)點，堆被建成。 稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。19147243653308516a.初始堆。輸出堆頂元素,再將最后一個元素放入堆頂(為了操作簡便，將堆頂元素R1與Rn交換)。b.堆被破壞調(diào)整：根結(jié)點與左右子女較大者比較，

50、若比根大，交換c.右子樹不滿足堆，繼續(xù)調(diào)整 d.到了葉子結(jié)點，調(diào)整結(jié)束，堆建成。164724365330851912485473653301619124854736163053123. 3. 【算法【算法19-1919-19】篩選算法】篩選算法void HeapAdjust(datetype R , int s, int t)void HeapAdjust(datetype R , int s, int t) / /* *以以RsRs為根的子樹只有為根的子樹只有RsRs與其左右孩子之間與其左右孩子之間可能不滿足堆特性可能不滿足堆特性* */ / / /* *進行調(diào)整使以進行調(diào)整使以RsRs為根

51、的子樹成為大頂堆為根的子樹成為大頂堆* */ /datetype rc; /datetype rc; /* *緩沖變量緩沖變量* */ /rc=Rsrc=Rs；i=s;i=s; for(j=2 for(j=2* *i; j=t; j=2i; j=t; j=2* *j) /j) /* *沿關鍵碼較大的孩沿關鍵碼較大的孩子結(jié)點向下篩選子結(jié)點向下篩選* */ / if(jt & Rj.keyRj+1.key) if(jt & Rj.key Rj.key) break; / if(rc.key Rj.key) break; /* *不用調(diào)不用調(diào)到葉子就到位了到葉子就到位了* */ /

52、Ri=Rj; i=j; Ri=Rj; i=j; / /* *準備繼準備繼續(xù)向下調(diào)整續(xù)向下調(diào)整 * */ / Ri=rc Ri=rc； / /* *插入插入* */ / 4 4、堆排序的實現(xiàn)、堆排序的實現(xiàn) 初步的堆排序算法：初步的堆排序算法： 1 1、建成初始堆；、建成初始堆； 2 2、for (i=n;i1;i-)for (i=n;i1;i-) R1Ri; R1Ri; HeapAdjust(R,1,i-1); HeapAdjust(R,1,i-1); 再討論第一個問題：對原始排序表建初始堆的過程。 對原始序列建堆過程，就是一個反復進行篩選的過程。 仍然通過對應的完全二叉樹分析：對n個結(jié)點的完全

53、二叉樹，可以認為：以葉子為根的子樹（只有它自己）已滿足堆特性，因此從最后一個分支結(jié)點開始，把每棵子樹調(diào)整為堆，直到根結(jié)點為止，整棵樹成為堆。 最后一個分支結(jié)點是第 個結(jié)點。2n例：建堆的過程：例：建堆的過程：設初始排序序列：設初始排序序列：30 24 85 16 36 53 191 47 30 24 85 16 36 53 191 47 ，建成大頂堆。，建成大頂堆。30241636531918547a.8個結(jié)點的初始狀態(tài)。 從R4結(jié)點開始調(diào)整； b.調(diào)整結(jié)束后，以R4為根的子樹滿足堆特性。再將以R3結(jié)點為根的子樹調(diào)整為堆；30244736531918516c. 以 R3為根的子樹滿足堆特性。再

54、將以R2結(jié)點為根的子樹調(diào)整為堆；30244736 5385191161914724365385301619147243653308516以R2為根的子樹滿足堆特性。 再將以R1結(jié)點為根的子樹調(diào)整為堆d. 調(diào)整結(jié)束后，整棵樹為堆。30472436538519116可見，初始建堆的過程也是反復篩選的過程.借助于篩選算法，排序表建立初始堆的過程為： for (i=n/2;i0;i-) HeapAdjust(R,i,n);堆排序：堆排序： 對對n n個元素的序列進行堆排序，先將其建成堆，以根結(jié)點個元素的序列進行堆排序，先將其建成堆，以根結(jié)點與第與第n n個結(jié)點交換；調(diào)整前個結(jié)點交換；調(diào)整前n-1n-1

55、個結(jié)點成為堆，再以根結(jié)點與個結(jié)點成為堆，再以根結(jié)點與第第n-1n-1個結(jié)點交換；個結(jié)點交換；重復上述操作，直到整個序列有序。；重復上述操作，直到整個序列有序?！舅惴ā舅惴?9-1019-10】堆排序算法】堆排序算法void HeapSort(datetype R , int n)void HeapSort(datetype R , int n) / /* *將序列將序列R1.RnR1.Rn按堆排序方法進行排序按堆排序方法進行排序* */ /for(i=n/2; i0; i- ) for(i=n/2; i0; i- ) HeapAdjust(R, i, n); /HeapAdjust(R, i,

56、 n); /* *將序列將序列R1.RnR1.Rn建成初建成初始堆始堆 * */ /for(i=n; i1; i-)for(i=n; i1; i-) R0=R1; / R0=R1; /* * 堆頂堆頂R1R1與堆底元素與堆底元素RiRi交交換換 * */ / R1=Ri; R1=Ri; Ri=R0; Ri=R0; HeapAdjust(R,1, i-1); / HeapAdjust(R,1, i-1); /* *將將R1.Ri-1R1.Ri-1重新重新調(diào)整為堆調(diào)整為堆* */ / 5 5、性能分析：、性能分析： 設樹高為設樹高為k k，由二叉樹的性質(zhì)知：，由二叉樹的性質(zhì)知：k=k=log2nl

57、og2n +1+1。從根到葉的篩選，關鍵碼比較次數(shù)至多為。從根到葉的篩選，關鍵碼比較次數(shù)至多為2(k-1)2(k-1)次，移動記錄至多次，移動記錄至多k k次。共次。共n-1n-1次。次。因此堆排序最壞情況下，時間復雜度為因此堆排序最壞情況下，時間復雜度為O(nlog2n)O(nlog2n)。第第1919章章 排序排序19.1 基本概念19.2 插入排序19.3 交換排序 19.4 選擇排序19.5 歸并排序19.6 分配排序（基數(shù)排序）19.5 19.5 歸并排序歸并排序 歸并排序的思想是將幾個相鄰的有歸并排序的思想是將幾個相鄰的有序表合并成一個總的有序表，本節(jié)主要介紹序表合并成一個總的有序

58、表，本節(jié)主要介紹2-2-路歸并排序。路歸并排序。1 1兩個有序表的合并兩個有序表的合并 二路歸并排序的基本操作是將兩個有二路歸并排序的基本操作是將兩個有序表合并為一個有序表。序表合并為一個有序表。 R: 25 38 46 75 R: 25 38 46 75 18 37 40 46 78 80 18 37 40 46 78 80 s m s m m+1 tm+1 t R1: 18 25 37 38 46 46 R1: 18 25 37 38 46 46 75 78 80 75 78 80 s s t t【算法19-11】兩個有序表的合并void Merge(datatype R , dataty

59、pe R1 , int s, int m , int t) /*設兩個有序子表Rs.Rm和Rm+1.Rt */ /*將兩個有序子表合并為一個有序表R1s.R1t*/ i=s; j=m+1; k=s; while (i=m&j=t) if(Ri.keyRj.key) R1k+=Ri+; else R1k+=Rj+; while (i=m) R1k+=Ri+; while (j=t) R1k+=Rj+;要注意：該合并算法的要求是兩個有序子表是相鄰的，即Rs.Rm和Rm+1.Rt。 2. 2-2. 2-路歸并算法路歸并算法 2-路歸并的基本思想是：只有1個元素的表總是有序的，所以將排序表R1

60、.n，看作是n個長度為len=1的有序子表，對相鄰的兩個有序子表兩兩合并到R11.n，使之生成表長len=2的有序表；再進行兩兩合并到R1.n中，直到最后生成表長len=n的有序表。這個過程需要log2n趟。56 47 619 48 27 198 56 519 38 28 6647 56 48 619 27 198 56 519 28 38 6647 48 56 619 27 56 519 198 28 38 6627 47 48 56 56 519 619 198 28 38 6627 28 38 47 48 56 56 519 66 619 198【算法19-12】一趟歸并算法void MergePass(datatype R , data