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

第十章內(nèi)部排序10.1排序的基本概念10.2插入排序10.3

快速排序10.4

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

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

KeyTypekey;/*關(guān)鍵字*/

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

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

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

while(r[0].key<r[j].key){r[j+1]=r[j];j--;}r[j+1]=r[0];/*在j+1位置插入r[0]*/}}簡單插入排序的時間復(fù)雜性是O(n2)(平均約為n2/4)。對于有相同關(guān)鍵字記錄的情況，此算法是穩(wěn)定的。10/11/20249第十章內(nèi)部排序其他插入排序折半插入排序：在有序表中進行查找和插入，從而查找操作可利用折半查找來實現(xiàn)，由此進行的插入排序稱為折半插入排序。希爾排序：對直接插入排序進行改進得到的一種插入排序方法?；舅枷胧牵合葘⒄麄€待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。10/11/202410第十章內(nèi)部排序冒泡排序冒泡排序是一種簡單而且容易理解的排序方法，它和氣泡從水中不斷往上冒的情況有些類似。其基本思想是對存放原始數(shù)據(jù)的數(shù)組，按從后往前的方向進行多次掃描，每次掃描稱為一趟（pass）。當(dāng)發(fā)現(xiàn)相鄰兩個數(shù)據(jù)的次序與排序要求的“遞增次序”不符合時，即將這兩個數(shù)據(jù)進行互換。這樣，較小的數(shù)據(jù)就會逐單元向前移動，好象氣泡向上浮起一樣。動畫演示10/11/202411第十章內(nèi)部排序冒泡排序過程圖10/11/202412第十章內(nèi)部排序需掃描的趟數(shù)視原始數(shù)據(jù)最初的排列次序的不同而不同，最壞的情況要進行（n-1）趟掃描，一般常常少于(n-1)趟即可完成?？梢栽O(shè)置一個標志flag用來指示掃描中有沒有進行數(shù)據(jù)交換，每趟掃描開始前將其置1。當(dāng)這趟掃描至少出現(xiàn)一次互換時，將其置0。如某趟掃描后flag仍為1，說明此趟掃描已無數(shù)據(jù)互換，則排序結(jié)束，不必再繼續(xù)掃描了。10/11/202413第十章內(nèi)部排序冒泡排序算法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第十章內(nèi)部排序冒泡排序算法續(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第十章內(nèi)部排序冒泡排序算法分析冒泡排序算法的優(yōu)點是比較容易理解，且當(dāng)原始數(shù)據(jù)大體符合要求的次序時，運算速度較快。但它不是高效率的算法，在最壞的情況下，如果輸入數(shù)據(jù)的次序與排序要求的次序完全相反，冒泡排序需要進行n(n-1)/2次比較和n(n-1)3/2次移動，其數(shù)量級均為O(n2)。對于有相同關(guān)鍵字記錄的情況，冒泡排序是穩(wěn)定的。10/11/202416第十章內(nèi)部排序快速排序快速排序是由冒泡排序改進而得到的，又稱為分區(qū)交換排序，是目前內(nèi)部排序中速度較快的方法。基本思想：在待排序的n個數(shù)據(jù)中任取一個數(shù)據(jù)（通常取第一個數(shù)據(jù)），把該數(shù)據(jù)放入合適的位置，使得數(shù)據(jù)序列被此數(shù)據(jù)分割成兩部分，所有比該數(shù)據(jù)小的放置在前一部分，所有比它大的放置在后一部分，即該數(shù)據(jù)排在這兩部分的中間。此數(shù)據(jù)在進一步的運算過程中不必再動，以后的排序運算只需在劃分成的每部分里進行，兩部分之間也不會再有數(shù)據(jù)交換。10/11/202417第十章內(nèi)部排序第一次劃分以后，再用相同的算法對劃成的兩部分分別進行類似的運算，即從每一部分中任選一個數(shù)據(jù)將其劃分成更小的兩部分。依此遞歸地做下去，直至每個小部分中的數(shù)據(jù)個數(shù)為一個，排序過程就結(jié)束了。下頁圖所示為一個快速排序的例子，圖中的方括號表示待排序部分，下面有橫線的數(shù)據(jù)則是某次進行劃分時所選的數(shù)據(jù)。10/11/202418第十章內(nèi)部排序快速排序10/11/202419第十章內(nèi)部排序一趟快速排序采用從兩頭向中間掃描的辦法。假設(shè)原始數(shù)據(jù)已存于一個一維數(shù)組r中，具體的做法是：設(shè)兩個指示器i和j，初始時i指向數(shù)組中的第一個數(shù)據(jù)，j指向最末一個數(shù)據(jù)。i先不動使j逐步前移，每次對二者所指的數(shù)據(jù)進行比較，當(dāng)遇到r[i]大于r[j]的情況時，就將二者對調(diào)位置；然后令j固定使i逐步后移做數(shù)據(jù)比較，當(dāng)遇到r[i]大于r[j]時，又進行位置對調(diào)；然后又是i不動使j前移作數(shù)據(jù)比較；……；如此反復(fù)進行，直至i與j兩者相遇為止。10/11/202420第十章內(nèi)部排序下頁圖所示是第一趟進行劃分時的比較和互換過程。圖中括號中的數(shù)據(jù)表示正進行比較的兩個數(shù)據(jù)，左面一個的下標為i，右面一個的下標為j。最后一行只有一個括號，說明i與j相等了，此單元即是數(shù)據(jù)13的最終位置。動畫演示10/11/202421第十章內(nèi)部排序一趟數(shù)據(jù)比較和互換10/11/202422第十章內(nèi)部排序快速排序分析快速排序的時間復(fù)雜性為O(nlogn)，對n較大的情況，這種算法是平均情況速度最快的排序算法，但當(dāng)n很小時，此方法往往比其他簡單排序方法還要慢?？焖倥判蚴遣环€(wěn)定的，對于有相同關(guān)鍵字的記錄，排序以后次序可能會顛倒。10/11/202423第十章內(nèi)部排序例已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結(jié)果。10/11/202424第十章內(nèi)部排序例解答解:快速排序各趟的結(jié)果如下:

[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èi)部排序簡單選擇排序簡單選擇排序的作法是：第一趟掃描所有數(shù)據(jù)，選擇其中最小的一個與第一個數(shù)據(jù)互換；第二趟從第二個數(shù)據(jù)開始向后掃描，選擇最小的與第二個數(shù)據(jù)互換；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。在每一趟掃描數(shù)據(jù)時，用一個整型變量跟蹤當(dāng)前最小數(shù)據(jù)的位置，然后，第i趟掃描只需將該位置的數(shù)據(jù)與第i個數(shù)據(jù)交換即可。這樣掃描n-1次，處理數(shù)據(jù)的個數(shù)從n每次逐漸減1，每次掃描結(jié)束時才可能有一次交換數(shù)據(jù)的操作。10/11/202426第十章內(nèi)部排序簡單選擇排序圖10/11/202427第十章內(nèi)部排序簡單選擇排序分析簡單選擇排序在(n-1)趟掃描中共需進行n(n-1)/2次比較，最壞情況下的互換次數(shù)為(n-1)，整個算法的時間復(fù)雜性為O(n2)。簡單選擇排序簡單并且容易實現(xiàn)，適宜于n較小的情況。簡單選擇排序是不穩(wěn)定的排序算法。10/11/202428第十章內(nèi)部排序簡單選擇排序算法voidselectsort(sqlistr,intn){

inti,j,min;for(i=1;i<=n-1;i++){min=i;/*用min指出每一趟在無序區(qū)范圍內(nèi)的最小元素*/10/11/202429第十章內(nèi)部排序簡單選擇排序算法續(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第十章內(nèi)部排序堆排序堆排序（HeapSort）是利用二叉樹的一種排序方法。堆（Heap）是與二叉排序樹不同的一種二叉樹，它的定義為：一個完全二叉樹，它的每個結(jié)點對應(yīng)于原始數(shù)據(jù)的一個元素，且規(guī)定如果一個結(jié)點有兒子結(jié)點，此結(jié)點數(shù)據(jù)必須大于或等于其兒子結(jié)點數(shù)據(jù)。由于堆是完全二叉樹，采用將結(jié)點順序編號存入一維數(shù)組中的表示法比鏈接表示法節(jié)省存儲空間，也便于計算。10/11/202431第十章內(nèi)部排序設(shè)某堆的結(jié)點數(shù)共有n個，順序?qū)⑺鼈兇嫒胍痪S數(shù)組r中。根據(jù)順序表示二叉樹的特點，除下標為1的結(jié)點是整棵樹的根結(jié)點而沒有父結(jié)點以外，其余下標為j的結(jié)點（2≤j≤n）都有父結(jié)點，父結(jié)點的下標為i=。故堆的條件可以表示成：

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