下面是范文網(wǎng)小編分享的排序算法總結(jié)3篇 十大經(jīng)典排序算法總結(jié)，以供借鑒。
排序算法總結(jié)1
10種排序算法總結(jié)
排序算法有很多，所以在特定情景中使用哪一種算法很重要。為了選擇合適的算法，可以按照建議的順序考慮以下標準：（1）執(zhí)行時間（2）存儲空間（3）編程工作
對于數(shù)據(jù)量較小的情形，（1）（2）差別不大，主要考慮（3）；而對于數(shù)據(jù)量大的，（1）為首要。主要排序法有：
一、冒泡（Bubble）排序——相鄰交換
二、選擇排序——每次最小/大排在相應(yīng)的位置
三、插入排序——將下一個插入已排好的序列中
四、殼（Shell）排序——縮小增量
五、歸并排序
六、快速排序
七、堆排序
八、拓撲排序
九、錦標賽排序
十、基數(shù)排序
一、冒泡（Bubble）排序
---Code 從小到大排序n個數(shù)-----voidBubbleSortArray(){ for(int i=1;i
二、選擇排序
---Code 從小到大排序n個數(shù)-voidSelectSortArray(){ intmin_index;for(int i=0;i
-------------Code 從小到大排序n個數(shù)------voidInsertSortArray(){ for(int i=1;i
四、殼（Shell）排序——縮小增量排序
------Code 從小到大排序n個數(shù)------voidShellSortArray(){ for(intincr=3;incr<0;incr--)//增量遞減，以增量3，2，1為例 { for(int L=0;L<(n-1)/incr;L++)//重復(fù)分成的每個子列表 { for(int i=L+incr;i
效率估計O（nlog2^n）~O（n^），取決于增量值的最初大小。建議使用質(zhì)數(shù)作為增量值，因為如果增量值是2的冪，則在下一個通道中會再次比較相同的元素。
殼（Shell）排序改進了插入排序，減少了比較的次數(shù)。是不穩(wěn)定的排序，因為排序過程中元素可能會前后跳躍。
五、歸并排序
---------------Code 從小到大排序--------voidMergeSort(intlow,int high){ if(low>=high)return;//每個子列表中剩下一個元素時停止
else int mid=(low+high)/2;/*將列表劃分成相等的兩個子列表,若有奇數(shù)個元素，則在左邊子列表大于右側(cè)子列表*/ MergeSort(low,mid);//子列表進一步劃分 MergeSort(mid+1,high);int [] B=new int [high-low+1];//新建一個數(shù)組，用于存放歸并的元素
for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*兩個子列表進行排序歸并，直到兩個子列表中的一個結(jié)束*/ { if(arr[i]<=arr[j];){ B[k]=arr[i];I++;} else { B[k]=arr[j];j++;} } for(;j<=high;j++,k++)//如果第二個子列表中仍然有元素，則追加到新列表 B[k]=arr[j];for(;i<=mid;i++,k++)//如果在第一個子列表中仍然有元素，則追加到新列表中 B[k]=arr[i];for(int z=0;z 六、快速排序 -----Code-------------/*快速排序的算法思想：選定一個樞紐元素，對待排序序列進行分割，分割之后的序列一個部分小于樞紐元素，一個部分大于樞紐元素，再對這兩個分割好的子序列進行上述的過程。*/ void swap(inta,int b){intt;t =a;a =b;b =t;} int Partition(int [] arr,intlow,int high){ int pivot=arr[low];//采用子序列的第一個元素作為樞紐元素 while(low < high){ //從后往前栽后半部分中尋找第一個小于樞紐元素的元素 while(low < high &&arr[high] >= pivot){--high;} //將這個比樞紐元素小的元素交換到前半部分 swap(arr[low], arr[high]);//從前往后在前半部分中尋找第一個大于樞紐元素的元素 while(low 此算法的總時間取決于樞紐值的位置；選擇第一個元素作為樞紐，可能導(dǎo)致O（n2）的最糟用例效率。若數(shù)基本有序，效率反而最差。選項中間值作為樞紐，效率是O（nlogn）。基于分治法。 七、堆排序 最大堆：后者任一非終端節(jié)點的關(guān)鍵字均大于或等于它的左、右孩子的關(guān)鍵字，此時位于堆頂?shù)墓?jié)點的關(guān)鍵字是整個序列中最大的。思想： (1)令i=l,并令temp＝ kl;(2)計算i的左孩子j=2i+1;(3)若j<＝n－1，則轉(zhuǎn)(4),否則轉(zhuǎn)(6);(4)比較kj和kj+1,若kj+1>kj,則令j＝j(luò)＋1，否則j不變； (5)比較temp和kj，若kj>temp，則令ki等于kj，并令i=j,j=2i+1,并轉(zhuǎn)(3),否則轉(zhuǎn)(6)(6)令ki等于temp，結(jié)束。 ----------Code---------------------------void HeapSort(SeqIAst R){ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int I;BuildHeap(R)； //將R[1-n]建成初始堆for(i=n;i>1；i--)//對當前無序區(qū)R[1..i]進行堆排序，共做n-1趟。{ R[0]=R[1];R[1]=R[i];R[i]=R[0];//將堆頂和堆中最后一個記錄交換 Heapify(R,1,i-1);//將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì) } }--------Code------- 堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。 堆排序的最壞時間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。 堆排序與直接插入排序的區(qū)別: 直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復(fù)執(zhí)行了這些比較操作。 堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。 八、拓撲排序 例 ：學(xué)生選修課排課先后順序 拓撲排序：把有向圖中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程。方法： 在有向圖中選一個沒有前驅(qū)的頂點且輸出 從圖中刪除該頂點和所有以它為尾的弧 重復(fù)上述兩步，直至全部頂點均已輸出（拓撲排序成功），或者當圖中不存在無前驅(qū)的頂點（圖中有回路）為止。 --------Code-------void TopologicalSort()/*輸出拓撲排序函數(shù)。若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則返回ERROR*/ { intindegree[M];inti,k,j;char n;int count=0;Stack thestack;FindInDegree(G,indegree);//對各頂點求入度indegree[0....num] InitStack(thestack);//初始化棧 for(i=0;i<;i++)(“結(jié)點”+[i].data+“的入度為”+indegree[i]);for(i=0;i<;i++){ if(indegree[i]==0)Push([i]);} (“拓撲排序輸出順序為：”);while(()!=null){ Pop(());j=locatevex(G,n);if(j==-2){ (“發(fā)生錯誤，程序結(jié)束?！?;exit();} ([j].data);count++;for(p=[j].firstarc;p!=NULL;p=){ k=;if(!(--indegree[k]))Push([k]);} } if(count<)(“該圖有環(huán)，出現(xiàn)錯誤，無法排序?！?;else (“排序成功。”);}---------Code-------算法的時間復(fù)雜度O（n+e）。 九、錦標賽排序 錦標賽排序的算法思想與體育比賽類似。 首先將n個數(shù)據(jù)元素兩兩分組，分別按關(guān)鍵字進行比較，得到n／2個比較的優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來，然后對這n／2個數(shù)據(jù)元素再兩兩分組，分別按關(guān)鍵字進行比較，?，如此重復(fù)，直到選出一個關(guān)鍵字最小的數(shù)據(jù)元素為止。 -Code in C--------#include <> #include <> #include <> #include <> #define SIZE #define MAX struct node { long num;//關(guān)鍵字 char str[10];intlastwin;//最后勝的對手 int killer;//被擊敗的對手 long times;//比賽次數(shù) }data[SIZE];long CompareNum=0;long ExchangeNum=0;long Read(char name[])//讀取文件中的數(shù)據(jù)，并存放在數(shù)組data[]中；最后返回數(shù)據(jù)的個數(shù) { FILE *fp;long i=1;fp=fopen(name,“rw”);fscanf(fp,“%d%s”,&data[i].num,data[i].str);while(!feof(fp)){ i++;fscanf(fp,“%d%s”,&data[i].num,data[i].str);} return(i-1);} long Create(long num)//創(chuàng)建勝者樹，返回冠軍（最小數(shù)）在數(shù)組data[]中的下標 { int i,j1,j2,max,time=1;long min;//記錄當前冠軍的下標 for(i=1;pow(2,i-1) if(j1==0)//如果第一位置是空的，則剛來的選手先來的 j1=j2;else//否則剛來的選手是后來的，那么選手都已到場比賽開始 { ++CompareNum;if(data[j1].num<= data[j2].num)//先來的選手獲勝 { data[j1].lastwin = j2;//最后贏的是j2 data[j2].killer=j1;//j2是被j1淘汰的 ++data[j1].times;++data[j2].times;//兩選手場次均加1 min=j1;//最小數(shù)下標為j1 j1=j2=0;//將j1，j2置0 } else//同理 { data[j2].lastwin=j1;data[j1].killer=j2;++data[j1].times;++data[j2].times;min=j2;j1=j2=0;} } } } time++;//輪數(shù)加1 } return min;//返回冠軍的下標 } void TournamentSort(long num)//錦標賽排序 { long tag=Create(num);//返回最小數(shù)下標 FILE *fp1;fp1=fopen(“”,“w+”);//為寫入創(chuàng)建并打開文件 while(data[tag].num!= MAX)//當最小值不是無窮大時 { printf(“%d %sn”,data[tag].num,data[tag].str);//輸出數(shù)據(jù) fprintf(fp1,“%d %sn”,data[tag].num,data[tag].str);//寫入數(shù)據(jù) data[tag].num=MAX;//將當前冠軍用無窮大替換 tag=Create(num);//返回下一個冠軍的下標 } } int main(){ intnum;char name[10];printf(“Input name of the file:”);gets(name);num=Read(name);//讀文件 TournamentSort(num);//錦標賽排序 printf(“CompareNum=%dnExchangeNum=%dn”,CompareNum,ExchangeNum);return 0;}-----------Code------ 十、基數(shù)排序 基數(shù)排序又被稱為桶排序。與前面介紹的幾種排序方法相比較，基數(shù)排序和它們有明顯的不同。 前面所介紹的排序方法都是建立在對數(shù)據(jù)元素關(guān)鍵字進行比較的基礎(chǔ)上，所以可以稱為基于比較的排序； 而基數(shù)排序首先將待排序數(shù)據(jù)元素依次“分配”到不同的桶里，然后再把各桶中的數(shù)據(jù)元素“收集”到一起。 通過使用對多關(guān)鍵字進行排序的這種“分配”和“收集”的方法，基數(shù)排序?qū)崿F(xiàn)了對多關(guān)鍵字進行排序?！?例： 每張撲克牌有兩個“關(guān)鍵字”：花色和面值。其大小順序為： 花色：§＜¨＜?＜a 面值：2＜3＜??＜K＜A 撲克牌的大小先根據(jù)花色比較，花色大的牌比花色小的牌大；花色一樣的牌再根據(jù)面值比較大小。所以，將撲克牌按從小到大的次序排列，可得到以下序列： §2，?，§A，¨2，?，¨A，?2，?，?A，a2，?，aA 這種排序相當于有兩個關(guān)鍵字的排序，一般有兩種方法實現(xiàn)。 其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值從小到大的次序排序，最后把已排好序的四堆牌按花色從小到大次序疊放在一起就得到排序的結(jié)果。其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后將這十三堆牌按面值從小到大的順序疊放在一起，再把整副牌按順序根據(jù)花色再分成四堆（每一堆牌已按面值從小到大的順序有序），最后將這四堆牌按花色從小到大合在一起就得到排序的結(jié)果。 ——————————————————————————————————————— 實現(xiàn)方法： 最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。 最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復(fù)，直到對k1排序后便得到一個有序序列。 --Code in C#----------- using System; using ; using ; using ; namespace LearnSort { class Program { static void Main(string[] args) { int[] arr = CreateRandomArray(10);//產(chǎn)生隨機數(shù)組 print(arr);//輸出數(shù)組 RadixSort(ref arr);//排序 print(arr);//輸出排序后的結(jié)果 (); } public static void RadixSort(ref int[] arr) { intiMaxLength = GetMaxLength(arr); RadixSort(ref arr, iMaxLength); } private static void RadixSort(ref int[] arr, intiMaxLength) { List List char currnetChar;//存放當前的字符比如說某個元素123 中的2 string currentItem;//存放當前的元素比如說某個元素123 for(int i = 0;i ListArr[i] = new List for(int i = 0;i { foreach(int number in arr)//分桶 { currentItem = ();//將當前元素轉(zhuǎn)化成字符串 Try { currnetChar = currentItem[];}//從個位向高位開始分桶 catch { listArr[0].Add(number);continue;}//如果發(fā)生異常，則將該數(shù)壓入listArr[0]。比如說5 是沒有十位數(shù)的，執(zhí)行上面的操作肯定會發(fā)生越界異常的，這正是期望的行為，我們認為5的十位數(shù)是0，所以將它壓入listArr[0]的桶里。 switch(currnetChar)//通過currnetChar的值，確定它壓人哪個桶中。 { case '0': listArr[0].Add(number);break; case '1': listArr[1].Add(number);break; case '2': listArr[2].Add(number);break; case '3': listArr[3].Add(number);break; case '4': listArr[4].Add(number);break; case '5': listArr[5].Add(number);break; case '6': listArr[6].Add(number);break; case '7': listArr[7].Add(number);break; case '8': listArr[8].Add(number);break; case '9': listArr[9].Add(number);break; default: throw new Exception(“unknow error”); } } for(int j = 0;j foreach(int number in listArr[j].ToArray { (number); ListArr[j].Clear();//清空每個桶 } arr = //(“{0} times:”,i); print(arr);//輸出一次排列的結(jié)果 ();//清空list } } //得到最大元素的位數(shù) private static intGetMaxLength(int[] arr) { intiMaxNumber = ; foreach(int i in arr)//遍歷得到最大值 { if(i >iMaxNumber) iMaxNumber = i; } Return ().Length;//這樣獲得最大元素的位數(shù)是不是有點投機取巧了...} //輸出數(shù)組元素 public static void Print(int[] arr) { foreach(int i in arr) (()+'t'); (); } //產(chǎn)生隨機數(shù)組。隨機數(shù)的范圍是0到1000。參數(shù)iLength指產(chǎn)生多少個隨機數(shù) public static int[] CreateRandomArray(intiLength) { int[] arr = new int[iLength]; Random random = new Random(); for(int i = 0;i arr[i] = (0,1001); Return arr; } } }--Code--------------基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復(fù)雜度為O(nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。 八種排序算法總結(jié)之C++版本 五種簡單排序算法 一、冒泡排序 【穩(wěn)定的】 void BubbleSort(int* a,int Count)//實現(xiàn)從小到大的最終結(jié)果 { int temp;for(int i=1;i for(int j=Count-1;j>=i;j--) if(a[j] < a[j-1]) { Temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } } 現(xiàn)在注意，我們給出O方法的定義： 若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n)= O(g(n))。（呵呵，不要說沒學(xué)好數(shù)學(xué)呀，對于編程數(shù)學(xué)是非常重要的！?。?/p> 現(xiàn)在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我們程序循環(huán)的復(fù)雜度為O(n*n)。 二、交換排序 【穩(wěn)定的】 void ExchangeSort(int *a,int Count){ int temp;for(int i=0;i for(int j=i+1;j if(a[j] < a[i]) { Temp = a[j]; a[j] = a[i]; a[i] = temp; } } 時間復(fù)雜度為O(n*n)。 三、選擇法 【不穩(wěn)定的】 void SelectSort(int *a,int Count){ int temp;//一個存儲值 int pos;//一個存儲下標 for(int i=0;i Temp = a[i]; pos = i; for(int j=i+1;j if(a[j] < temp)//選擇排序法就是用第一個元素與最小的元素交換 { Temp = a[j]; pos = j;//下標的交換賦值，記錄當前最小元素的下標位置 } a[pos] = a[i]; a[i] = temp;} } 遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復(fù)雜度為O(n*n)。 我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個最小值）。所以f(n)<=n 所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時候，可以減少一定的交換次數(shù)。 四、插入法 【穩(wěn)定的】 void InsertSort(int *a,int Count){ int temp;//一個存儲值 int pos;//一個存儲下標 for(int i=1;i { Temp = a[i];//當前要插入的元素 pos = i-1; while(pos>=0 && temp { a[pos+1] = a[pos];//將前一個元素后移一位 pos--; } a[pos+1] = temp;} } 其復(fù)雜度仍為O(n*n)。 最終，我個人認為，在簡單排序算法中，直接插入排序是最好的。 五、希爾排序法 【不穩(wěn)定的】 /* * 希爾排序，n為數(shù)組的個數(shù) */ void ShellSort(int arr[], int n){ int temp,pos;int d = n;//增量初值 do{ d = d/3 + 1; for(int i= d;i { Temp = arr[i]; pos = i-d; while(pos>=0 && temp < arr[pos]){ arr[ pos + d ] = arr[pos]; pos-= d; } arr[ pos + d ] = temp; } } while(d > 1);} //實現(xiàn)增量為d的插入排序 三種高級排序算法 一、快速排序 輔助空間復(fù)雜度為O（1） 【不穩(wěn)定的】 void QuickSort(int *a,int left, int right){ int i,j,middle,temp;i = left;j = right;middle = a[(left+right)/2 ];do { while(a[i] i++; while(a[j]>middle && j>left)//從右掃描小于中值的數(shù) j--; if(i<=j)//找到了一對值 { Temp = a[i]; a[i] = a[j]; } a[j] = temp; i++; j--;} } while(i 注意，在掃描過程中，對于給定參考值，對于向右(左)掃描，如果掃描值大(小)于或等于參考值，就需要進行交換。最終得到的結(jié)果是，j左邊的值都小于參考值，而i右邊的值都大于參考值，j和i之間的值都等于參考值。對j左邊和i右邊的分別使用遞歸，就可以完成最終的排序。 這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況 1.數(shù)組的大小是2的冪，這樣分下去始終可以被2整除。假設(shè)為2的k次方，即k=log2(n)。 2.每次我們選擇的值剛好是中間值，這樣，數(shù)組才可以被等分。 第一層遞歸，循環(huán)n次，第二層循環(huán)2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n)= n+n+n+...+n=k*n=log2(n)*n 所以算法復(fù)雜度為O(log2(n)*n) 其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變 成交換法（由于使用了遞歸，情況更糟），但是糟糕的情況只會持續(xù)一個流程，到下一個流程的時候就很可能已經(jīng)避開了該中間的最大和最小值，因為數(shù)組下標變化了，于是中間值不在是那個最大或者最小值。但是你認為這種情況發(fā)生的幾率有多大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數(shù)的情況，快速排序總是最好的。 如果你擔心這個問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢 于快速排序（因為要重組堆）。 二、歸并排序（兩種實現(xiàn)方法均要掌握） 【穩(wěn)定的】 歸并排序是一種極好的外部排序方法，即針對數(shù)據(jù)保存在磁盤上而不是高速內(nèi)存中的問題。 //以下程序參考數(shù)據(jù)結(jié)構(gòu)課本P286頁的模板,為使用指針鏈表實現(xiàn)的 #include struct node{ //鏈表的節(jié)點數(shù)據(jù) int value;node *next;}; node * divide_from(node * head){ node * position, * midpoint, * second_half;if((midpoint=head)== NULL)//List is empty Return NULL;position = midpoint->next;while(position!= NULL)//Move position twice for midpoint's one move { position = position->next; if(position!= NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next;midpoint->next = NULL;//在這里將原鏈拆斷，分為兩段 Return second_half;} node * merge(node * first, node * second){ node * last_sorted;//當前已經(jīng)鏈接好的有序鏈中的最后一個節(jié)點 node combined;//啞節(jié)點 Last_sorted = &combined;while(first!=NULL && second!=NULL){ if(first->value < second->value){ Last_sorted->next = first; Last_sorted = first; first = first->next; }else { Last_sorted->next = second; Last_sorted = second; second = second->next; } } if(first==NULL) Last_sorted->next = second;else Last_sorted->next = first;return ;//返回啞節(jié)點的后繼指針，即為合并后的鏈表的頭指針 } //這里的參數(shù)必須是引用調(diào)用，需要這個指引去允許函數(shù)修改調(diào)用自變量 void MergeSort(node * &head){ if(head!= NULL && head->next!= NULL)//如果只有一個元素，則不需排序 { node * second_half = divide_from(head); mergeSort(head); mergeSort(second_half); head = merge(head, second_half);} } int main(){ node a,b,c,d;node *p1, *p2, *p3, *p4,*head;p1 = &a;p2 = &b;p3 = &c;p4 = &d; = 2; = 4; = 3; = 1; = p2; = p3; = p4; = NULL;//調(diào)用歸并排序前的結(jié)果 head = p1;while(head!= NULL){ cout< head = head->next;} cout< head = p1;while(head!= NULL){ cout< head = head->next;} cout< //以下程序為使用數(shù)組實現(xiàn)的歸并排序,輔助空間復(fù)雜度為O（n） #include void Merge(int data[], int left, int mid, int right){ int n1,n2,k,i,j;n1 = midmid;int *L = new int[n1];//兩個指針指向兩個動態(tài)數(shù)組的首地址 int *R = new int[n2];for(i=0,k=left;i L[i] = data[k];for(i=0,k=mid+1;i R[i] = data[k];for(k=left,i=0,j=0;i if(L[i] < R[j]){ //取小者放前面 data[k] = L[i]; i++; } else { data[k] = R[j]; j++; } } if(i for(j=i;j < n1;j++,k++) } /* * left:數(shù)組的開始下標，一般為0；right：數(shù)組的結(jié)束下標，一般為（n-1）*/ void MergeSort(int data[], int left, int right){ if(left < right){ int mid = left +(right-left)/ 2;//mid=(right+left)/2，防止溢出 mergeSort(data, left, mid); mergeSort(data , mid+1, right); merge(data , left, mid , right);} } int main(){ int data[] = {9,8,7,2,5,6,3,55,1};//排序前的輸出 for(int i=0;i<9;i++) cout< for(int i=0;i<9;i++) cout< 三、堆排序 【不穩(wěn)定的】 /* * 向堆中插入current元素的函數(shù) */ void insert_heap(int data[], const int ¤t, int low, int high) data[k] = L[j];else //if(j for(i=j;i data[k] = R[i];delete []L;//回收內(nèi)存 delete []R;{ int large;//元素data[low]左右兒子中，大者的位置 Large = 2*low + 1;while(large <= high){ if(large < high && data[large] < data[ large+1]) Large++; if(current > data[ large ])//待插入元素的值比它的兩個兒子都大 break; else { data[ low ] = data[ large ];//將其左右兒子的大者上移 Low = large; Large = 2 * large + 1; } } data[ low ] = current;} /* * 建立堆函數(shù)，num為數(shù)組data的元素個數(shù) * 只有一個結(jié)點的<2-樹>自動滿足堆的屬性，因此不必擔心樹中的任何樹葉，即 * 不必擔心表的后一半中的元素。如果從表的中間點開始并從后向前工作，就 * 能夠使用函數(shù)insert_heap去將每個元素插入到包含了所有后面元素的部分堆 * 中，從而創(chuàng)建完整的堆。*/ void build_heap(int data[], int num){ int current;for(int low = num/2-1;low>=0;low--){ current = data[ low ]; insert_heap(data, current, low, num-1);} } /* * 堆排序主函數(shù),num為數(shù)組data的元素個數(shù) */ void heap_sort(int data[], int num){ int current, last_sorted;build_heap(data, num);//建立堆 for(last_sorted = num-1;last_sorted>0;last_sorted--){ //逐個元素處理 current = data[ last_sorted ];//data[0]在整個數(shù)組排序結(jié)束前，存儲的是待排序元素中最大的元素 data[last_sorted] = data[0]; insert_heap(data, current, 0, last_sorted-1);} } int main(){ //用于排序算法的輸入輸出 int a[8] = {5,7,1,2,9,4,6,3,};for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< 事先聲明，此文檔來自某技術(shù)論壇，內(nèi)容歸原作者所有。 1.基本思想： 每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2.排序過程： 【示例】： 初始關(guān)鍵字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結(jié)果 13 27 38 49 49 76 76 97 selectionSort(Type* arr,long len){ long i=0,j=0;/*iterator value*/ long maxPos;assertF(arr!=NULL,“In InsertSort sort,arr is NULLn”);for(i=len-1;i>=1;i--){ maxPos=i;for(j=0;j 直接插入排序（Straight Insertion Sort）：將一個記錄插入到排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。直接插入排序算法 哨兵（監(jiān)視哨）有兩個作用：一是作為臨變量存放R[i]（當前要進行比較的關(guān)鍵字）的副本；二是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。 當文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復(fù)雜度為O(n)，最壞情況是文件初態(tài)為反序，相應(yīng)的時間復(fù)雜度為O(n2)，算法的平均時間復(fù)雜度是O(n2)。算法的輔助空間復(fù)雜度是O(1)，是一個就地排序。 直接插入排序是穩(wěn)定的排序方法。三.冒泡排序 [算法思想]：將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反 復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應(yīng)為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //發(fā)生了交換，故將交換標志置為真 } if(!exchange)return；//本趟排序未發(fā)生交換，提前終止算法 } //endfor(外循環(huán))} //BubbleSort [分析]：起泡排序的結(jié)束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。[算法思想]：將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應(yīng)為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //發(fā)生了交換，故將交換標志置為真 } if(!exchange)return；//本趟排序未發(fā)生交換，提前終止算法 } //endfor(外循環(huán))} //BubbleSort [分析]：起泡排序的結(jié)束條件為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。四.希爾排序 基本思想： 先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d L的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2 假設(shè)待排序文件有10個記錄，其關(guān)鍵字分別是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次為： 5，3，1 Shell排序的算法實現(xiàn) 1． 不設(shè)監(jiān)視哨的算法描述 void ShellPass(SeqList R，int d){//希爾排序中的一趟排序，d為當前增量 for(i=d+1;i<=n；i++)//將R[d+1．．n]分別插入各組當前的有序區(qū) if(R[i].key R[j+d]；=R[j]； //后移記錄 j=j-d； //查找前一記錄 }while(j>0&&R[0].key R[j+d]=R[0]； //插入R[i]到正確的位置上 } //endif } //ShellPass void ShellSort(SeqList R){ int increment=n； //增量初值，不妨設(shè)n>0 do { increment=increment/3+1； //求下一增量 shellPass(R，increment)； //一趟增量為increment的Shell插入排序 }while(increment>1)} //ShellSort 注意： 當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件“j>0”，以防下標越界。2．設(shè)監(jiān)視哨的shell排序算法 算法分析 1．增量序列的選擇 shell排序的執(zhí)行時間依賴于增量序列。 好的增量序列的共同特征： ① 最后一個增量必須為1； ② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。 有人通過大量的實驗，給出了目前較好的結(jié)果：當n較大時，比較和移動的次數(shù)約在到之間。 2．Shell排序的時間性能優(yōu)于直接插入排序 希爾排序的時間性能優(yōu)于直接插入排序的原因： ①當文件初態(tài)基本有序時直接插入排序所需的比較和移動次數(shù)均較少。 ②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度0(n2)差別不大。 ③在希爾排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。 因此，希爾排序在效率上較直接插人排序有較大的改進。3．穩(wěn)定性 希爾 排序是不穩(wěn)定的。參見上述實例，該例中兩個相同關(guān)鍵字49在排序前后的相對次序發(fā)生了變化。五.堆排序 1、堆排序定義 n個關(guān)鍵字序列Kl，K2，?，Kn稱為堆，當且僅當該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))： (1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。 【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對應(yīng)的完全二叉樹分別如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為小根堆。 根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆。注意： ①堆中任一子樹亦是堆。 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。 3、堆排序特點 堆排序(HeapSort)是一樹形選擇排序。 堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系【參見二叉樹的順序存儲結(jié)構(gòu)】，在當前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。 4、堆排序與直接插入排序的區(qū)別 直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復(fù)執(zhí)行了這些比較操作。 堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。 5、堆排序 堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。（1）用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū) ② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有 序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。 ?? 直到無序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作： ① 初始化操作：將R[1..n]構(gòu)造為初始堆； ② 每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。注意： ①只需做n-1趟排序，選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。 ②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。（3）堆排序的算法： void HeapSort(SeqIAst R){ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元 int i； buildHeap(R)； //將R[1-n]建成初始堆 for(i=n;i>1；i--){ //對當前無序區(qū)R[1..i]進行堆排序，共做n-1趟。R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最后一個記錄交換 heapify(R，1，i-1)； //將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì) } //endfor } //HeapSort（4）BuildHeap和Heapify函數(shù)的實現(xiàn) 因為構(gòu)造初始堆必須使用到調(diào)整堆的操作，先討論Heapify的實現(xiàn)。① Heapify函數(shù)思想方法 每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換后，新的無序區(qū)R[1..i-1]中只有R[1]的值發(fā)生了變化，故除R[1]可能違反堆性質(zhì)外，其余任何結(jié)點為根的子樹均是堆。因此，當被調(diào)整區(qū)間是R[low..high]時，只須調(diào)整以R[low]為根的樹即可?！昂Y選法”調(diào)整堆 R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關(guān)鍵字最大的結(jié)點。若R[low].key不小于這兩個孩子結(jié)點的關(guān)鍵字，則R[low]未違反堆性質(zhì)，以R[low]為根的樹已是堆，無須調(diào)整；否則必須將R[low]和它的兩個孩子結(jié)點中關(guān)鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結(jié)點R[large]違反堆性質(zhì)，同樣由于該結(jié)點的兩棵子樹(若存在)仍然是堆，故可重復(fù)上述的調(diào)整過程，對以R[large]為根的樹進行調(diào)整。此過程直至當前被調(diào)整的結(jié)點已滿足堆性質(zhì)，或者該結(jié)點已是葉子為止。上述過程就象過篩子一樣，把較小的關(guān)鍵字逐層篩下去，而將較大的關(guān)鍵字逐層選上來。因此，有人將此方法稱為“篩選法”。 ②BuildHeap的實現(xiàn) 要將初始文件R[l..n]調(diào)整為一個大根堆，就必須將它所對應(yīng)的完全二叉樹中以每一結(jié)點為根的子樹都調(diào)整為堆。 顯然只有一個結(jié)點的 樹是堆，而在完全二叉樹中，所有序號 的結(jié)點都是葉子，因此以這些結(jié)點為根的子樹均已是堆。這樣，我們只需依次將以序號為，-1，?，1的結(jié)點作為根的子樹都調(diào)整為堆即可。 具體算法【參見教材】。 5、大根堆排序?qū)嵗?/p> 對于關(guān)鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結(jié)構(gòu)的變化情況參見。 6、算法分析 堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。 堆排序的最壞時間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。六.快速排序 快速排序的基本思路是：首先我們選擇一個中間值middle（程序中我們可使用數(shù)組中間值），把比中間值小的放在其左邊，比中間值大的放在其右邊。由于這個排序算法較復(fù)雜，我們先給出其進行一次排序的程序框架（從各類數(shù)據(jù)結(jié)構(gòu)教材中可得）： void QuickSort(int *pData, int left, int right){ int i, j;int middle, iTemp;i = left;j = right;middle = pData[(left + right)/ 2];//求中間值 do { while((pData[i] < middle)&&(i < right))//從左掃描大于中值的數(shù) i++; while((pData[j] > middle)&&(j > left))//從右掃描小于中值的數(shù) j--; if(i <= j)//找到了一對值 { //交換 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } } while(i <= j);//如果兩邊掃描的下標交錯，就停止（完成一次） //當左邊部分有值(left if(left QuickSort(pData,left,j); //當右邊部分有值(right>i)，遞歸右半邊 if(right>i) QuickSort(pData,i,right);} 對于n個成員，快速排序法的比較次數(shù)大約為n*logn 次，交換次數(shù)大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950 次比較，而快速排序法僅需要200 次，快速排序法的效率的確很高?？焖倥判蚍ǖ男阅芘c中間值的選定關(guān)系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降?？焖倥判蛩惴ㄗ顗那闆r下的時間復(fù)雜度為O(n2)，而平均時間復(fù)雜度為O(n*logn)。七.合并排序 說明 之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？ 解法 可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。 有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數(shù)字不斷的分為兩個等分，直到最後剩一個數(shù)字為止，然後再反過來不斷的合併，就如下圖所示： 不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。 下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。例子 c #include <> #include <> #include <> #define MAX1 10 #define MAX2 10 #define SWAP(x,y){int t;t = x;x = y;y = t;} int partition(int[], int, int);void quicksort(int[], int, int);void mergesort(int[], int, int[], int, int[]);int main(void){ int number1[MAX1] = {0};int number2[MAX1] = {0};int number3[MAX1+MAX2] = {0};int i, num;srand(time(NULL));printf(“排序前：”);printf(“nnumber1[]：”);for(i = 0;i < MAX1;i++){ number1[i] = rand()% 100;printf(“%d ”, number1[i]);} printf(“nnumber2[]：”);for(i = 0;i < MAX2;i++){ number2[i] = rand()% 100;printf(“%d ”, number2[i]);} // 先排序兩筆資料 Quicksort(number1, 0, MAX1-1);quicksort(number2, 0, MAX2-1);printf(“n排序後：”);printf(“nnumber1[]：”);for(i = 0;i < MAX1;i++)printf(“%d ”, number1[i]);printf(“nnumber2[]：”);for(i = 0;i < MAX2;i++)printf(“%d ”, number2[i]);// 合併排序 mergesort(number1, MAX1, number2, MAX2, number3);printf(“n合併後：”);for(i = 0;i < MAX1+MAX2;i++)printf(“%d ”, number3[i]);printf(“n”);return 0;} int partition(int number[], int left, int right){ int i, j, s;s = number[right];i = left-1;for(j = left;j < right;j++){ if(number[j] <= s){ i++;SWAP(number[i], number[j]);} } SWAP(number[i+1], number[right]);return i+1;} void quicksort(int number[], int left, int right){ int q;if(left < right){ q = partition(number, left, right);quicksort(number, left, q-1);quicksort(number, q+1, right);} } void mergesort(int number1[], int M, int number2[], int N, int number3[]){ int i = 0, j = 0, k = 0;while(i < M && j < N){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < M)number3[k++] = number1[i++];while(j < N)number3[k++] = number2[j++];} Java public class MergeSort { public static int[] sort(int[] number1, int[] number2){ int[] number3 = new int[ + ];int i = 0, j = 0, k = 0;while(i < && j < ){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < )number3[k++] = number1[i++];while(j < )number3[k++] = number2[j++];return number3;} } 八。基數(shù)排序 基數(shù)排序是根據(jù)組成關(guān)鍵字的各位值，用“分配”和“收集”的方法進行排序。例如，把撲克牌的排序看成由花色和面值兩個數(shù)據(jù)項組成的主關(guān)鍵字排序。 花色：梅花<方塊<紅心<黑桃 面值：2<3<4<...<10 梅花2,...,梅花A,方塊2,...,方塊A,紅心2,...,紅心A,黑桃2,...,黑桃A。 有兩種排序方法： 一、先按花色分成四堆，把各堆收集起來；然后對每堆按面值由小到大排列，再按花色從小到大按堆收疊起來。----稱為“最高位優(yōu)先”(MSD)法。 二、先按面值由小到大排列成13堆,然后從小到大收集起來；再按花色不同分成四堆,最后順序收集起來。----稱為“最低位優(yōu)先”(LSD)法。 [例] 設(shè)記錄鍵值序列為{88,71,60,31,87,35,56,18}，用基數(shù)排序(LSD)。如圖所示：其中f[i]、e[i]為按位分配面值為i的隊列的隊頭和隊尾指針。 #define D 3 typedef struct { int key;float data;int link;} JD key data link int jspx(JD r[],int n){ /*鏈式存儲表示的基數(shù)排序*/ int i,j,k,t,p,rd,rg,f[10],e[10];/*p為r[]的下標,rd,rg為比例因子,f[j],e[j]是代碼為j的隊的首尾指針*/ for(i=1;i 將每個記錄項與其他諸項比較計算出小于該項的記錄個數(shù)，以確定該項的位置。 排序算法總結(jié)3篇 十大經(jīng)典排序算法總結(jié)相關(guān)文章：排序算法總結(jié)2
排序算法總結(jié)3