C程序設(shè)計(jì)排序

會(huì)計(jì)學(xué)1C程序設(shè)計(jì)排序概述什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的元素序列調(diào)整為“有序”的元素序列。排序的分類待排序元素關(guān)鍵字個(gè)數(shù)單關(guān)鍵字排序多關(guān)鍵字排序待排序元素的存儲(chǔ)介質(zhì)內(nèi)部排序：排序過(guò)程不需要訪問(wèn)外存便能完成外部排序：排序過(guò)程需要訪問(wèn)外存才能完成第1頁(yè)/共92頁(yè)概述內(nèi)部排序的類別插入類：直接插入排序、折半排序、2-路插入排序、

希爾排序分劃類：冒泡排序、快速排序選擇類：簡(jiǎn)單選擇排序、堆排序歸并類：2-路歸并排序其他方法：基數(shù)排序第2頁(yè)/共92頁(yè)概述排序的兩個(gè)基本操作比較兩個(gè)關(guān)鍵字大小將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置穩(wěn)定性待排序列{a1,a2,…,an}，其相應(yīng)的關(guān)鍵字序列{k1,k2,…,kn}，假設(shè)ki=kj

(

1≤i,j≤n且i≠j)，且在排序前的序列中ai領(lǐng)先于aj。

若在排序后的序列中ai仍領(lǐng)先于aj，則稱所用的排序方法是穩(wěn)定的，反之，則稱其是不穩(wěn)定的。第3頁(yè)/共92頁(yè)7.1插入類排序插入類排序?qū)⒋判蛟刂饌€(gè)插入到已排好序的有序表中，從而得到一個(gè)新的有序表。應(yīng)用插入類排序思想的算法直接插入排序折半插入排序2-路插入排序希爾排序第4頁(yè)/共92頁(yè)7.1.1直接插入排序排序過(guò)程整個(gè)排序過(guò)程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序第i趟直接插入排序的基本思想有序序列A[0..i-1]R[i]無(wú)序序列A[i..n-1]有序序列A[0..i]無(wú)序序列A[i+1..n-1]第5頁(yè)/共92頁(yè)直接插入排序例第6頁(yè)/共92頁(yè)7.1.1直接插入排序直接插入排序算法//直接插入排序,數(shù)組data用于存放待排序元素，n為待排序元素個(gè)數(shù)template<classElemType>voidInsertSort(ElemTypedata[],intn){ElemTypetmp;inti,j;for(i=1;i<n;i++){if(data[i]>data[i-1])continue;tmp=data[i]; //保存待插入的元素data[i]=data[i-1];for(j=i-1;j>0&&data[j-1]>tmp;j--)data[j]=data[j-1]; //元素后移data[j]=tmp; //插入到正確位置}}第7頁(yè)/共92頁(yè)7.1.1直接插入排序算法評(píng)價(jià)時(shí)間復(fù)雜度正序元素移動(dòng)次數(shù)：0元素比較次數(shù)：n-1逆序元素移動(dòng)次數(shù)：元素比較次數(shù)：平均情況O(n2)第8頁(yè)/共92頁(yè)7.1.2折半插入排序因?yàn)锳[0..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用“折半查找”實(shí)現(xiàn)“在A[0..i-1]中查找A[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉p少元素關(guān)鍵字間的比較次數(shù)，但元素移動(dòng)次數(shù)不變第9頁(yè)/共92頁(yè)折半插入排序例第10頁(yè)/共92頁(yè)折半插入排序算法7.1.2折半插入排序template<classElemType>voidBInsertSort(ElemTypedata[],intn){ElemTypetmp;inti,j,mid,low,high;for(i=1;i<n;i++){tmp=data[i],low=0,high=i-1;

while(low<=high){ //在data[low..high]中查找插入的位置mid=(low+high)/2; //折半if(tmp<data[mid])high=--mid; //插入點(diǎn)在低半?yún)^(qū)elselow=++mid; //插入點(diǎn)在高半?yún)^(qū)}for(j=i-1;j>=low;j--)data[j+1]=data[j]; //元素后移

data[low]=tmp; //插入到正確位置}}第11頁(yè)/共92頁(yè)7.1.32-路插入排序?qū)⒉迦雲(yún)^(qū)域分成大致等長(zhǎng)的兩段，選擇性地插人到其中一段排序過(guò)程設(shè)置一個(gè)和原數(shù)組data同類型，同規(guī)模的是數(shù)組d，并將其視為循環(huán)數(shù)組（即位置n-1和0邏輯上相鄰）d[0]=data[0]，將d[0]看作為排好序中處于中間位置的元素，從第二個(gè)元素data[1]開始做以下操作如果data[i]>d[0]，將data[i]插入d[0]之后的有序序列，并保持插入后有序；反之，將其插入d[0]之前的有序序列，并保持插入后有序

第12頁(yè)/共92頁(yè)2-路插入排序例第13頁(yè)/共92頁(yè)7.1.32-路插入排序算法評(píng)價(jià)減少約為n2/8的元素移動(dòng)次數(shù)基準(zhǔn)元素選取的好壞直接影響排序的效率第14頁(yè)/共92頁(yè)7.1.4希爾排序希爾排序又稱縮小增量排序?qū)⒂涗浶蛄蟹殖扇舾勺有蛄?，分別對(duì)每個(gè)子序列進(jìn)行插入排序。例如：將n個(gè)記錄分成d個(gè)子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]} {R[2]，R[2+d]，R[2+2d]，…，R[2+kd]} … {R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}

其中，d稱為增量，它的值在排序過(guò)程中從大到小逐漸縮小，直至最后一趟排序減為1。第15頁(yè)/共92頁(yè)希爾排序例3428817922165524996446設(shè)增量d=516282479

22345581996446設(shè)增量d=31622245528346446997981設(shè)增量d=11622242834465564798199第16頁(yè)/共92頁(yè)7.1.4希爾排序希爾排序算法template<classElemType>voidShellSort(ElemTypedata[],intincrements[] ,intn,intincrementsLength){inti,j,k;ElemTypetmp;

for(k=0;k<incrementsLength;k++){ //進(jìn)行以increments[k]為增量的排序for(i=increments[k];i<n;i++){tmp=data[i];for(j=i;j>=increments[k];j-=increments[k]){if(tmp>=data[j-increments[k]])break;data[j]=data[j-increments[k]];}data[j]=tmp;}}}第17頁(yè)/共92頁(yè)7.1.4希爾排序特點(diǎn)子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的元素組成一個(gè)子序列希爾排序可提高排序速度，因?yàn)榉纸M后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序第18頁(yè)/共92頁(yè)7.1.4希爾排序算法評(píng)價(jià)算法效率依賴于增量序列的選擇時(shí)間復(fù)雜度在O(n3/2)到O(n7/6)之間增量序列的取法最后一個(gè)增量必須為1其他增量間保持“互質(zhì)”第19頁(yè)/共92頁(yè)7.2分劃類排序分劃類排序通過(guò)一趟劃分確定一個(gè)元素在序列中的位置，保證在它之前的一組元素不比它大，之后的不比它小，接著對(duì)兩組元素繼續(xù)分劃，直至待排序列有序。應(yīng)用插入類排序思想的算法冒泡排序快速排序第20頁(yè)/共92頁(yè)7.2.1冒泡排序排序過(guò)程將第一個(gè)和第二個(gè)元素的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩元素互換；接著比較第二個(gè)和第三個(gè)元素的關(guān)鍵字，依次類推，直至最后兩個(gè)元素的完成比較，這稱為第一趟冒泡排序。第一趟排序分劃出一組元素個(gè)數(shù)為n-1的待排序列和一個(gè)關(guān)鍵字最大的元素。第i趟對(duì)前n-i+1個(gè)的元素進(jìn)行類似的排序操作，得到一組元素個(gè)數(shù)為n-i的待排序列和一個(gè)關(guān)鍵字次大的元素。這樣不斷分劃直至一趟分劃時(shí)無(wú)元素互換為止。第21頁(yè)/共92頁(yè)7.2.1冒泡排序假設(shè)在排序過(guò)程中，元素序列A[1..n]的狀態(tài)為：無(wú)序序列A[1..n-i+1]有序序列A[n-i+2..n]n-i+1無(wú)序序列A[1..n-i]有序序列A[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到n-i+1的位置上第i趟起泡排序第22頁(yè)/共92頁(yè)冒泡排序例第23頁(yè)/共92頁(yè)7.2.1冒泡排序冒泡排序算法template<classElemType>voidBubbleSort(ElemTypedata[],intn){intlastSwapIndex=n-1;//用于記錄最后一次交換的元素下標(biāo)inti,j;for(i=lastSwapIndex;i>0;i=lastSwapIndex){lastSwapIndex=0;for(j=0;j<i;j++)if(data[j]>data[j+1]){Swap(data[j],data[j+1]);lastSwapIndex=j;}}}第24頁(yè)/共92頁(yè)7.2.1冒泡排序算法評(píng)價(jià)最好情況（正序）移動(dòng)次數(shù)：0比較次數(shù)：n-1最壞情況（逆序）移動(dòng)次數(shù)：3n(n-1)/2比較次數(shù)：n(n-1)/2T(n)=O(n2)第25頁(yè)/共92頁(yè)7.2.2快速排序一趟快速排序選第一個(gè)待排序元素作為樞軸（或支點(diǎn)pivot），根據(jù)樞軸將待排序列劃分為兩個(gè)子列這兩個(gè)子列必須滿足以下條件：一個(gè)子列的元素關(guān)鍵字都不大于樞軸的關(guān)鍵字，另一個(gè)子列的元素關(guān)鍵字都不小于樞軸的關(guān)鍵字。第26頁(yè)/共92頁(yè)7.2.2快速排序首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。無(wú)序的元素序列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸一次劃分分別進(jìn)行快速排序第27頁(yè)/共92頁(yè)7.2.2快速排序排序過(guò)程對(duì)待排序列A進(jìn)行快速排序的遞歸算法QuickSort(A)可以描述如下：如果A中元素的個(gè)數(shù)為0或1，則返回；否則，繼續(xù)選取A中的一個(gè)元素p作為樞軸（pivot）將A中剩下的元素“劃分”成兩個(gè)不相交的集合：

QuickSort(A1),p,QuickSort(A2)第28頁(yè)/共92頁(yè)一趟快速排序例第29頁(yè)/共92頁(yè)7.2.2快速排序//對(duì)data[low...high]進(jìn)行分劃，確定樞軸的位置，并返回其所在位置//子序列中，在樞軸之前（后）的元素均不大（?。┯谒黷emplate<classElemType>intPartition(ElemTypedata[],intlow,inthigh){ElemTypepivot=data[low]; //用子序列的頭元素作為樞軸

while(low<high){while(low<high&&data[high]>=pivot)high--;data[low]=data[high]; //比樞軸小的元素移到低端

while(low<high&&pivot>=data[low])low++;data[high]=data[low]; //比樞軸大的元素移到高端}data[low]=pivot; //確定樞軸的合適位置returnlow; //返回樞軸的位置}一趟快速排序算法第30頁(yè)/共92頁(yè)7.2.2快速排序快速排序算法//對(duì)data[begin...end]進(jìn)行快速排序template<classElemType>voidQuickSort(ElemTypedata[],intbegin,intend){if(begin>=end) //data長(zhǎng)度小于等于時(shí)返回return;intpivot=Partition(data,begin,end); //對(duì)data[begin...end]進(jìn)行分劃QuickSort(data,begin,pivot-1);//對(duì)低端子列進(jìn)行遞歸排序QuickSort(data,pivot+1,end);//對(duì)高端子列進(jìn)行遞歸排序}

//快速排序template<classElemType>voidQuickSort(ElemTypedata[],intn){if(n<2)return;QuickSort(data,0,n-1);}第31頁(yè)/共92頁(yè)7.2.2快速排序算法分析最好情況每次中間值作為樞軸T(n)=O(nlog2n)最壞情況每次總選最大或最小元素作為樞軸T(n)=O(n2)平均情況T(n)=O(nlogn)三數(shù)中值分割法第32頁(yè)/共92頁(yè)7.3選擇類排序選擇類排序逐趟掃描未排序的部分，從中選取一個(gè)元素移動(dòng)到合適的位置。應(yīng)用選擇類排序思想的算法簡(jiǎn)單選擇排序樹形選擇排序堆排序第33頁(yè)/共92頁(yè)7.3.1簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列A[1..i-1]無(wú)序序列A[i..n]第i趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的元素有序序列A[1..i]無(wú)序序列A[i+1..n]第34頁(yè)/共92頁(yè)7.3.1簡(jiǎn)單選擇排序排序過(guò)程第一趟掃描所有待排序元素，找出關(guān)鍵字最小的元素并將它與第一個(gè)元素進(jìn)行交換；第i趟，掃描待排序列中剩余n-i+1個(gè)元素，找出關(guān)鍵字最小的元素與序列中第i個(gè)位置上的元素交換重復(fù)上述操作,直到所有的元素都放到正確的位置上為止第35頁(yè)/共92頁(yè)簡(jiǎn)單選擇排序例第36頁(yè)/共92頁(yè)簡(jiǎn)單選擇排序算法7.3.1簡(jiǎn)單選擇排序template<classElemType>voidSelectionSort(ElemTypedata[],intn){inti,j,min;for(i=0;i<n;i++){min=i;for(j=i+1;j<n;j++){ //選擇data[i+1...n-1]中最小的元素if(data[j]<data[min])min=j;}Swap(data[i],data[min]); //將data[i]與第i小的元素交換}}第37頁(yè)/共92頁(yè)7.3.1簡(jiǎn)單選擇排序算法分析最好情況比較次數(shù)：移動(dòng)次數(shù)：0最壞情況比較次數(shù)：移動(dòng)次數(shù)：3(n-1)T(n)=O(n2)第38頁(yè)/共92頁(yè)7.3.2樹形選擇排序簡(jiǎn)單選擇排序中一趟排序中的比較操作可能在前一趟中已經(jīng)做過(guò)，但前一趟中未保存這些比較結(jié)果，因此在后一趟的排序中又重復(fù)執(zhí)行了這些操作。為了解決這個(gè)問(wèn)題，樹形選擇排序應(yīng)運(yùn)而生。算法思想先將n個(gè)元素的關(guān)鍵字兩兩比較，然后將其中

個(gè)較小者兩兩比較，如此重復(fù)，不斷的淘汰較大者，最終選出關(guān)鍵字最小的元素第39頁(yè)/共92頁(yè)樹形選擇排序例第40頁(yè)/共92頁(yè)7.3.3堆排序堆的定義：堆是滿足下列性質(zhì)的數(shù)列{a1,a2,…，an}：或(小頂堆)(大頂堆){12,36,27,65,40,34,98,81,73,55,49}小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆第41頁(yè)/共92頁(yè)7.3.3堆排序若將該數(shù)列視作完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri的右孩子aia2i

a2i+1

1236276549817355403498不是堆14第42頁(yè)/共92頁(yè)7.3.3堆排序堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法。建大頂堆{98,53,55,18,4,22,24}{24,53,55,18,4,22,98}交換98和24重新調(diào)整為大頂堆{55,53,24,18,4,22,98}{22,18,53,98,4,24,55}經(jīng)過(guò)篩選第43頁(yè)/共92頁(yè)7.3.3堆排序排序過(guò)程將待排序列A[0…n-1]調(diào)整為大頂堆；將堆頂元素A[0]（即關(guān)鍵字最大的元素）與堆尾元素（即堆中最后一個(gè)元素）交換，從堆中除去堆尾元素(即關(guān)鍵字最大的元素)，同時(shí)調(diào)整堆中剩余元素，使它們恢復(fù)堆屬性；反復(fù)進(jìn)行步驟2，直至堆中元素個(gè)數(shù)為1。第44頁(yè)/共92頁(yè)7.3.3堆排序堆排序需解決的兩個(gè)問(wèn)題：如何將初始的待排序列調(diào)整為一個(gè)堆？因堆頂元素與堆尾元素交換后，新的堆頂元素可能破壞了堆屬性，如何再調(diào)整成為堆？第二個(gè)問(wèn)題解決方法輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中較大者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選”第45頁(yè)/共92頁(yè)例堆排序調(diào)整例第46頁(yè)/共92頁(yè)堆排序調(diào)整例第47頁(yè)/共92頁(yè)7.3.3堆排序第一個(gè)問(wèn)題解決方法從最后一個(gè)非葉子結(jié)點(diǎn)（即第

個(gè)元素）開始對(duì)所有非葉子結(jié)點(diǎn)調(diào)整操作第48頁(yè)/共92頁(yè)建堆例含7個(gè)元素的無(wú)序序列（22,18,53,98,4,24,55）2218552449822551853244982255985324418985522532441853第49頁(yè)/共92頁(yè)調(diào)整堆算法7.3.3堆排序//將data[i..n-1]中的元素調(diào)整為大頂堆template<classElemType>voidHeapAdjust(ElemTypedata[],inti,intn){ElemTypetmp;intchild;

for(tmp=data[i];LeftChild(i)<n;i=child){child=LeftChild(i);if(child!=n-1&&data[child+1]>data[child]) //取較大的孩子結(jié)點(diǎn)child++;if(tmp<data[child])data[i]=data[child];elsebreak;}data[i]=tmp;}第50頁(yè)/共92頁(yè)7.3.3堆排序堆排序算法//堆排序template<classElemType>voidHeapSort(ElemTypedata[],intn){inti;for(i=n/2;i>=0;i--) //建堆HeapAdjust(data,i,n);

//將堆的根結(jié)點(diǎn)與最后的一個(gè)葉結(jié)點(diǎn)交換,并進(jìn)行調(diào)整for(i=n-1;i>0;i--){ Swap(data[0],data[i]);HeapAdjust(data,0,i);}}第51頁(yè)/共92頁(yè)7.3.3堆排序算法評(píng)價(jià)最好情況：O(n)最壞情況：O(nlogn)平均：O(nlogn)第52頁(yè)/共92頁(yè)7.4歸并類排序歸并將兩個(gè)有序列合并成為一個(gè)新的有序列2-路歸并排序?qū)⑾噜彽脑貎蓛蓺w并，得到

個(gè)長(zhǎng)度為2或1的有序子序列，再將這些子序列兩兩歸并，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序列為止第53頁(yè)/共92頁(yè)2-路歸并排序例第54頁(yè)/共92頁(yè)“歸并”算法//將數(shù)組data中，[lptr...rptr-1][rptr...rightEnd]兩部分的元素進(jìn)行合并//tmpArr為合并時(shí)的輔存空間template<classElemType>voidMerge(ElemTypedata[],ElemTypetmpArr[],intlptr ,intrptr,intrightEnd){intleftEnd=rptr-1;intptr,i;ptr=i=lptr;

while(lptr<=leftEnd&&rptr<=rightEnd)if(data[lptr]<=data[rptr])tmpArr[ptr++]=data[lptr++];elsetmpArr[ptr++]=data[rptr++];

while(lptr<=leftEnd)tmpArr[ptr++]=data[lptr++];while(rptr<=rightEnd)tmpArr[ptr++]=data[rptr++];

for(;i<=rightEnd;i++)data[i]=tmpArr[i];}第55頁(yè)/共92頁(yè)2-路歸并排序算法template<classElemType>voidMPass(ElemTypedata[],ElemTypetmpArr[],intn,intmergeLength){inti=0;

while(i<=n-2*mergeLength){Merge(data,tmpArr,i,i+mergeLength,i+2*mergeLength-1);i=i+2*mergeLength;}if(i+mergeLength<n)Merge(data,tmpArr,i,i+mergeLength,n-1);}//2-路歸并算法非遞歸實(shí)現(xiàn)template<classElemType>voidMergeSortNonRecursion(ElemTypedata[],intn){intmergeLength=1; //mergeLength記錄每趟歸并的步長(zhǎng)ElemType*pArr=NULL;pArr=newElemType[n]; //pArr為合并時(shí)的輔存空間

while(mergeLength<n){MPass(data,pArr,n,mergeLength);mergeLength*=2;}delete[]pArr;}第56頁(yè)/共92頁(yè)7.4歸并類排序算法評(píng)價(jià)T(n)=O(nlogn)缺點(diǎn)空間復(fù)雜度為O(n)算法中需要較多的拷貝工作第57頁(yè)/共92頁(yè)7.5基數(shù)排序無(wú)須比較關(guān)鍵字通過(guò)“分組”和“收集”兩個(gè)過(guò)程來(lái)完成排序任務(wù)借助“多關(guān)鍵字排序”的思想第58頁(yè)/共92頁(yè)7.5.1多關(guān)鍵字的排序假設(shè)待排序列{a1,a2,…,an}中每個(gè)元素ai有d個(gè)關(guān)鍵字

，該序列對(duì)關(guān)鍵字

有序是指：

對(duì)序列中任意兩個(gè)元素ai和aj(1≤i＜j≤n)都滿足下列有序關(guān)系：

當(dāng)兩個(gè)元素的所有關(guān)鍵字都相等時(shí)，則必須保持其穩(wěn)定性。其中

稱為最主位關(guān)鍵字，

稱為最次位關(guān)鍵字。第59頁(yè)/共92頁(yè)7.5.1多關(guān)鍵字的排序排序方法最高位優(yōu)先法（MSD）先對(duì)最高位關(guān)鍵字k1排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值接著讓每個(gè)子序列對(duì)次關(guān)鍵字k2排序，又分成若干更小的子序列依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個(gè)有序序列最低位優(yōu)先法（LSD）從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序，……依次重復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列第60頁(yè)/共92頁(yè)7.5.1多關(guān)鍵字的排序MSD與LSD不同特點(diǎn)按MSD排序，必須將序列逐層分割成若干子序列，然后對(duì)各子序列分別排序按LSD排序，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過(guò)關(guān)鍵字比較，而通過(guò)若干次分配與收集實(shí)現(xiàn)排序第61頁(yè)/共92頁(yè)7.5.2基數(shù)排序基數(shù)排序依次根據(jù)各關(guān)鍵字分量進(jìn)行“分配”、“收集”完成排序在單關(guān)鍵字排序中，一個(gè)關(guān)鍵字可以看作由若干個(gè)關(guān)鍵字分量復(fù)合而成，如整數(shù)可視為若干數(shù)位的集合。第62頁(yè)/共92頁(yè)基數(shù)排序例第63頁(yè)/共92頁(yè)7.5.2基數(shù)排序用數(shù)組實(shí)現(xiàn)的基數(shù)排序算法voidRadixSort(intdata[],intn){constintradix=10;constintdigits=10;

inti,j,k,factor;

queue<int>queues[radix];

for(i=0,factor=1;i<digits;i++,factor*=radix){for(j=0;j<n;j++)queues[(data[j]/factor)%radix].push(data[j]);//分配for(k=j=0;j<radix;j++,k++)//收集while(!queues[j].empty()){data[k]=queues[j].front();queues[j].pop();}}}第64頁(yè)/共92頁(yè)7.5.2基數(shù)排序用數(shù)組實(shí)現(xiàn)基數(shù)排序的缺點(diǎn)雖然不需要進(jìn)行“比較”操作，但仍需要大量的元素移動(dòng)操作還需要額外的空間來(lái)存放10個(gè)隊(duì)列鏈?zhǔn)交鶖?shù)排序用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序第65頁(yè)/共92頁(yè)7.5.2基數(shù)排序鏈?zhǔn)交鶖?shù)排設(shè)置10個(gè)隊(duì)列，front[i]和rear[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變?cè)氐闹羔樦?，將鏈表中的元素分配?0個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對(duì)十位、百位進(jìn)行，最后得到一個(gè)有序序列第66頁(yè)/共92頁(yè)鏈?zhǔn)交鶖?shù)排序（第一趟）例第67頁(yè)/共92頁(yè)靜態(tài)鏈表classSLList{structNode{intkey[DIGITS];intinfo;intnext;};friendostream&operator<<(ostream&os,SLList&s);public:SLList():data(NULL),length(0){};~SLList();voidArrange();//重排voidInit(intarr[],intn);voidRadixSort();//鏈?zhǔn)交鶖?shù)排序private:voidDistribute(int[],int[],int);//分配voidCollection(int[],int[],int);//收集Node*data;intlength;};第68頁(yè)/共92頁(yè)7.5.2基數(shù)排序voidSLList::Distribute(intfront[],intrear[],intdigit){inti,index;for(i=0;i<RADIX;i++)front[i]=0;

for(i=data[0].next;i>0;i=L.data[i].next){index=data[i].key/(int)pow(10.0,digit)-data[i].key/(int)pow(10.0,digit+1)*10;if(front[index]==0)front[index]=i;elsedata[rear[index]].next=i;

rear[index]=i;}}鏈?zhǔn)交鶖?shù)排序——“分配”算法第69頁(yè)/共92頁(yè)鏈?zhǔn)交鶖?shù)排序——“收集”算法7.5.2基數(shù)排序voidSLList::Collection(intfront[],intrear[],intdigit){inti,current;for(i=0;front[i]==0;i++); //找到第一個(gè)非空子表data[0].next=front[i]; //頭結(jié)點(diǎn)指向第一個(gè)非空子表中第一個(gè)結(jié)點(diǎn)current=rear[i++];

for(;i<RADIX;i++){if(front[i]==0)continue;data[current].next=front[i]; //鏈接兩個(gè)非空子表current=rear[i];}data[current].next=0;}第70頁(yè)/共92頁(yè)鏈?zhǔn)交鶖?shù)排序算法7.5.2基數(shù)排序//用SLList實(shí)現(xiàn)的基數(shù)排序voidSLList::RadixSort(){inti;intfront[RADIX],rear[RADIX];

//從最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分配收集for(i=0;i<DIGITS;i++){Distribute(front,rear,i);Collection(front,rear,i);}}第71頁(yè)/共92頁(yè)7.5.2基數(shù)排序重排鏈?zhǔn)交鶖?shù)排序產(chǎn)生的是一個(gè)有序循環(huán)鏈表，只能對(duì)它進(jìn)行順序訪問(wèn)，無(wú)法進(jìn)行隨機(jī)訪問(wèn)，因此有時(shí)需要對(duì)元素重新排列，將元素按照鏈表結(jié)點(diǎn)中next域的值調(diào)整位置使其順序存儲(chǔ)具體做法順序掃描有序鏈表，將鏈表中第i個(gè)結(jié)點(diǎn)移動(dòng)至靜態(tài)鏈表中的第i個(gè)分量第72頁(yè)/共92頁(yè)重排例第73頁(yè)/共92頁(yè)重排算法7.5.2基數(shù)排序voidSLList::Arrange(){inti,tmp;intcurrent=data[0].next; //current存放第一個(gè)元素的當(dāng)前位置

for(i=1;i<length;i++){while(current<i) //找到第i個(gè)元素，并用current存放其在靜態(tài) //鏈表中當(dāng)前位置current=data[current].next;tmp=data[current].next;if(current!=i){Swap(data[current],data[i]);//第i個(gè)元素調(diào)整到位data[i].next=current;//指向被移走的元素}current=tmp;//為找第i+1個(gè)元素做準(zhǔn)備}}第74頁(yè)/共92頁(yè)7.5.2基數(shù)排序算法分析空間復(fù)雜度O(r+n)時(shí)間復(fù)雜度 T(n)=O(d(n+r))

其中，n為待排序元素個(gè)數(shù)，d為元素的關(guān)鍵字分量數(shù)，r為基數(shù)第75頁(yè)/共92頁(yè)7.6內(nèi)部排序的比較排序方法平均情況最好情況最壞情況基數(shù)排序O(d(n+r))O(d(n+r))O(d(n+r))2-路歸并排序O(nlogn)O(nlogn)O(nlogn)堆排序O(nlogn)O(n)O(nlogn)快速排序O(nlogn)O(nlogn)O(n2)希爾排序O(n)直接插入排序O(n2)O(n)O(n2)簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)第76頁(yè)/共92頁(yè)7.6內(nèi)部排序的比較從平均性能而言，快速排序最佳，但最壞情況下不如堆排序