第一篇：《算法導論》學習總結(jié)——快速排序
《算法導論》學習總結(jié)——快速排序
曾經(jīng)在程序員雜志上看到快速排序的作者，Hoare，曾經(jīng)的圖靈獎獲得者啊，牛光閃閃的。不過當時，對快速排序什么的，印象不算深刻，畢竟沒好好學。記得當時雜志上說到的是，快速排序，應該是目前最快的內(nèi)部排序算法（雖然獨立到語言上，C++的sort會比調(diào)用快速排序快）。現(xiàn)在就進入快速排序的美好復習吧。
與歸并排序類似，快排也用分治模式。主要是三個步驟：
1）分解：將數(shù)組A[p....r]劃分為2個子數(shù)組A[p....q-1]和A[q+1....r]，使前一個每個元素都小于A[q],后一個數(shù)組，每個元素都大于A[q]（q在劃分過程中計算）
2）解決：遞歸調(diào)用快速排序，對2個子數(shù)組進行排序
3）合并：因為2個子數(shù)組是就地排序，所以合并不用操作，數(shù)組已排序
看到這個合并，就想到啊，和歸并比，一個從小到大，一個從大到小，差距就是這么大，快排么得合并開銷，一下就省了很多啊，說明，方向很重要啊，如同那句，同樣一個B，S與N的差別，大家都懂的。
快速排序的實現(xiàn)代碼如下：
? ? ? ? ? ? ? ? //=================
// Name : Qsort.cpp
// Author : xia
// Copyright : NUAA
// Description : 快速排序的實現(xiàn)
//=================
#include
#include
#include
?? #include
?? #include
??
?? using namespace std;?? const int MAX = 1000;??
?? void WriteToFile(vector
?? {//將v寫入文件，純看排序結(jié)果是否正確，也可以寫個test()
?? int i;?? ofstream result(“Qsort.txt”);??
if(result.fail())?? {
?? cout << “ open data error ” << endl;?? exit(EXIT_FAILURE);?? }
??
for(i=0;i ?? result << v[i] << “ ”;?? } ?? result.close();?? } ?? int Partion(vector ?? int x=A[r];//x都感覺沒用 ?? int i=p-1; ?? for(int j=p;j ?? if(A[j] <= x)?? { ?? i++; ?? swap(A[i],A[j]);?? } ?? } ?? swap(A[i+1],A[r]);?? return i+1;?? } ?? void Qsort(vector ?? if(p < r)?? { ?? int q = Partion(A,p,r);?? Qsort(A,p,q-1);?? Qsort(A,q+1,r);?? } ?? } ?? int main(int argc, char **argv)?? { ?? vector int i; ?? for(i=0;i< MAX;i++)?? v.push_back(i); ?? random_shuffle(v.begin(),v.end());//打亂 ?? ?? Qsort(v,0,v.size()-1);?? WriteToFile(v);?? ?? return 0;?? } 說到代碼，很慚愧的，http://）由于以下兩個原因： 1）做格式化時，結(jié)果常常是扭曲的，所以得不到正確的隨機數(shù)（如某些數(shù)的出現(xiàn)頻率要高于其它數(shù)） 2）rand()只支持整型數(shù)；不能用它來產(chǎn)生隨機字符，浮點數(shù)，字符串或數(shù)據(jù)庫中的記錄 所以采用了STL函數(shù)random_shuffle()，先隨機生成0到MAX-1的隨機數(shù)，用random_shuffle()打亂，再進行排序。 另外，其實Hoare老師用的快排并不是如上代碼所示，也就是說，最原始的快速排序，是這樣滴： int HoarePartion(vector ?? int x=A[p];?? int i=p-1;?? int j=r+1;?? while(1)?? { ?? while(A[--j] > x)??; ?? while(A[++i] < x)??;?? if(i ?? swap(A[i],A[j]);?? else ?? return j;?? } ?? } ?? ?? void Qsort(vector if(p < r)?? { ?? int q = HoarePartion(A,p,r);?? Qsort(A,p,q);?? Qsort(A,q+1,r);?? } ?? } 也可以參考：http://tayoto.blog.hexun.com/25048556_d.html，區(qū)別只是我的代碼直接while里面用A[--j]，可讀性不高，因為著實不喜歡do-while結(jié)構。 對于最原始的快排，嚴蔚敏老師的《數(shù)據(jù)結(jié)構》是這樣實現(xiàn)的： int Partion(vector int pivotkey;?? pivotkey = v[low];?? while(low < high)??? { ??? while(low < high && v[high] >= pivotkey)??? high--;??? v[low] = v[high]; ??? while(low < high && v[low] <= pivotkey)??? low ++; ??? v[high] = v[low];??? } ??? v[low] = pivotkey;??? return low;??? } ??? void quickSort(vector ??? if(left < right)??? { ??? int i = Partion(number , left, right); ??? quickSort(number, left, i-1);// 對左邊進行遞歸 ??? quickSort(number, i+1, right);// 對右邊進行遞歸 ??? } ??? } 當然，區(qū)別都只是在劃分的過程，畢竟分治，才是快排的精髓嘛，不過這倆大同小異。 快排的運行時間，顯然與劃分是否對稱有關，要是直接劃分出來，是一個最不均衡的二叉樹，那就夠喝一壺的了，跟插入排序似的。下面網(wǎng)址有說法，是快排隱藏的二叉排序樹思想，其實可以參考，雖然只是個人理解http://bbs.chinaunix.net/viewthread.php?tid=1011316。其實說到二叉，堆排序不也是嗎？區(qū)別只是堆排序顯式的建堆，也就構成了一筆不小的開銷，如果考慮隱藏排序二叉樹的話，倒是可以理解為毛快排快于堆排。 由于快排平均情況下效果顯然很良好，那么怎么得到平均情況就是個值得思考的問題，所以書上給出了，在劃分的時候，隨機獲取一個數(shù)作為樞軸，而不是用我們的A[low]。于是我們得到了快排的隨機化版本如下： int Partion(vector ??? int x=A[r];??? int i=p-1; ??? for(int j=p;j ??? if(A[j] <= x)??? { ??? i++; ??? swap(A[i],A[j]);??? } ??? } ??? swap(A[i+1],A[r]);??? return i+1;??? } ??? int RandomPartion(vector int i= p + rand()%(r-p+1);//i<-RANDOM(p,r) ??? swap(A[r],A[i]);??? return Partion(A,p,r);??? } ??? void RandomQsort(vector ??? if(p < r)??? { ??? int q = RandomPartion(A,p,r);??? RandomQsort(A,p,q-1);??? RandomQsort(A,q+1,r);??? } ??? } 與常規(guī)快排的區(qū)別，就是在劃分的時候，獲取一個隨機數(shù)下標，再用其數(shù)組中的值作為樞軸，當然，這樣就充分考慮平均性能了。 還有一種改進RANDOM-QUICKSORT的方法，就是根據(jù)從子數(shù)組更仔細地選擇的（而不是隨機選擇的元素）作為樞軸來劃分。常用的做法是三數(shù)取中。可以參考： http://blog.csdn.net/zhanglei8893/article/details/6266915 本章最后還提到個很蛋疼的Stooge排序，實現(xiàn)如下： void StoogeSort(vector ??? if(A[i] > A[j])??? swap(A[i],A[j]);??? if(i+1 >=j)??? return; ??? int k =(j-i+1)/3; ??? StoogeSort(A,i,j-k);//前2/ 3??? StoogeSort(A,i+k,j);//后2/3 ??? StoogeSort(A,i,j-k);//又前2/3 ??? // StoogeSort(A,i,i+k-1);// 如果采用1/3排不出來啊 ??? } 對于數(shù)組A[i...j]，STOOGE-SORT算法將這個數(shù)組劃分成均等的3份，分別用A, B, C表示。第8、9行從宏觀上來看它進行了兩趟，結(jié)果是最大的1/3到了C，最小的1/3到了B，從宏觀上來看，整個數(shù)組的三個大塊就有序了，再進行遞歸，整個數(shù)組就有序了。第8和第9行，可以看做一個冒泡過程。 不過從運行時間的測試來講，很不給力（具體數(shù)據(jù)就不列了）。STOOGE-SORT最壞情況下的運行時間的遞歸式 T(n)= 2T(2n/3)+Θ(1)由主定律可以求得T(n)=n^2.71，相比插入排序、快速排序的Θ(n^2)和 堆排序、合并排序的Θ(nlgn)，不給力啊。參考自：http://blog.csdn.net/zhanglei8893/article/details/6235294。 本章最后，練習7-4還提出個尾遞歸的概念，起因是QuickSort的第二次遞歸調(diào)用不是必須的，可以用迭代控制結(jié)構來替代。如： QUICKSORT'(A, p, r)1 while p < r 2 do ? Partition and sort left subarray.3 q ← PARTITION(A, p, r)4 QUICKSORT'(A, p, q-1)5 p ← q + 1 具體 有效性的證明可以參考：http://blog.csdn.net/zhanglei8893/article/details/6236792，需要說明的是，當數(shù)組正序時，其遞歸深度和棧深度都為Θ(n)。 排序算法總結(jié) 所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。當待排序記錄的關鍵字都不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。 在待排序的文件中，若存在多個關鍵字相同的記錄，經(jīng)過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關鍵字的記錄之間的相對次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定的。 要注意的是，排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。 一.插入排序 插入排序的基本思想是每步將一個待排序的記錄按其排序碼值的大小，插到前面已經(jīng)排好的文件中的適當位置，直到全部插入完為止。插入排序方法主要有直接插入排序和希爾排序。 ①.直接插入排序(穩(wěn)定)接插入排序的過程為：在插入第i個記錄時，R1,R2,..Ri-1已經(jīng)排好序，將第i個記錄的排序碼Ki依次和R1,R2,..,Ri-1的排序碼逐個進行比較，找到適當?shù)奈恢谩Ｊ褂弥苯硬迦肱判颍瑢τ诰哂衝個記錄的文件，要進行n-1趟排序。 代碼如下: void Dir_Insert(int A[],int N)//直接插入排序 { int j,t;for(int i=1;i 希爾(Shell)排序的基本思想是：先取一個小于n的整數(shù)d1作為第一個增量把文件的全部記錄分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取得第二個增量d2 一般取d1=n/2，di+1=di/2。如果結(jié)果為偶數(shù)，則加1，保證di為奇數(shù)。 希爾排序是不穩(wěn)定的，希爾排序的執(zhí)行時間依賴于增量序列，其平均時間復雜度為O(n^1.3).代碼如下: void Shell(int A[],int n)//Shell排序 { int i,j,k,t;(n/2)%2 == 0 ? k = n/2+1 : k = n/2;//保證增量為奇數(shù) while(k > 0){ for(j=k;j 二.選擇排序 選擇排序的基本思想是每步從待排序的記錄中選出排序碼最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。選擇排序中主要使用直接選擇排序和堆排 序。 ①.直接選擇排序(不穩(wěn)定) 直接選擇排序的過程是：首先在所有記錄中選出序碼最小的記錄，把它與第1個記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個記錄交換......依次類推，直到所有記錄排完為止。 無論文件初始狀態(tài)如何，在第i趟排序中選出最小關鍵字的記錄，需要做n-i次比較，因此，總的比較次數(shù)為n(n-1)/2=O(n^2)。當初始文件為正序時，移動次數(shù)為0；文件初態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總的移動次數(shù)取最大值3(n-1)。直接選擇排序的平均時間復雜度為O(n^2)。直接選擇排序是不穩(wěn)定的。 代碼如下: void Dir_Choose(int A[],int n)//直接選擇排序 { int k,t;for(int i=0;i ②.堆排序(不穩(wěn)定) 堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。n個關鍵字序列 K1,K2,...,Kn稱為堆，當且僅當該序列滿足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根結(jié)點(堆頂)的關鍵字是堆里所有結(jié)點關鍵字中最小者，稱為小根堆；根結(jié)點的關鍵字是堆里所有結(jié)點關鍵字中最大者，稱為大根堆。若將此序列所存儲的向量R[1..n]看作是一棵完全二叉樹的存儲結(jié)構，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關鍵字。 堆排序的關鍵步驟有兩個：一是如何建立初始堆；二是當堆的根結(jié)點與堆的最后一個結(jié)點交換后，如何對少了一個結(jié)點后的結(jié)點序列做調(diào)整，使之重新成為堆。堆排序的最壞時間復雜度為O(nlog2n),堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較 次數(shù)較多，所以堆排序不適宜于記錄較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。 代碼略..三.交換排序 交換排序的基本思想是：兩兩比較待排序記錄的排序碼，并交換不滿足順序要求的那寫偶對，直到滿足條件為止。交換排序的主要方法有冒泡排序和快速排序.①.冒泡排序(穩(wěn)定的) 冒泡排序?qū)⒈慌判虻挠涗洈?shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為ki的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R；凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 冒泡排序的具體過程如下： 第一步，先比較k1和k2，若k1>k2，則交換k1和k2所在的記錄，否則不交換。繼續(xù)對k2和k3重復上述過程，直到處理完kn-1和kn。這時最大的排序碼記錄轉(zhuǎn)到了最后位置，稱第1次起泡，共執(zhí)行n-1次比較。 與第一步類似，從k1和k2開始比較，到kn-2和kn-1為止，共執(zhí)行n-2次比較。 依次類推，共做n-1次起泡，完成整個排序過程。 若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需關鍵字比較次數(shù)為n-1次，記錄移動次數(shù)為0。因此，冒泡排序最好的時間復雜度為O(n)。 若初始文件是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關鍵字的比較(1<=i<=n-1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較次數(shù)達到最大值n(n-1)/2=O(n^2),移動次數(shù)也達到最大值3n(n-1)/2=O(n^2)。因此，冒泡排序的最壞時間復雜度為O(n^2)。 雖然冒泡排序不一定要進行n-1趟，但由于它的記錄移動次數(shù)較多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是穩(wěn)定的。 代碼如下: void QP(int A[],int n)//優(yōu)化的冒泡排序 { int count=0,t,flag;for(int i=0;i ②.快速排序：(不穩(wěn)定的) 快速排序采用了一種分治的策略，通常稱其為分治法，其基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。 快速排序的具體過程如下： 第一步，在待排序的n個記錄中任取一個記錄，以該記錄的排序碼為準，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2組各記錄的排序碼都大于該排序碼，并把該記錄排在這兩組中間。 第二步，采用同樣的方法，對左邊的組和右邊的組進行排序，直到所有記錄都排到相應的位置為止。 代碼如下: void Quick_Sort(int A[],int low,int high)//low和high是數(shù)組的下標 { if(low 四.歸并排序 歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。初始時，把含有n個結(jié)點的待排序序列看作由n個長度都為1的有序子表組成，將它們依次兩兩歸并得到長度為2的若干有序子表，再對它們兩兩合并。直到得到長度為n的有序表，排序結(jié)束。 歸并排序是一種穩(wěn)定的排序，可用順序存儲結(jié)構，也易于在鏈表上實現(xiàn)，對長度為n的文件，需進行l(wèi)og2n趟二路歸并，每趟歸并的時間為O(n),故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。歸并排序需要一個輔助向量來暫存兩個有序子文件歸并的結(jié)果，故其輔助空間復雜度為O(n),顯然它不是就地排序。 代碼略...五.基數(shù)排序 設單關鍵字的每個分量的取值范圍均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值個數(shù)rd稱為基數(shù)．基數(shù)的選擇和關鍵字的分解因關鍵字的類型而異． (1).若關鍵字是十進制整數(shù)，則按個、十等位進行分解，基數(shù)rd=10,C0=0,C9=9,d為最長整數(shù)的位數(shù)． (2).若關鍵字是小寫的英文字符串，則rd=26,C0='a',C25='z',d為最長字符串的長度． 基數(shù)排序的基本思想是：從低位到高位依次對待排序的關鍵碼進行分配和收集，經(jīng)過d趟分配和收集，就可以得到一個有序序列． 按平均時間將排序分為四類： （1）平方階(O(n2))排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序； （2）線性對數(shù)階(O(nlgn))排序 如快速、堆和歸并排序； （3）O(n1+￡)階排序 ￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序； （4）線性階(O(n))排序 如基數(shù)排序。 各種排序方法比較 簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。 影響排序效果的因素 因為不同的排序方法適應不同的應用環(huán)境和要求，所以選擇合適的排序方法應綜合考慮下列因素： ①待排序的記錄數(shù)目n； ②記錄的大小(規(guī)模)； ③關鍵字的結(jié)構及其初始狀態(tài)； ④對穩(wěn)定性的要求； ⑤語言工具的條件； ⑥存儲結(jié)構； ⑦時間和輔助空間復雜度等。 不同條件下，排序方法的選擇 (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應選直接選擇排序為宜。 (2)若文件初始狀態(tài)基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或 歸并排序。 快速排序是目前基于比較的內(nèi)部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短； 堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。 若要求排序穩(wěn)定，則可選用歸并排序。但從單個記錄起進行兩兩歸并的 排序算法并不值得提倡，通常可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以改進后的歸并排序仍是穩(wěn)定的。 事先聲明，此文檔來自某技術論壇，內(nèi)容歸原作者所有。 1.基本思想： 每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2.排序過程： 【示例】： 初始關鍵字 [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 3.void 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 插入排序（Insertion Sort）的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。直接插入排序 直接插入排序（Straight Insertion Sort）：將一個記錄插入到排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。直接插入排序算法 哨兵（監(jiān)視哨）有兩個作用：一是作為臨變量存放R[i]（當前要進行比較的關鍵字）的副本；二是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。 當文件的初始狀態(tài)不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態(tài)為正序，此時算法的時間復雜度為O(n)，最壞情況是文件初態(tài)為反序，相應的時間復雜度為O(n2)，算法的平均時間復雜度是O(n2)。算法的輔助空間復雜度是O(1)，是一個就地排序。 直接插入排序是穩(wěn)定的排序方法。三.冒泡排序 [算法思想]：將被排序的記錄數(shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反 復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應為假 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：凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； //交換標志 for(i=1;i exchange=FALSE； //本趟排序開始前，交換標志應為假 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 該方法實質(zhì)上是一種分組插入方法。給定實例的shell排序的排序過程 假設待排序文件有10個記錄，其關鍵字分別是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次為： 5，3，1 Shell排序的算法實現(xiàn) 1． 不設監(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； //增量初值，不妨設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．設監(jiān)視哨的shell排序算法 算法分析 1．增量序列的選擇 Shell排序的執(zhí)行時間依賴于增量序列。 好的增量序列的共同特征： ① 最后一個增量必須為1； ② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。 有人通過大量的實驗，給出了目前較好的結(jié)果：當n較大時，比較和移動的次數(shù)約在nl.25到1.6n1.25之間。 2．Shell排序的時間性能優(yōu)于直接插入排序 希爾排序的時間性能優(yōu)于直接插入排序的原因： ①當文件初態(tài)基本有序時直接插入排序所需的比較和移動次數(shù)均較少。 ②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。 ③在希爾排序開始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。 因此，希爾排序在效率上較直接插人排序有較大的改進。3．穩(wěn)定性 希爾 排序是不穩(wěn)定的。參見上述實例，該例中兩個相同關鍵字49在排序前后的相對次序發(fā)生了變化。五.堆排序 1、堆排序定義 n個關鍵字序列Kl，K2，?，Kn稱為堆，當且僅當該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))： (1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關鍵字。 【例】關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根結(jié)點(亦稱為堆頂)的關鍵字是堆里所有結(jié)點關鍵字中最小者的堆稱為小根堆。 根結(jié)點(亦稱為堆頂)的關鍵字是堆里所有結(jié)點關鍵字中最大者，稱為大根堆。注意： ①堆中任一子樹亦是堆。 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。 3、堆排序特點 堆排序(HeapSort)是一樹形選擇排序。 堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結(jié)構，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關系【參見二叉樹的順序存儲結(jié)構】，在當前無序區(qū)中選擇關鍵字最大(或最小)的記錄。 4、堆排序與直接插入排序的區(qū)別 直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復執(zhí)行了這些比較操作。 堆排序可通過樹形結(jié)構保存部分比較結(jié)果，可減少比較次數(shù)。 5、堆排序 堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關鍵字的記錄變得簡單。（1）用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū) ② 再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質(zhì)，故應將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有 序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。 ?? 直到無序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作： ① 初始化操作：將R[1..n]構造為初始堆； ② 每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。注意： ①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。 ②用小根堆排序與利用大根堆類似，只不過其排序結(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) 因為構造初始堆必須使用到調(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]為根的樹即可。“篩選法”調(diào)整堆 R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結(jié)點。若R[low].key不小于這兩個孩子結(jié)點的關鍵字，則R[low]未違反堆性質(zhì)，以R[low]為根的樹已是堆，無須調(diào)整；否則必須將R[low]和它的兩個孩子結(jié)點中關鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結(jié)點R[large]違反堆性質(zhì)，同樣由于該結(jié)點的兩棵子樹(若存在)仍然是堆，故可重復上述的調(diào)整過程，對以R[large]為根的樹進行調(diào)整。此過程直至當前被調(diào)整的結(jié)點已滿足堆性質(zhì)，或者該結(jié)點已是葉子為止。上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。因此，有人將此方法稱為“篩選法”。 ②BuildHeap的實現(xiàn) 要將初始文件R[l..n]調(diào)整為一個大根堆，就必須將它所對應的完全二叉樹中以每一結(jié)點為根的子樹都調(diào)整為堆。 顯然只有一個結(jié)點的 樹是堆，而在完全二叉樹中，所有序號 的結(jié)點都是葉子，因此以這些結(jié)點為根的子樹均已是堆。這樣，我們只需依次將以序號為，-1，?，1的結(jié)點作為根的子樹都調(diào)整為堆即可。 具體算法【參見教材】。 5、大根堆排序?qū)嵗?/p> 對于關鍵字序列(42，13，24，91，23，16，05，88)，在建堆過程中完全二叉樹及其存儲結(jié)構的變化情況參見。 6、算法分析 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調(diào)用Heapify實現(xiàn)的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。六.快速排序 快速排序的基本思路是：首先我們選擇一個中間值middle（程序中我們可使用數(shù)組中間值），把比中間值小的放在其左邊，比中間值大的放在其右邊。由于這個排序算法較復雜，我們先給出其進行一次排序的程序框架（從各類數(shù)據(jù)結(jié)構教材中可得）： 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 次，快速排序法的效率的確很高。快速排序法的性能與中間值的選定關系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降。快速排序算法最壞情況下的時間復雜度為O(n2)，而平均時間復雜度為O(n*logn)。七.合并排序 說明 之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？ 解法 可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。 有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數(shù)字不斷的分為兩個等分，直到最後剩一個數(shù)字為止，然後再反過來不斷的合併，就如下圖所示： 不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。 下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。例子 C #include 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[number1.length + number2.length];int i = 0, j = 0, k = 0;while(i < number1.length && j < number2.length){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < number1.length)number3[k++] = number1[i++];while(j < number2.length)number3[k++] = number2[j++];return number3;} } 八。基數(shù)排序 基數(shù)排序是根據(jù)組成關鍵字的各位值，用“分配”和“收集”的方法進行排序。例如，把撲克牌的排序看成由花色和面值兩個數(shù)據(jù)項組成的主關鍵字排序。 花色：梅花<方塊<紅心<黑桃 面值：2<3<4<...<10 若要將一副撲克牌排成下列次序： 梅花2,...,梅花A,方塊2,...,方塊A,紅心2,...,紅心A,黑桃2,...,黑桃A。 有兩種排序方法： 一、先按花色分成四堆，把各堆收集起來；然后對每堆按面值由小到大排列，再按花色從小到大按堆收疊起來。----稱為“最高位優(yōu)先”(MSD)法。 二、先按面值由小到大排列成13堆,然后從小到大收集起來；再按花色不同分成四堆,最后順序收集起來。----稱為“最低位優(yōu)先”(LSD)法。 [例] 設記錄鍵值序列為{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ù)，以確定該項的位置。 10種排序算法總結(jié) 排序算法有很多，所以在特定情景中使用哪一種算法很重要。為了選擇合適的算法，可以按照建議的順序考慮以下標準：（1）執(zhí)行時間（2）存儲空間（3）編程工作 對于數(shù)據(jù)量較小的情形，（1）（2）差別不大，主要考慮（3）；而對于數(shù)據(jù)量大的，（1）為首要。主要排序法有： 一、冒泡（Bubble）排序——相鄰交換 二、選擇排序——每次最小/大排在相應的位置 三、插入排序——將下一個插入已排好的序列中 四、殼（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++)//重復分成的每個子列表 { for(int i=L+incr;i 效率估計O（nlog2^n）~O（n^1.5），取決于增量值的最初大小。建議使用質(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 此算法的總時間取決于樞紐值的位置；選擇第一個元素作為樞紐，可能導致O（n2）的最糟用例效率。若數(shù)基本有序，效率反而最差。選項中間值作為樞紐，效率是O（nlogn）。基于分治法。 七、堆排序 最大堆：后者任一非終端節(jié)點的關鍵字均大于或等于它的左、右孩子的關鍵字，此時位于堆頂?shù)墓?jié)點的關鍵字是整個序列中最大的。思想： (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＋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------- 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調(diào)用Heapify實現(xiàn)的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。 堆排序與直接插入排序的區(qū)別: 直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復執(zhí)行了這些比較操作。 堆排序可通過樹形結(jié)構保存部分比較結(jié)果，可減少比較次數(shù)。 八、拓撲排序 例 ：學生選修課排課先后順序 拓撲排序：把有向圖中各頂點按照它們相互之間的優(yōu)先關系排列成一個線性序列的過程。方法： 在有向圖中選一個沒有前驅(qū)的頂點且輸出 從圖中刪除該頂點和所有以它為尾的弧 重復上述兩步，直至全部頂點均已輸出（拓撲排序成功），或者當圖中不存在無前驅(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 九、錦標賽排序 錦標賽排序的算法思想與體育比賽類似。 首先將n個數(shù)據(jù)元素兩兩分組，分別按關鍵字進行比較，得到n／2個比較的優(yōu)勝者(關鍵字小者)，作為第一步比較的結(jié)果保留下來，然后對這n／2個數(shù)據(jù)元素再兩兩分組，分別按關鍵字進行比較，?，如此重復，直到選出一個關鍵字最小的數(shù)據(jù)元素為止。 -Code in C--------#include 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(“sort.txt”,“w+”);//為寫入創(chuàng)建并打開文件sort.txt 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ù)元素關鍵字進行比較的基礎上，所以可以稱為基于比較的排序； 而基數(shù)排序首先將待排序數(shù)據(jù)元素依次“分配”到不同的桶里，然后再把各桶中的數(shù)據(jù)元素“收集”到一起。 通過使用對多關鍵字進行排序的這種“分配”和“收集”的方法，基數(shù)排序?qū)崿F(xiàn)了對多關鍵字進行排序。——————————————————————————————————————— 例： 每張撲克牌有兩個“關鍵字”：花色和面值。其大小順序為： 花色：§＜¨＜?＜a 面值：2＜3＜??＜K＜A 撲克牌的大小先根據(jù)花色比較，花色大的牌比花色小的牌大；花色一樣的牌再根據(jù)面值比較大小。所以，將撲克牌按從小到大的次序排列，可得到以下序列： §2，?，§A，¨2，?，¨A，?2，?，?A，a2，?，aA 這種排序相當于有兩個關鍵字的排序，一般有兩種方法實現(xiàn)。 其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值從小到大的次序排序，最后把已排好序的四堆牌按花色從小到大次序疊放在一起就得到排序的結(jié)果。其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后將這十三堆牌按面值從小到大的順序疊放在一起，再把整副牌按順序根據(jù)花色再分成四堆（每一堆牌已按面值從小到大的順序有序），最后將這四堆牌按花色從小到大合在一起就得到排序的結(jié)果。 ——————————————————————————————————————— 實現(xiàn)方法： 最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關鍵碼繼續(xù)這樣的排序分組，直到按最次位關鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。 最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序后便得到一個有序序列。 --Code in C#----------- using System; using System.Collections.Generic; using System.Linq; using System.Text; 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é)果 Console.ReadKey(); } 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 = number.ToString();//將當前元素轉(zhuǎn)化成字符串 try { currnetChar = currentItem[currentItem.Length-i-1];}//從個位向高位開始分桶 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 { list.Add(number); listArr[j].Clear();//清空每個桶 } arr = list.ToArray //Console.Write(“{0} times:”,i); Print(arr);//輸出一次排列的結(jié)果 list.Clear();//清空list } } //得到最大元素的位數(shù) private static intGetMaxLength(int[] arr) { intiMaxNumber = Int32.MinValue; foreach(int i in arr)//遍歷得到最大值 { if(i >iMaxNumber) iMaxNumber = i; } return iMaxNumber.ToString().Length;//這樣獲得最大元素的位數(shù)是不是有點投機取巧了...} //輸出數(shù)組元素 public static void Print(int[] arr) { foreach(int i in arr) System.Console.Write(i.ToString()+'t'); System.Console.WriteLine(); } //產(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] = random.Next(0,1001); return arr; } } }--Code--------------基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復雜度為O(nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。 算 法 設 計 與 分 析 學習 報 告 第一部分 學習內(nèi)容歸納 “計算機算法是以一步接一步的方式來詳細描述計算機如何將輸入轉(zhuǎn)化為所要求的輸出的過程，或者說，算法是對計算機上執(zhí)行的計算過程的具體描述。”（參考文獻：百度百科）《算法設計與分析》是一門面向設計，在計算機科學中處于核心地位的課程。這門課程主要講授了在計算機應用中經(jīng)常遇到的問題和求解的方法，分治法、動態(tài)規(guī)劃法、隨機算法等設計算法的基本原理、技巧和算法復雜性的分析，以及計算理論簡介。 第一部分“概論和數(shù)學準備”在簡單了解了算法的基本概念和復雜性、研究步驟等幾個重要知識點后，著重學習了算法的數(shù)學基礎，包括生成函數(shù)、差方方程的求解等，主要適用于求解算法的時間復雜性。 “任何可以用計算機求解的問題所需要的計算時間都與其規(guī)模有關：問題的規(guī)模越小，解題所需的計算時間往往也越短，從而也就比較容易處理。”（參考文獻：《計算機算法設計與分析（第3版）》）而第二部分介紹的算法常用技術之首——分治法就運用了這樣的思想。分治法的要領在于Divide（子問題的劃分）-Conquer（子問題的求解）-Combine（子問題解的組合）。由于子問題和原問題是同類的，遞歸的思想在分治法中顯得尤其重要，它們經(jīng)常同時運用在算法設計中。這部分內(nèi)容從Select（求第k小元）算法，尋找最近點對算法和快速傅立葉變換FFT等實際應用中深化對分治法思想的理解，同時也強調(diào)了平衡思想的重要性。 第三部分“動態(tài)規(guī)劃”與分治法類似，同樣是把問題層層分解成規(guī)模越來越小的同類型的子問題。但與分治法不同的是，分治法中的子問題通常是相互獨立的，而動態(tài)規(guī)劃法中的子問題很多都是重復的，因此通常采用遞推的方法以避免重復計算。然而，也不是所有的情況下都采用遞推法，當有大量的子問題無需求解時，更好的方式是采用動態(tài)規(guī)劃法的變形——備忘錄方法。通常需要用到動態(tài)規(guī)劃法求解的問題都具有子問題的高度重復性和最優(yōu)子結(jié)構性質(zhì)兩大特征，這也是我們分析問題和設計算法時的關鍵點。最長公共子序列LCS問題和最優(yōu)二分搜索樹就是從動態(tài)規(guī)劃法的兩個主要特征角度分析問題，進而設計出相應的解決算法的。而這部分內(nèi)容中的另一個問題——流水作業(yè)調(diào)度，則告訴我們采用動態(tài)規(guī)劃時偶爾也得不到高效的算法，我們要學會將已有的知識靈活運用，適當加工。 第四部分“集合算法”中首先介紹了一種分析算法復雜度的手法——平攤分析（Amortized Analysis）。與之前我們所接觸的算法分析方法即逐一考慮執(zhí)行每條指令所需的時間復雜度再進行累加的方法不同，平攤分析是對若干條指令從整體角度考慮其時間復雜度，通過這樣的方法獲得的時間復雜度更加貼近實際的情況。平攤分析的主要方法有聚集方法，會計方法和勢能方法。聚集方法將指令的時間復雜度分類計算再相加；會計方法采用了耗費提前計算的思想；勢能方法引入了勢函數(shù)的概念，從每步操作的數(shù)據(jù)結(jié)構狀態(tài)和勢函數(shù)的關系角度分析得出操作的平攤代價。“集合算法”這一部分主要分析了Union（合并集合）和Find（給出元素所在集合名）這兩種運算。從上學期的《數(shù)據(jù)結(jié)構》課程的學習中，我們就已經(jīng)發(fā)現(xiàn)集合和樹之間的關系是密不可分的，我們經(jīng)常用樹結(jié)構來表示集合。而2-3樹是一種特殊的每個內(nèi)結(jié)點都只有2個或3個兒子的樹，廣泛的應用于可實現(xiàn)Member（查找）、Insert（插入）、Delete（刪除）操作的數(shù)據(jù)結(jié)構——字典，可實現(xiàn)Insert、Delete、Union和Min（查找最小葉結(jié)點）的數(shù)據(jù)結(jié)構——可并堆，可實現(xiàn)Insert、Delete、Find、Concatenate（保序合并）和Split （分裂）的數(shù)據(jù)結(jié)構——可連接隊列等。 之前討論的算法中每一步計算步驟都是確定的，然而第五部分“隨機算法”中所討論的隨機化算法允許算法在執(zhí)行的過程中隨機的選擇下一個執(zhí)行步驟。“在許多情況下，當算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時。因此隨機化算法可在很大程度上降低算法的復雜度。”（參考文獻：《計算機算法設計與分析（第3版）》）隨機化算法對問題用同一輸入算法求解時可能會得到完全不同的效果，這是它的基本特征——算法在執(zhí)行時產(chǎn)生真正隨機的結(jié)果。一般情況下，隨即算法分為兩大類——Las Vegas算法和Monte Carlo算法。Las Vegas算法不會得到不準確的結(jié)果，但有時卻會找不到解，這時就需要重復調(diào)用算法進行計算。而Monte Carlo算法用來求取問題的準確解。它能保證求得一個截但無法保證其正確性，這是Monte Carlo算法的主要缺點。不過由于每次執(zhí)行的算法都是獨立的，通過反復執(zhí)行算法可以有效的將發(fā)生錯誤的概率大大降低。另外，對于一個已經(jīng)有了平均性質(zhì)較好的確定性算法的問題，通過Sherwood隨機化方法可將確定性算法改成隨機算法，以解決其在最壞情況下效率不高的問題，提高了算法的性能。隨機化算法為很多用確定性算法難以很好的解決的難解問題提供了高效的解決途徑，具有很高的實用價值。 第六部分“NP完全性理論與近似算法”首先介紹了計算模型、確定性和非確定性圖靈（Turing）機。“在進行問題的計算復雜性分析之前，首先必須建立求解問題所用的計算模型，包括定義該計算模型中所用的基本運算，其目的是使問題的計算復雜性分析有一個共同的客觀尺度。”（參考文獻：《計算機算法設計與分析（第3版）》）隨機存取機RAM（Random Access Machine）、隨機存取存儲程序機RASP（Random Access Stored Program Machine）和圖靈機（Turing Machine）是三種基本的計算模型。RAM和RASP的相同處在于都有各種尋址指令且時間復雜性數(shù)量級相同，不同處在于RAM程序的不允許修改和RASP程序的可修改性。RAM程序和RASP程序之間可以相互模擬。圖靈機可以計算函數(shù)部分的遞歸函數(shù)，涉及到遞歸可枚舉集、遞歸集、原始遞歸集、部分遞歸函數(shù)、完全遞歸函數(shù)和原始遞歸函數(shù)。確定性圖靈機DTM和非確定性圖靈機NDTM的差別在于，NDTM的每一步動作允許有若干個選擇，且它的ID序列通常是由樹描述的，而DTM的ID序列是線性的。這部分接著又進一步深入介紹NP完全性理論和解NP難問題的近似算法。NP是能在多項式時間內(nèi)被一臺NDTM所接受的語言。NP完全問題是當前計算機算法領域的熱點研究課題。 第二部分 學習心得 學習之初剛開始看到那些函數(shù)以及一大堆數(shù)學公式的時候都覺得頭大，一時都摸不清這些復雜的式子是用來干什么的，甚至都以為學的不是算法而是高數(shù)了。后來在接觸到分治法等算法思想后，在老師講解的例子中學會了對那些式子的應用。課后也在實際的應用中真正掌握了第一部分所講的數(shù)學知識，懂得了那些數(shù)學基礎對算法研究的重要性。所以說，只有當自己學會在問題中運用了，才算是真正學會了那些知識。 算法的思想看著都似乎簡單易懂，就算思路復雜的只要認真研究也比較容易理解，但要真正的在實驗中、在實際問題的解決過程中運用出來就不是那么容易的一件事了。對于同一個問題，往往都有好幾種不同的算法，就像要求分別運用 KMP、Monte Carlo、Las Vegas算法解決同一個問題的實驗二一樣。每種算法都有各自的優(yōu)缺點，需要我們從算法的準確性和時間復雜度等多個方面進行權衡，從而找到最優(yōu)的算法。 第三部分 個人建議 一直以來都習慣于老師用PPT或者PDF課件上課，個人覺得上課看著屏幕上的Word文檔有點不大適應。特別是剛開始上課講函數(shù)的時候，那部分知識涉及比較復雜的數(shù)學計算，看得比較吃力。所以建議老師或許可以改用PPT課件作為教學的輔助工具，這樣我們課后打印課件進行復習的時候也會方便一點。 另外，對于課后老師布置的實驗題，做起來有難度而且很容易出現(xiàn)錯誤，耗費了不少時間。我覺得可以專門在機房上幾堂實驗課，大家在實驗中碰到錯誤可以及時的請教老師或者和同學討論。 第四部分 報告總結(jié) 繼上學期《數(shù)據(jù)結(jié)構與算法》課程的學習后，在《算法設計與分析》這門課程中我又更深入的學習了幾種算法常用技術，學會了運用這些典型方法設計算法和反洗算法的效率。將來不管是繼續(xù)讀研還是工作，對算法的理解和研究都是十分重要的。因此，在今后的學習和研究中，我也會繼續(xù)對算法的重視。在最后，也要感謝鄧老師繼《專業(yè)導論》后對我們這門課的辛苦教授。第二篇：排序算法總結(jié)
第三篇：51CTO下載-排序和算法總結(jié)
第四篇：10種排序算法總結(jié)
第五篇：算法導論學習報告[小編推薦]
點擊咨詢 