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

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

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

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

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

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

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

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