數(shù)據(jù)結(jié)構(gòu)之排序課件(與“排序”有關(guān)文檔共83張)

第九章排序知識(shí)點(diǎn)排序的基本概念三種簡(jiǎn)單的排序方法：冒泡排序、直接選擇排序、簡(jiǎn)單插入排序堆排序快速排序歸并排序基數(shù)排序難點(diǎn)堆排序快速排序歸并排序基數(shù)排序第1頁(yè)，共83頁(yè)。要求熟練掌握以下內(nèi)容：熟悉各種內(nèi)部排序方法的基本思想和特點(diǎn)各種排序方法的優(yōu)缺點(diǎn)、時(shí)、空性能和適用場(chǎng)合熟悉并掌握三種簡(jiǎn)單排序算法、快速排序算法和堆排序算法了解以下內(nèi)容：二路歸并排序算法基數(shù)排序算法第2頁(yè)，共83頁(yè)。排序的歷史大約公元前300年，在愛琴島上發(fā)現(xiàn)了若干個(gè)表,給出了宗教中的人名.這些表按字母排列,但只按頭一個(gè)字母排列.(單個(gè)字母的字符排序)約公元前200年,巴比倫人艾娜基比特-安奴(Inakibit-Anu),用陶土做的,含有500個(gè)以上高精度的六十進(jìn)制數(shù)及其倒數(shù)表,并把它排列成詞典順序.(數(shù)字排序)在許多圣經(jīng)贊美詩(shī)中,遵循一個(gè)嚴(yán)格的字母序列,頭一個(gè)詩(shī)句以a開始,第二個(gè)詩(shī)句以b開始,……有助于記憶.(單個(gè)字母的字符排序)第3頁(yè)，共83頁(yè)。公元134-135年,某些希臘文稿包含一些分類賬的片斷,他列出了按頭兩個(gè)字母排序的納稅人的名字.……對(duì)于今天排序技術(shù)起源的探索,是19世紀(jì)末發(fā)明的排序機(jī)器.1880年,美國(guó)人口普查,數(shù)據(jù)處理成為令人頭痛的問(wèn)題—無(wú)法在當(dāng)年完成.赫爾曼.霍勒里斯(HermanHollerith),一位人口統(tǒng)計(jì)局的20歲的職員,發(fā)明了一臺(tái)巧妙的制表機(jī),用100臺(tái)這樣的制表機(jī),成功的完成了人口普查的統(tǒng)計(jì)問(wèn)題.……第4頁(yè)，共83頁(yè)。計(jì)算機(jī)的誕生和發(fā)展促進(jìn)了排序技術(shù)的發(fā)展1945年,馮.諾依曼(VonNeuman)編制了一個(gè)用于內(nèi)部合并排序的程序---這也是存儲(chǔ)程序計(jì)算機(jī)的第一個(gè)程序.……如果我能把過(guò)去幾年內(nèi)所產(chǎn)生的大量的關(guān)于排序的材料的要旨都加以排序,編排出次序來(lái),那我就心滿意足了.----J.C.霍斯金(J.C.Heskin1955)第5頁(yè)，共83頁(yè)。排序的概念將一組雜亂無(wú)序的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)叫做排序(sort)。關(guān)鍵字(key)：對(duì)一批記錄的排序，應(yīng)該指定是根據(jù)記錄中哪個(gè)字段進(jìn)行排列。這個(gè)作為排序依據(jù)的字段稱之為關(guān)鍵字。約定：本章討論的排序均為按遞增順序排序，并假定要排序的記錄均已存儲(chǔ)在一個(gè)一維數(shù)組中。第6頁(yè)，共83頁(yè)。記錄的形式定義為：Typedefstructrectype{KeyTypekey;/*關(guān)鍵字*/itemTypeotherinfo;/*其他域*/}rectype;第7頁(yè)，共83頁(yè)。大多數(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)定的。返回第8頁(yè)，共83頁(yè)。三種簡(jiǎn)單排序算法第9頁(yè)，共83頁(yè)。1直接插入排序基本思想：設(shè)有n個(gè)待排序的記錄，順序存放在數(shù)組R[1—n]中。設(shè)前I-1個(gè)記錄已經(jīng)有序，從第I個(gè)記錄開始和前I-1個(gè)記錄的關(guān)鍵字比較，找到合適的位置插入。直接插入算法需要經(jīng)過(guò)（n-1）趟插入過(guò)程。如果數(shù)據(jù)恰好應(yīng)插入到序列的最后端，則不需移動(dòng)數(shù)據(jù)，可節(jié)省時(shí)間，所以若原始數(shù)據(jù)大體有序，此算法可以有較快的運(yùn)算速度。第10頁(yè)，共83頁(yè)。圖直接插入排序第11頁(yè)，共83頁(yè)。直接插入排序算法voidinsertsort(rectyper[],intn){inti,j;for(i=2;i<=n;i++){r[0]=r[i];/*r[0]用于暫時(shí)存放待插入的元素*/j=i-1;/*j為待比較元素下標(biāo)while(r[0].key<r[j].key){r[j+1]=r[j];/*記錄后移*/j--;}r[j+1]=r[0];/*在j+1位置插入r[0]*/}}第12頁(yè)，共83頁(yè)。性能分析最好的情況：當(dāng)待排序的記錄已經(jīng)有序時(shí)，比較次數(shù)為n-1；移動(dòng)次數(shù)為2（n-1）最壞的情況：當(dāng)待排序的記錄按遞減排列時(shí)，比較次數(shù)為2+3+……+n=(n-1)(n+2)/2移動(dòng)次數(shù)為(I+1)=(n-1)(n+4)/2取其平均值：比較次數(shù)和移動(dòng)次數(shù)均為n*n/2，時(shí)間復(fù)雜度為O（n*n），空間復(fù)雜度為O（1）。第13頁(yè)，共83頁(yè)。性能分析R[0]的使用：把R[I]放在R[0]中，R[I]的位置用來(lái)向后移動(dòng)記錄比較過(guò)程中，又防止下標(biāo)j出界，起到了監(jiān)視哨的作用。可以看出，該算法是穩(wěn)定的。第14頁(yè)，共83頁(yè)。2.冒泡排序基本思想：首先將R[1]和R[2]比較，若逆序，則交換R[1]和R[2]，然后比較R[2]和R[3],…..直到第n-1個(gè)記錄和第n個(gè)記錄比較，經(jīng)過(guò)這一趟比較，最大的記錄被放在最后一個(gè)位置上；然后對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，則具有次大關(guān)鍵字的記錄被放在第n-1個(gè)記錄的位置上；重復(fù)以上過(guò)程，直到?jīng)]有記錄交換為止。第15頁(yè)，共83頁(yè)。圖冒泡排序過(guò)程第16頁(yè)，共83頁(yè)。

冒泡排序算法voidbubblesort(r[],n){inti,j;for(i=1;i<n;i++){for(j=1;j<=n-i;j++)if(r[j+1].key<r[j].key)r[j]r[j+1];}}

第17頁(yè)，共83頁(yè)。修正后的冒泡排序算法voidbubblesort(r[],n){inti,j,flag;for(i=1;i<n;i++){flag=1;for(j=1;j<=n-i;j++)if(r[j+1].key<r[j].key){flag=0;r[j]r[j+1];}if(flag==1)return;}}第18頁(yè)，共83頁(yè)。Flag的作用用來(lái)指示掃描中有沒(méi)有進(jìn)行數(shù)據(jù)交換，每趟掃描開始前將其置1。當(dāng)這趟掃描至少出現(xiàn)一次互換時(shí)，將其置0。如某趟掃描后flag仍為1，說(shuō)明此趟掃描已無(wú)數(shù)據(jù)互換，則排序結(jié)束，不必再繼續(xù)掃描了。第19頁(yè)，共83頁(yè)。冒泡排序算法分析最好情況：比較次數(shù)：n-1交換次數(shù)：0最壞情況比較次數(shù)：n(n-1)/2交換次數(shù):n(n-1)/2時(shí)間復(fù)雜度：o(n*n)冒泡排序是穩(wěn)定的。第20頁(yè)，共83頁(yè)?；舅枷耄旱谝惶藦腞[0]—R[n-1]中最小的記錄，并R[1]交換；第二趟從R[2]—R[n]選擇最小的J記錄并與R[2]交換；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。在每一趟掃描時(shí)，用一個(gè)整型變量i跟蹤當(dāng)前最小元素的位置。第i趟掃描只需將該位置的元素與第i個(gè)元素交換即可。這樣掃描n-1次，處理元素的個(gè)數(shù)從n逐次減1。第21頁(yè)，共83頁(yè)。圖簡(jiǎn)單選擇排序第22頁(yè)，共83頁(yè)。簡(jiǎn)單選擇排序算法voidselectsort(r[],n){inti,j,k;for(i=1;i<=n-1;i++){k=i;/*k始終記住到目前為止最小者的下標(biāo)

for(j=i+1;j<=n;j++)if(r[j].key<r[k].key)k=j;if(i!=k)r[i]r[k];}}

第23頁(yè)，共83頁(yè)。簡(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)定的排序算法。第24頁(yè)，共83頁(yè)。直接插入排序和簡(jiǎn)單選擇排序的比較直接插入1.輸入序列是未知的；2.排序結(jié)束之前，不能確定任何元素的最終位置。簡(jiǎn)單選擇1.輸入是已知的；2.每一趟排序結(jié)束后，所選擇的元素都都放在了最終的位置上。第25頁(yè)，共83頁(yè)。9.3希爾排序希爾（ShellSort)又稱“縮小增量排序”，它也時(shí)一種插入排序類的方法。基本思想：把整個(gè)文件分成若干個(gè)較小的子文件，對(duì)每個(gè)子文件進(jìn)行直接插入排序；在文件的記錄達(dá)到基本有序時(shí)，再對(duì)整個(gè)文件進(jìn)行一次直接插入排序。例：9138251371411第26頁(yè)，共83頁(yè)。希爾排序算法Voidshellsort(r[],n,dk[],t)/*dk[]增量數(shù)組/*t:增量數(shù)組的元素?cái)?shù){for(i=1;i<=t;i++)shellpass(r[],n,dk[i]);/*以dk[i]為增量進(jìn)/*行一趟希爾排序}

第27頁(yè)，共83頁(yè)。Voidshellpass(r[],n,d)/*一趟希爾排序*/{inti,k;for(i=d+1,i<=n;i++){r[0]=r[i];k=i-d;while((k>0)&&(r[0].key<r[k].key)){r[k+d}.key=r[k].key;k=k-d;}r[k+d]=r[0];}}第28頁(yè)，共83頁(yè)。文件的分割不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子文件，這樣可以使元素跳躍式地移動(dòng)；每個(gè)子文件中的元素個(gè)數(shù)不必相等。任何增量序列能使用，但必須保證t1=1；當(dāng)增量序列為1時(shí)，該算法就退化成直接插入排序了。希爾排序是不穩(wěn)定的。第29頁(yè)，共83頁(yè)?？焖倥判蚩焖倥判蚴怯擅芭菖判蚋倪M(jìn)而得到的，又稱為分區(qū)交換排序，是目前內(nèi)部排序中速度較快的方法?；舅枷耄涸诖判虻膎個(gè)數(shù)據(jù)中任取一個(gè)數(shù)據(jù)（通常取第一個(gè)數(shù)據(jù)），把該數(shù)據(jù)和文件中的所有記錄比較，所有比該數(shù)據(jù)小的放置在前一部分，所有比它大的放置在后一部分，即該數(shù)據(jù)排在這兩部分的中間。第30頁(yè)，共83頁(yè)。key)&&(i<j))i=j;r[t].j--;希爾（ShellSort)又稱“縮小增量排序”，它也時(shí)一種插入排序類的方法。如果在排序過(guò)程中，數(shù)據(jù)的主要部分存放在外存儲(chǔ)器中（如軟盤、硬盤、磁帶），借助內(nèi)存進(jìn)行內(nèi)、外存數(shù)據(jù)交換，逐步排列記錄之間的順序，則稱之為外部排序。簡(jiǎn)單選擇排序簡(jiǎn)單并且容易實(shí)現(xiàn)，適宜于n較小的情況。這個(gè)作為排序依據(jù)的字段稱之為關(guān)鍵字。依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。for(j=0;j<rd;j++)KeyTypekey;/*關(guān)鍵字*/堆排序在最壞的情況下，其時(shí)間復(fù)雜度為key)/*j為左右兒子中較小者的下標(biāo){if((j<m&&r[j].{r[1]r[i];/*堆頂元素和最后一個(gè)while(i<=m)/*把子序列r[s…m]中剩{r[k+d}.r2[k++]=r[i++];/*余的部分copy到已知序列{491，77，572，16，996，101，863，258，689，325}，請(qǐng)分別給出采用快速排序、堆排序和基數(shù)排序法對(duì)該序列作遞增排序時(shí)每一趟的結(jié)果。一趟快速排序采用從兩頭向中間掃描的辦法。for(i=2;i<=n;i++)快速排序是由冒泡排序改進(jìn)而得到的，又稱為分區(qū)交換排序，是目前內(nèi)部排序中速度較快的方法。while((k>0)&&(r[0].關(guān)鍵字(key)：對(duì)一批記錄的排序，應(yīng)該指定是根據(jù)記錄中哪個(gè)字段進(jìn)行排列。t=r[p].已知序列{26,5,77,1,61,11,59,15,48,19}寫出采用歸并排序算法排序的每一趟的結(jié)果。{for(i=1;i<=t;i++)解:快速排序各趟的結(jié)果如下:第一次劃分以后，再用相同的算法對(duì)劃成的兩部分分別進(jìn)行類似的運(yùn)算，即從每一部分中任選一個(gè)數(shù)據(jù)將其劃分成更小的兩部分。依此遞歸地做下去，直至每個(gè)小部分中的數(shù)據(jù)個(gè)數(shù)為1時(shí)，排序過(guò)程就結(jié)束了。圖7.7所示為一個(gè)快速排序的例子，圖中的方括號(hào)表示待排序部分。第31頁(yè)，共83頁(yè)。圖快速排序第32頁(yè)，共83頁(yè)。一趟快速排序采用從兩頭向中間掃描的辦法。假設(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兩者相遇為止。第33頁(yè)，共83頁(yè)。圖7.8所示是第一趟進(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的最終位置。第34頁(yè)，共83頁(yè)。圖一趟數(shù)據(jù)比較和互換第35頁(yè)，共83頁(yè)。一趟快速排序voidquickOnePass(r[],low,hig){i=low,j=hig;x=r[i];do{while(r[j].key>=x.key&&(i<j))j--;if(i<j)/*已找到了滿足{r[i]=r[j];/*r[j].key<x的r[j]

i++;}

第36頁(yè)，共83頁(yè)?？焖倥判蛩惴ɡm(xù)while(r[i].key<=x.key)&&(i<j))i++;if(i<j)/*已找到了滿足r[i].key>x的r[i]{r[j]=r[i];j--;}}while(i<j);r[i]=x;return(i);}第37頁(yè)，共83頁(yè)。整個(gè)快速排序過(guò)程如下：Voidquicksort(r[],low,hig){intk;If(low<hig){k=quickonepass(r,low,hig);Quicksort(r,low,k-1);Quicksort(r,k+1,hig);}}第38頁(yè)，共83頁(yè)?？焖倥判蚍治霎?dāng)初始序列有序或基本有序時(shí)，快速排序就接近于冒泡排序了，其時(shí)間復(fù)雜度為O(n*n).該算法是霍爾1962年提出的。在所有已發(fā)表的排序算法中，該算法是研究最深的。當(dāng)時(shí)他就發(fā)現(xiàn)了以上的問(wèn)題，他在文章中建議用兩種方法改進(jìn)：產(chǎn)生一個(gè)隨機(jī)數(shù)，或選擇一個(gè)小樣本中值。1969年，辛格爾頓就遵循了這一建議，采用R[1].key,R[n].key,R[n/2].key的中間值，故稱作“三者取中”法。第39頁(yè)，共83頁(yè)。快速排序分析快速排序的平均時(shí)間復(fù)雜性為O(nlogn)，對(duì)n較大的情況，這種算法是平均速度最快的排序算法，但當(dāng)n很小時(shí)，此方法往往比其他簡(jiǎn)單排序方法還要慢?？焖倥判蚋珢垡粋€(gè)“雜亂無(wú)章”的序列?？焖倥判蚴遣环€(wěn)定的。返回第40頁(yè)，共83頁(yè)。9.5堆排序堆的概念堆排序（HeapSort）是利用二叉樹的一種排序方法。（大根）堆（Heap）：在一棵完全二叉樹中，每個(gè)結(jié)點(diǎn)如果有兒子的話，此結(jié)點(diǎn)必須大于或等于其兒子結(jié)點(diǎn)。由于堆是完全二叉樹，采用將結(jié)點(diǎn)順序編號(hào)存入一維數(shù)組中的表示法比鏈接表示法節(jié)省存儲(chǔ)空間，也便于計(jì)算。第41頁(yè)，共83頁(yè)。設(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=。第42頁(yè)，共83頁(yè)。由堆的定義可知，其根結(jié)點(diǎn)（即在數(shù)組中下標(biāo)為1的結(jié)點(diǎn)）具有最小的關(guān)鍵字，堆排序就是利用這一特點(diǎn)進(jìn)行的。實(shí)現(xiàn)堆排序需要解決兩個(gè)問(wèn)題：1.把一組待排序的元素構(gòu)建成堆；2.輸出堆頂后,如何將剩下的n-1個(gè)元素調(diào)整成一個(gè)新的堆.第43頁(yè)，共83頁(yè)。先介紹第2個(gè)問(wèn)題設(shè)堆頂輸出后，以堆的最后一個(gè)元素代替之，此時(shí)的左子樹、右子樹都是堆，則只需自上而下地調(diào)整即可。這個(gè)調(diào)整過(guò)程稱為“篩選”。例：第44頁(yè)，共83頁(yè)。voidsift(r[],i,m)/*把R[i：m]看成完全二叉樹，以{j=2*i;/*R[i+1]和R[i+2]為根的左右子樹是x=r[i];/*堆，現(xiàn)要調(diào)整R[i]，使整個(gè)序列while(j<=m)/*R[i：m]成為一個(gè)堆{if((j<m&&r[j].key>r[j+1].key))j++;if(x.key>r[j].key)/*j為左右兒子中較小者的下標(biāo){

r[i]=r[j];

/*左右兒子中較小者上移，

i=j;

j=2*i}elsebreak;/*x不大于左右兒子，即已找到}/*了合適的位置i，循環(huán)結(jié)束

r[i]=x;/*把x放在i的位置上}篩選算法第45頁(yè)，共83頁(yè)。介紹第1個(gè)問(wèn)題，即把一個(gè)無(wú)序的序列建成一個(gè)堆。把一個(gè)n個(gè)元素的無(wú)序序列看成一棵完全二叉樹，則最后一個(gè)內(nèi)部結(jié)點(diǎn)的下標(biāo)是n/2.因此，只需從第n/2個(gè)元素開始，直到第1個(gè)元素，依次調(diào)用sift,即可建成一個(gè)堆。例：第46頁(yè)，共83頁(yè)。堆排序算法voidheapsort(r[],n){inti;for(i=n/2;i>=1;i--)sift(r,i,n);/*初始建堆*/for(i=n;i>1;i--){r[1]r[i];/*堆頂元素和最后一個(gè)sift(r,1,i-1);/*元素交換}}第47頁(yè)，共83頁(yè)。堆排序算法分析其運(yùn)行時(shí)間主要消耗在建初始堆和進(jìn)行反復(fù)的篩選上。對(duì)n個(gè)元素，樹的深度k=log2n+1，篩選算法中關(guān)鍵字的比較次數(shù)最多為2（k-1），共調(diào)用了n-1次，所以總的比較次數(shù)小于2n（log2n）次；在建初始堆時(shí)，因?yàn)榈趆（1≤h≤k-1）層最多有2h-1個(gè)元素，而每一個(gè)元素的最大調(diào)整次數(shù)為k-h，故總的調(diào)整次數(shù)不大于4n。堆排序在最壞的情況下，其時(shí)間復(fù)雜度為O（nlog2n）。堆排序是不穩(wěn)定的。返回第48頁(yè)，共83頁(yè)。歸并排序歸并是指將若干個(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的有序表為止，就完成了排序。第49頁(yè)，共83頁(yè)。歸并排序算法voidmerge(r[],r2[],s,m,t)/*把兩個(gè)有序子{/*序列r[s…m]和r[m+1…t]歸inti,j,k;/*并成一個(gè)有序序列r2[s…t]i=s;j=m+1;k=s;/*k為數(shù)組r2[]的下標(biāo)while(i<=m&&j<=t){if(r[i].key<=r[j].key)/*比較當(dāng)前r2[k++]=r[i++];/*記錄elser2[k++]=r[j++];/*復(fù)制

}第50頁(yè)，共83頁(yè)。歸并排序算法續(xù)

while(i<=m)/*把子序列r[s…m]中剩r2[k++]=r[i++];/*余的部分copy到while(j<=t)/*r2[]中r2[k++]=r[j++];}第51頁(yè)，共83頁(yè)。上面的算法是對(duì)兩個(gè)有序序列歸并成一個(gè)有序序列。若待排序的序列在一個(gè)數(shù)組r[1…n]中，可把n個(gè)記錄分成n個(gè)子序列，兩兩歸并，……直到歸并成一個(gè)有n個(gè)記錄的有序序列為止。二路歸并的遞歸算法如下：第52頁(yè)，共83頁(yè)。二路歸并排序函數(shù)voidmergesort(r[],r1[],s,t)/*將r[s..t]中的記{intk;/*錄2路歸并后放在r1[s..t]中if(s=t)r1[s]=r[s];else{k=(s+t)/2;mergesort(r,r2,s,k);mergesort(r,r2,k+1,t);merge(r2,r1,s,k,t);}}第53頁(yè)，共83頁(yè)。歸并排序分析二路歸并排序的時(shí)間復(fù)雜性為O(nlogn)，與堆排序和快速排序平均情況的時(shí)間復(fù)雜性是相同數(shù)量級(jí)。歸并排序是穩(wěn)定的排序方法。返回第54頁(yè)，共83頁(yè)?；鶖?shù)排序基數(shù)排序(Radixsort)最初是用于在卡片排序機(jī)上處理穿孔卡片的一種排序方法。基數(shù)排序是采用“分散”的辦法排序。設(shè)每張卡片對(duì)應(yīng)著一個(gè)多位數(shù)的關(guān)鍵字，在卡片排序機(jī)中對(duì)卡片進(jìn)行多趟“分散”過(guò)程，每一趟逐張檢查卡片關(guān)鍵字的某一位數(shù)，將此位數(shù)取值相同的卡片放入同一片盒中。一趟“分散”過(guò)程結(jié)束后，在此排列基礎(chǔ)上，再進(jìn)行下一趟檢查另一位數(shù)的“分散”。對(duì)關(guān)鍵字的檢查從低位到高位進(jìn)行，到檢查最高位的一趟“分散”過(guò)程結(jié)束，最后將卡片“收集”起來(lái)即排序完畢。第55頁(yè)，共83頁(yè)。設(shè)一組關(guān)鍵字的個(gè)數(shù)為n（即卡片的張數(shù)），每個(gè)關(guān)鍵字的位數(shù)為d，每位數(shù)可能有rd種取值，則這種排序方法需進(jìn)行d趟“分散”，每趟檢查n張卡片的某一位數(shù)，并按此位數(shù)值的不同，將卡片分別放到rd個(gè)卡片盒中。每位數(shù)可能取值的數(shù)目rd稱為基數(shù)(Radix)，例如對(duì)于十進(jìn)制數(shù)的每一位可能有0到9十種取值，故基數(shù)為10；而二進(jìn)制的每一位數(shù)只能有0和1兩種取值，則基數(shù)為2。圖7.11所示為基數(shù)排序過(guò)程的一個(gè)例子。第56頁(yè)，共83頁(yè)。圖基數(shù)排序第57頁(yè)，共83頁(yè)。第58頁(yè)，共83頁(yè)。第59頁(yè)，共83頁(yè)。為每個(gè)“盒”設(shè)置一個(gè)鏈接隊(duì)列，并將各隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e存于兩個(gè)一維數(shù)組中。開始時(shí)，將原始數(shù)據(jù)構(gòu)成一個(gè)鏈接隊(duì)列，設(shè)各“盒”的隊(duì)列均為空隊(duì)列。然后將原始數(shù)據(jù)隊(duì)列中各結(jié)點(diǎn)，按所考慮的關(guān)鍵字某位數(shù)的值插入到相應(yīng)“盒”的隊(duì)列中去。當(dāng)一趟結(jié)束時(shí)，再把各“盒”的隊(duì)列依次首尾相連，鏈接成一個(gè)鏈接隊(duì)列，以此作為下一趟的輸入。如此反復(fù)進(jìn)行，直至做完d趟，即排序結(jié)束。第60頁(yè)，共83頁(yè)。數(shù)據(jù)類型設(shè)基數(shù)排序中記錄的數(shù)據(jù)類型如下：structelement{intkey[d];/*d為關(guān)鍵字的位數(shù)*/intnext;};elementrsqlist[n];第61頁(yè)，共83頁(yè)?；鶖?shù)排序算法voidradixsort(rsqlistr,intd,intn,intp){/*d為關(guān)鍵字的位數(shù)，n為待排序的數(shù)據(jù)個(gè)數(shù)，p指向鏈表中的第一個(gè)結(jié)點(diǎn)*/inti,j,t;intf[rd],e[rd];/*隊(duì)列的頭、尾指示器，rd是基數(shù)，十進(jìn)制為10*/for(i=1;i<=n-1;i++)r[i].next=i+1;r[n].next=0;p=1;/*原始數(shù)據(jù)串成靜態(tài)鏈表，頭指針為p*/第62頁(yè)，共83頁(yè)?；鶖?shù)排序算法續(xù)for(i=d;i>0;i--)/*從關(guān)鍵字的最后一位開始*/{for(j=0;j<rd;j++)f[j]=0;/*隊(duì)列指示器置初值*/while(i!=0)/*進(jìn)行分配*/{t=r[p].key[i];if(f[t]==0)f[t]=p;elser[e[t]].next=p;第63頁(yè)，共83頁(yè)。基數(shù)排序算法續(xù)e[t]=p;p=r[p].next;}j=0;while(f[j]==0)j++;/*尋找第一個(gè)非空隊(duì)列*/p=f[j];t=e[j];while(j<rd)第64頁(yè)，共83頁(yè)。基數(shù)排序算法續(xù){j++;if(f[j]!=0){r[t].next=f[j];t=e[j];}/*進(jìn)行收集*/}r[t].next=0;/*收尾*/}}第65頁(yè)，共83頁(yè)。圖初始狀態(tài)現(xiàn)以圖7.11所示的三位十進(jìn)制數(shù)序列306，028，009，948，505，917，721，430，390為例說(shuō)明radixsort函數(shù)的執(zhí)行過(guò)程。第66頁(yè)，共83頁(yè)。第一趟分配后各隊(duì)列情況第67頁(yè)，共83頁(yè)。第68頁(yè)，共83頁(yè)。第一趟收集后的情況第69頁(yè)，共83頁(yè)。第三趟分配后各隊(duì)列情況第70頁(yè)，共83頁(yè)。第71頁(yè)，共83頁(yè)。第三趟收集后的情況第72頁(yè)，共83頁(yè)?；鶖?shù)排序分析采用基數(shù)排序需進(jìn)行d趟關(guān)鍵字的分散和收集過(guò)程，每趟運(yùn)算時(shí)間為O(n+rd)，故總的時(shí)間復(fù)雜性為O(d(n+rd))。若基數(shù)rd相同，對(duì)于關(guān)鍵字?jǐn)?shù)目較多但位數(shù)較少的情況，采用基數(shù)排序較為適用?；鶖?shù)排序是穩(wěn)定的排序方法。返回第73頁(yè)，共83頁(yè)。已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結(jié)果。第74頁(yè)，共83頁(yè)。解:快速排序各趟的結(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]4455606180150200145202930314455606180150200第75頁(yè)，共83頁(yè)。已知序列{26,5,77,1,61,11,59,15,48,19}寫出采用歸并排序算法排序的每一趟的結(jié)果。解:快速排序各趟的結(jié)果如下:[26][5][77][1][61][11][59][15][48][19]