10￥-ten(天津科技大學)

第十章內部排序10.1排序的基本概念10.2插入排序10.3

快速排序10.4

選擇排序10.5歸并排序10.6基數排序(略)10.7各種內部排序方法的比較討論10/11/20241第十章內部排序10.1

排序的基本概念將一組雜亂無序的數據按一定的規(guī)律順次排列起來叫做排序(sort)。對一批記錄的排序，應該指定是根據記錄中哪個域的數據進行排列。這個作為排序依據的數據域我們稱之為關鍵字(key)。本章討論的排序均為按遞增順序排序，并假定要排序的記錄均已存儲在一個一維數組中。10/11/20242第十章內部排序該一維數組定義如下：#defineMAXITEM100structrecord{

KeyTypekey;/*關鍵字*/

ElemTypedata;/*其他域*/}sqlist[MAXITEM];10/11/20243第十章內部排序大多數的排序方法數據是存儲在內存中，并在內存中加以處理的，這種排序方法叫內部排序。如果在排序過程中，數據的主要部分存放在外存儲器中（如軟盤、硬盤、磁帶），借助內存進行內、外存數據交換，逐步排列記錄之間的順序，則稱之為外部排序。一種排序方法，如果排序后具有相同關鍵字的記錄仍維持排序之前的相對次序，則稱之為穩(wěn)定的，否則稱為不穩(wěn)定的。10/11/20244第十章內部排序內部排序方法分類按所用策略不同，可分五類：插入排序、交換排序、選擇排序、歸并排序和基數排序。按所需工作量，可分為三類：簡單排序O(n2)、先進排序O(nlogn)、基數排序O(d*n)。內部排序兩種基本操作：1.比較兩個關鍵字的大??；2.將記錄從一個位置移動到另一個位置。10/11/20245第十章內部排序10.2

直接插入排序直接插入排序的基本思想是：從數組的第二個單元開始，依次從原始數據中取出數據，并將其插入到數組中該單元之前的已排好序的序列中合適的位置處。直接插入算法需要經過（n-1）趟插入過程。如果數據恰好應插入到序列的最后端，則不需移動數據，可節(jié)省時間，所以若原始數據大體有序，此算法可以有較快的運算速度。動畫演示10/11/20246第十章內部排序直接插入排序圖10/11/20247第十章內部排序直接插入排序算法voidinsertsort(sqlistr,intn){

inti,j;for(i=2;i<=n;i++){r[0]=r[i];/*r[0]用于暫時存放待插入的元素*/j=i-1;/*j為待比較元素下標，初始時指向待插入元素前一個單元*/10/11/20248第十章內部排序直接插入排序算法續(xù)

while(r[0].key<r[j].key){r[j+1]=r[j];j--;}r[j+1]=r[0];/*在j+1位置插入r[0]*/}}簡單插入排序的時間復雜性是O(n2)(平均約為n2/4)。對于有相同關鍵字記錄的情況，此算法是穩(wěn)定的。10/11/20249第十章內部排序其他插入排序折半插入排序：在有序表中進行查找和插入，從而查找操作可利用折半查找來實現，由此進行的插入排序稱為折半插入排序。希爾排序：對直接插入排序進行改進得到的一種插入排序方法。基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。10/11/202410第十章內部排序冒泡排序冒泡排序是一種簡單而且容易理解的排序方法，它和氣泡從水中不斷往上冒的情況有些類似。其基本思想是對存放原始數據的數組，按從后往前的方向進行多次掃描，每次掃描稱為一趟（pass）。當發(fā)現相鄰兩個數據的次序與排序要求的“遞增次序”不符合時，即將這兩個數據進行互換。這樣，較小的數據就會逐單元向前移動，好象氣泡向上浮起一樣。動畫演示10/11/202411第十章內部排序冒泡排序過程圖10/11/202412第十章內部排序需掃描的趟數視原始數據最初的排列次序的不同而不同，最壞的情況要進行（n-1）趟掃描，一般常常少于(n-1)趟即可完成?？梢栽O置一個標志flag用來指示掃描中有沒有進行數據交換，每趟掃描開始前將其置1。當這趟掃描至少出現一次互換時，將其置0。如某趟掃描后flag仍為1，說明此趟掃描已無數據互換，則排序結束，不必再繼續(xù)掃描了。10/11/202413第十章內部排序冒泡排序算法voidbubblesort(sqlistr,intn){

inti,j,flag;for(i=1;i<=n-1;i++){flag=1;for(j=i;j<=n-1;j++)if(r[j+1].key<r[j].key)10/11/202414第十章內部排序冒泡排序算法續(xù)

{flag=0;r[0]=r[j];/*r[0]用于暫時存放元素*/r[j]=r[j+1];r[j+1]=r[0];}if(flag==1)return;}}10/11/202415第十章內部排序冒泡排序算法分析冒泡排序算法的優(yōu)點是比較容易理解，且當原始數據大體符合要求的次序時，運算速度較快。但它不是高效率的算法，在最壞的情況下，如果輸入數據的次序與排序要求的次序完全相反，冒泡排序需要進行n(n-1)/2次比較和n(n-1)3/2次移動，其數量級均為O(n2)。對于有相同關鍵字記錄的情況，冒泡排序是穩(wěn)定的。10/11/202416第十章內部排序快速排序快速排序是由冒泡排序改進而得到的，又稱為分區(qū)交換排序，是目前內部排序中速度較快的方法?；舅枷耄涸诖判虻膎個數據中任取一個數據（通常取第一個數據），把該數據放入合適的位置，使得數據序列被此數據分割成兩部分，所有比該數據小的放置在前一部分，所有比它大的放置在后一部分，即該數據排在這兩部分的中間。此數據在進一步的運算過程中不必再動，以后的排序運算只需在劃分成的每部分里進行，兩部分之間也不會再有數據交換。10/11/202417第十章內部排序第一次劃分以后，再用相同的算法對劃成的兩部分分別進行類似的運算，即從每一部分中任選一個數據將其劃分成更小的兩部分。依此遞歸地做下去，直至每個小部分中的數據個數為一個，排序過程就結束了。下頁圖所示為一個快速排序的例子，圖中的方括號表示待排序部分，下面有橫線的數據則是某次進行劃分時所選的數據。10/11/202418第十章內部排序快速排序10/11/202419第十章內部排序一趟快速排序采用從兩頭向中間掃描的辦法。假設原始數據已存于一個一維數組r中，具體的做法是：設兩個指示器i和j，初始時i指向數組中的第一個數據，j指向最末一個數據。i先不動使j逐步前移，每次對二者所指的數據進行比較，當遇到r[i]大于r[j]的情況時，就將二者對調位置；然后令j固定使i逐步后移做數據比較，當遇到r[i]大于r[j]時，又進行位置對調；然后又是i不動使j前移作數據比較；……；如此反復進行，直至i與j兩者相遇為止。10/11/202420第十章內部排序下頁圖所示是第一趟進行劃分時的比較和互換過程。圖中括號中的數據表示正進行比較的兩個數據，左面一個的下標為i，右面一個的下標為j。最后一行只有一個括號，說明i與j相等了，此單元即是數據13的最終位置。動畫演示10/11/202421第十章內部排序一趟數據比較和互換10/11/202422第十章內部排序快速排序分析快速排序的時間復雜性為O(nlogn)，對n較大的情況，這種算法是平均情況速度最快的排序算法，但當n很小時，此方法往往比其他簡單排序方法還要慢?？焖倥判蚴遣环€(wěn)定的，對于有相同關鍵字的記錄，排序以后次序可能會顛倒。10/11/202423第十章內部排序例已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結果。10/11/202424第十章內部排序例解答解:快速排序各趟的結果如下:

[602031154455612003080150429][292031154455430]60[8015020061][42051]29[44553130]60[61]80[200150][1]4[520]29[3031]44[55]606180150[200]145[20]2930[31]445560618015020014520293031445560618015020010/11/202425第十章內部排序簡單選擇排序簡單選擇排序的作法是：第一趟掃描所有數據，選擇其中最小的一個與第一個數據互換；第二趟從第二個數據開始向后掃描，選擇最小的與第二個數據互換；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。在每一趟掃描數據時，用一個整型變量跟蹤當前最小數據的位置，然后，第i趟掃描只需將該位置的數據與第i個數據交換即可。這樣掃描n-1次，處理數據的個數從n每次逐漸減1，每次掃描結束時才可能有一次交換數據的操作。10/11/202426第十章內部排序簡單選擇排序圖10/11/202427第十章內部排序簡單選擇排序分析簡單選擇排序在(n-1)趟掃描中共需進行n(n-1)/2次比較，最壞情況下的互換次數為(n-1)，整個算法的時間復雜性為O(n2)。簡單選擇排序簡單并且容易實現，適宜于n較小的情況。簡單選擇排序是不穩(wěn)定的排序算法。10/11/202428第十章內部排序簡單選擇排序算法voidselectsort(sqlistr,intn){

inti,j,min;for(i=1;i<=n-1;i++){min=i;/*用min指出每一趟在無序區(qū)范圍內的最小元素*/10/11/202429第十章內部排序簡單選擇排序算法續(xù)

for(j=i+1;j<=n-1;j++)if(r[j].key<r[min].key)min=j;r[0]=r[i];/*r[0]用于暫時存放元素*/r[i]=r[min];r[min]=r[0];}}10/11/202430第十章內部排序堆排序堆排序（HeapSort）是利用二叉樹的一種排序方法。堆（Heap）是與二叉排序樹不同的一種二叉樹，它的定義為：一個完全二叉樹，它的每個結點對應于原始數據的一個元素，且規(guī)定如果一個結點有兒子結點，此結點數據必須大于或等于其兒子結點數據。由于堆是完全二叉樹，采用將結點順序編號存入一維數組中的表示法比鏈接表示法節(jié)省存儲空間，也便于計算。10/11/202431第十章內部排序設某堆的結點數共有n個，順序將它們存入一維數組r中。根據順序表示二叉樹的特點，除下標為1的結點是整棵樹的根結點而沒有父結點以外，其余下標為j的結點（2≤j≤n）都有父結點，父結點的下標為i=。故堆的條件可以表示成：

r[i]≥r[j]當2≤j≤n且i=10/11/202432第十章內部排序堆及其順序存儲結構10/11/202433第十章內部排序堆排序（續(xù)）由堆的定義可知，其根結點（即在數組中下標為1的結點）具有最大的數字，堆排序就是利用這一特點進行的。實現堆排序需要解決二個問題：1.對一組待排序的數據，先將它們構建成一個堆，輸出堆頂的最大數據；2.將余下的n-1個數據再構建堆，輸出具有次小值的數據；如此反復進行下去，直至全部數據都輸出，就可以得到排好序的元素序列。10/11/202434第十章內部排序構建堆一般構建堆是采用一種稱為篩選（sift）的算法。這種方法是將一個無序數據序列的構建堆的過程看作一個反復“篩選”的過程。設原始數據為7，10，13，15，4，20，19，8（數據個數n=8）。首先把這些數據按任意次序置入完全二叉樹的各結點中，由于原始數據的次序是任意的，此樹一般不符合堆的條件，需要用篩選運算進行調整。10/11/202435第十章內部排序篩選運算是從最末尾結點的父結點開始，向前逐結點進行，直至篩選完根結點即形成此堆。篩每個結點時，將其數值與其兩個兒子結點中數值較大者進行比較，如小于該兒子結點數值，則與之進行交換，互換后又將它看成父結點，再與下一層的兒子結點進行比較，如此做下去，直至不小于其兒子結點的數值，或已篩到葉結點而不再有兒子結點了，此數據的篩選運算即完成。10/11/202436第十章內部排序用篩選算法構建堆10/11/202437第十章內部排序10/11/202438第十章內部排序10/11/202439第十章內部排序利用堆排序利用堆進行排序的方法是從根結點逐個取出數據，每次將新的再提到根結點，如此反復進行，直到堆只剩下一個結點為止。為了節(jié)約存儲空間，要求排序得到的有序數據序列仍存放于原數組中，故將從根結點取出的數據由數組的末端起逐單元存放。每存放一個數據，同時將原來在該單元的數據換到根結點。但這樣互換后一般會破壞堆的條件，因此需要對根結點再做依次篩選運算，即令v=1再調用一次函數sift，就又可形成新的滿足條件的堆。動畫演示10/11/202440第十章內部排序堆排序圖10/11/202441第十章內部排序10/11/202442第十章內部排序10/11/202443第十章內部排序10/11/202444第十章內部排序10/11/202445第十章內部排序堆排序算法分析整個堆排序過程的時間復雜性是n與h的乘積數量級，考慮到h與n的關系，其復雜性為O(nlogn)。堆排序適合于待排序的數據較多的情況，對于存在相同關鍵字的記錄的情況，堆排序是不穩(wěn)定的。10/11/202446第十章內部排序歸并排序歸并是指將若干個已排序好的有序表合并成一個有序表。兩個有序表的歸并稱為二路歸并。歸并排序就是利用歸并過程，開始時先將n個數據看成n個長度為1的已排好序的表，將相鄰的表成對合并，得到長度為2的（n/2）個有序表，每個表含有2個數據；進一步再將相鄰表成對合并，得到長度為4的（n/4）個有序表；……；如此重復做下去，直至所有數據均合并到一個長度為n的有序表為止，就完成了排序。動畫演示10/11/202447第十章內部排序二路歸并排序10/11/202448第十章內部排序下面是將兩個有序表歸并的函數Merge，設待歸并的兩個表存于數組r中，其中一個的數據安排在下標從m到n單元中，另一個安排在下標從（n+1）到h單元中，歸并后得到的一個有序表，存入輔助數組r2中。歸并過程是依次比較這兩個有序表中相應的數據，按照“取小”原則復制到r2之中即可。10/11/202449第十章內部排序兩個有序表的歸并圖10/11/202450第十章內部排序上面的函數只是歸并兩個有序表,在進行二路歸并的每一趟歸并過程中是將多對相鄰的表進行歸并?，F在討論一趟的歸并。設已將數組r中的n個數據分成一對對長度為s的有序表，要求將這些表兩兩歸并，歸并成一些長度為2s的有序表，并把結果置入輔助數組r2中。10/11/202451第十章內部排序如果n不是2s的整數倍，雖然前面進行歸并的表長度均為s，最后不可能再剩下一對長度都是s的表，此時可有兩種情況：一種情況是剩下一個長度為s的表和一個長度小于s的表，由于上述的歸并函數merge并不要求待歸并的兩個表必須長度相同，仍可將二者歸并，只是歸并后的表的長度小于其它表的長度2s；再一種情況是只剩下一個表，它的長度小于或等于s，由于沒有另一個表與它歸并，只能將它直接抄到數組r2中，準備參加下一趟的歸并。10/11/202452第十章內部排序歸并排序分析二路歸并排序的時間復雜性為O(nlogn)，與堆排序和快速排序平均情況的時間復雜性是相同數量級。歸并排序是穩(wěn)定的排序方法。10/11/202453第十章內部排序例已知序列{26,5,77,1,61,11,59,15,48,19}寫出采用歸并排序算法排序的每一趟的結果。解:歸并排序各趟的結果如下:[26][5][77][1][61][11][59][15][48][19][526][177][1161][1559][1948][152677][11155961][1948][15111526596177][1948][151115192648596177]10/11/202454第十章內部排序各種排序方法比較直接插入排序冒泡排序快速排序簡單選擇排序堆排序歸并排序時間復雜性空間復雜性穩(wěn)定性算法簡單性待排序記錄數的大小記錄本身信息量的大小10/11/202455第十章內部排序各種排序方法比較從時間復雜性看，直接插入排序、直接選擇排序和冒泡排序這三種簡單排序方法屬于一類，其時間復雜性為O(n2);堆排序、快速排序和歸并排序屬于第二類，其時間復雜性為O(nlog2n)。進一步分析可知：在最好情況下，直接插入排序和冒泡排序最快；在平均情況下，快速排序最快；在最壞情況下，堆排序和歸并排序最快。10/11/202456第十章內部排序各種排序方法比較從空間復雜性看，所有排序方法可歸為三類，歸并排序單獨屬于一類，空間復雜性為O(n)；快速排序方法空間復雜性為O(log2n)(但在最壞情況下為O(n))；其它排序方法歸為第三類，其空間復雜性為O(1)。由此可知，第三類算法的空間復雜性最好，第二類次之，第一類最差。從穩(wěn)定性看，所有排序方法分為二類，一類是穩(wěn)定的，它包括直接插入排序，起泡