排序算法匯總總結

1、排序算法匯總總結一、插入排序直接插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。代碼實現(xiàn)：#include <stdio.h>#include <stdlib.h>void swap(int *p1, int *p2) int temp; temp=*p1; *p1=*p2; *p

2、2=temp;void insertSort(int *a,int len) int i,j; for(i=0;i<len;i+) for(j=i+1;j>=1;j-) if(aj<aj-1) swap(&aj,&aj-1); 希爾排序，也稱遞減增量排序算法，是插入排序的一種高速而穩(wěn)定的改進版本。它的基本思想是先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<<

3、;d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。該方法實質(zhì)上是一種分組插入方法。代碼實現(xiàn)：#include <stdio.h>#include <stdlib.h>void swap(int *p1, int *p2) int temp; temp=*p1; *p1=*p2; *p2=temp;void shell(int *a,int d,int len) int i,j; for(i=d+1;i<len;i+) for(j=i+d;j>=i && j<len;j-) if(aj<aj-d) swap(&

4、;aj,&aj-d); void shellSort(int *a,int d,int len) while(d>=1) shell(a,d,len); d=d/2; 二、交換排序冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。代碼實現(xiàn)：(swap函數(shù)同前 以后同)void bubbleSort(int *a,int len) int i,j,chan

5、ge; for(i=0;i<len;i+) change=0; for(j=len-1;j>i;j-) if(aj<aj-1) change=1; swap(&aj,&aj-1); if(!change) break; 快速排序是由東尼·霍爾所發(fā)展的一種排序算法 基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。代碼實現(xiàn)：int partition(int *a,int s,int e) i

6、nt roll=as,i,j; for(i=s+1,j=i;i<=e;i+) if(ai<roll) swap(&ai,&aj); j+; swap(&as,&aj-1); return j-1;void quickSort(int *a, int start,int end) if(start<=end) int split=partition(a,start,end); quickSort(a,start,split-1); quickSort(a,split+1,end); 三、選擇排序直接選擇排序(Selection sort)是一種簡

7、單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾(目前已被排序的序列)。以此類推，直到所有元素均排序完畢。代碼實現(xiàn)：void selectSort(int *a, int len) int i,j,min,mark; for(i=0;i<len;i+) min=ai; for(j=i+1;j<len;j+) if(aj<min) min=aj; mark=j if(min!=ai) swap(&ai,&amark); 堆排序（Heapsort）是指利用

8、堆這種數(shù)據(jù)結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆性質(zhì)：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點代碼實現(xiàn)：void shift(int *a,int r,int len) int j,maxid; for(j=r;j<=len/2;) maxid=j; if(2*j<len && a2*j>aj) maxid=2*j; if(2*j+1<len && a2*j+1>amaxid) maxid=2*j+1; if(maxid!=j) swap(&amaxid,&aj); void

9、buildHeap(int *a, int len) /為便宜計算 a的下標從1開始 構建大頂堆 int i; for(i=len/2;i>0;i-) shift(a,i,len);void heapSort(int *a, int len) int clen; buildHeap(a,len); swap(&a1,&alen); for(clen=len-1;clen>0;clen-) shift(a,1,clen); swap(&a1,&aclen); 四、歸并排序歸并排序（Merge sort，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的

10、排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。算法描述歸并操作的過程如下：1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列2. 設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置4. 重復步驟3直到某一指針達到序列尾5. 將另一序列剩下的所有元素直接復制到合并序列尾代碼實現(xiàn)：void merge(int *a,int start,int mid,int end) if(start>mid | mid >end ) return

11、; int i=start,j=mid+1,k=0; int *L=(int *)malloc(end-start+1)*sizeof(int); while(i<=mid && j<=end) if(ai<aj) Lk+=ai+; else Lk+=aj+; while(i<=mid) Lk+=ai+; while(j<=end) Lk+=aj+; for(i=start,j=0;i<=end;i+,j+) ai=Lj; free(L);void mergeSort(int *a, int start,int end) if(start&l

12、t;end) int mid=(start+end)/2; mergeSort(a,start,mid); mergeSort(a,mid+1,end); merge(a,start,mid,end); 五、基數(shù)排序基數(shù)排序(Radix sort)是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。算法實現(xiàn)（未驗證正確性）：struct DNode int data; DNode *next;struct Table int id; DNode *fisrt;i

13、nt digit(int num,int loc) for(int i=1;i<loc;i+) num/=10; int res=num%10; return res;int maxCount(int *a,int len) int max=0,n,num; for(int i=0;i<len;i+) n=0; num=ai; while(num) num/=10; n+; if(n>max) max=n; return max;void radixSort(int *a,int len) int maxloc=maxcount(a,len); DNode *ptemp; T

14、able *t=(Table *)malloc(10 * sizeof(Table); for(int i=0;i<10;i+) ti->id=i; ti->first=NULL; for(int j=1;j<maxcount;j+) for(int k=0;k<len;k+) int idm=digit(ak,j); DNode *p=tidm->first; while(pt->next!=NULL) p=p->next; DNode *d=(DNode *)malloc(sizeof(DNode); d->data=ak; d->

15、;next=p->next; p->next=d; for(int i=0,k=0;i<=9;i+) while(ti->first!=NULL) ak-=ti->first->data; ptemp=ti->first; ti->first=ti->first->next; free(ptemp); 六、排序算法特點，算法復雜度和比較直接插入排序如果目標是把n個元素的序列升序排列，那么采用直接插入排序存在最好情況和最壞情況。最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降

16、序排列，那么此時需要進行的比較共有n(n-1)/2次。直接插入排序的賦值操作是比較操作的次數(shù)減去(n-1)次。平均來說直接插入排序算法復雜度為O(n2)。因而，直接插入排序不適合對于數(shù)據(jù)量比較大的排序應用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級小于千，那么直接插入排序還是一個不錯的選擇。 插入排序在工業(yè)級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）。希爾排序希爾排序是基于插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間復雜度為 O(N*(logN)2)

17、， 沒有快速排序算法快 O(N*(logN)，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(N2）復雜度的算法快得多。并且希爾排序非常容易實現(xiàn)，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時快速排序在最壞 的情況下執(zhí)行的效率會非常差。專家們提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快， 再改成快速排序這樣更高級的排序算法.希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺?/p>

18、所以，希爾排序的時間復雜度會比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的冒泡排序時間復雜度為O（n2），雖然不及堆排序、快速排序的O（nlogn，底數(shù)為2），但是有兩個優(yōu)點：1.“編程復雜度”很低，很容易寫出代碼；2.具有穩(wěn)定性。其中若記錄序列的初始狀態(tài)為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態(tài)為"逆序"，則需進行

19、n(n-1）/2次比較和記錄移動。因此冒泡排序總的時間復雜度為O(n*n)?？焖倥判?在最好的情況，每次我們執(zhí)行一次分割，我們會把一個數(shù)列分為兩個幾近相等的片段。這個意思就是每次遞回調(diào)用處理一半大小的數(shù)列。因此，在到達大小為一的數(shù)列前，我們只要作 log n 次巢狀的調(diào)用。這個意思就是調(diào)用樹的深度是O(log n)。但是在同一階層的兩個程序調(diào)用中，不會處理到原來數(shù)列的相同部份；因此，程序調(diào)用的每一階層總共全部僅需要O(n)的時間（每個調(diào)用有某些共同的額外耗費，但是因為在每一階層僅僅只有O(n)個調(diào)用，這些被歸納在O(n)系數(shù)中）。結果是這個算法僅需使用O(n log n)時間。另外一個方法是為

20、T(n)設立一個遞回關系式，也就是需要排序大小為n的數(shù)列所需要的時間。在最好的情況下，因為一個單獨的快速排序調(diào)用牽涉了O(n)的工作，加上對n/2大小之數(shù)列的兩個遞回調(diào)用，這個關系式可以是：T(n) = O(n) + 2T(n/2)解決這種關系式型態(tài)的標準數(shù)學歸納法技巧告訴我們T(n) = O(n log n)。事實上，并不需要把數(shù)列如此精確地分割；即使如果每個基準值將元素分開為 99% 在一邊和 1% 在另一邊，調(diào)用的深度仍然限制在 100log n，所以全部執(zhí)行時間依然是O(n log n)。然而，在最壞的情況是，兩子數(shù)列擁有大各為 1 和 n-1，且調(diào)用樹（call tree）變成為一個

21、 n 個巢狀（nested）呼叫的線性連串（chain）。第 i 次呼叫作了O(n-i)的工作量，且遞回關系式為：T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)這與插入排序和選擇排序有相同的關系式，以及它被解為T(n) = O(n2)。討論平均復雜度情況下，即使如果我們無法隨機地選擇基準數(shù)值，對于它的輸入之所有可能排列，快速排序仍然只需要O(n log n)時間。因為這個平均是簡單地將輸入之所有可能排列的時間加總起來，除以n這個因子，相當于從輸入之中選擇一個隨機的排列。當我們這樣作，基準值本質(zhì)上就是隨機的，導致這個算法與亂數(shù)快速排序有一樣的執(zhí)行時

22、間。更精確地說，對于輸入順序之所有排列情形的平均比較次數(shù)，可以借由解出這個遞回關系式可以精確地算出來。在這里，n-1 是分割所使用的比較次數(shù)。因為基準值是相當均勻地落在排列好的數(shù)列次序之任何地方，總和就是所有可能分割的平均。這個意思是，平均上快速排序比理想的比較次數(shù)，也就是最好情況下，只大約比較糟39%。這意味著，它比最壞情況較接近最好情況。這個快速的平均執(zhí)行時間，是快速排序比其他排序算法有實際的優(yōu)勢之另一個原因。討論空間復雜度時 被快速排序所使用的空間，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何遞回呼叫前，僅會使用固定的額外空間。然而，如果需要產(chǎn)生O(log

23、n)巢狀遞回呼叫，它需要在他們每一個儲存一個固定數(shù)量的資訊。因為最好的情況最多需要O(log n)次的巢狀遞回呼叫，所以它需要O(log n)的空間。最壞情況下需要O(n)次巢狀遞回呼叫，因此需要O(n)的空間。然而我們在這里省略一些小的細節(jié)。如果我們考慮排序任意很長的數(shù)列，我們必須要記住我們的變量像是left和right，不再被認為是占據(jù)固定的空間；也需要O(log n)對原來一個n項的數(shù)列作索引。因為我們在每一個堆?？蚣苤卸加邢襁@些的變量，實際上快速排序在最好跟平均的情況下，需要O(log2 n)空間的位元數(shù)，以及最壞情況下O(n log n)的空間。然而，這并不會太可怕，因為如果一個數(shù)列

24、大部份都是不同的元素，那么數(shù)列本身也會占據(jù)O(n log n)的空間字節(jié)。非原地版本的快速排序，在它的任何遞回呼叫前需要使用O(n)空間。在最好的情況下，它的空間仍然限制在O(n)，因為遞回的每一階中，使用與上一次所使用最多空間的一半，且它的最壞情況是很恐怖的，需要空間，遠比數(shù)列本身還多。如果這些數(shù)列元素本身自己不是固定的大小，這個問題會變得更大；舉例來說，如果數(shù)列元素的大部份都是不同的，每一個將會需要大約O(log n)為原來儲存，導致最好情況是O(n log n)和最壞情況是O(n2 log n)的空間需求。直接選擇排序選擇排序的交換操作介于0和(n-1)次之間。選擇排序的比較操作為n(n

25、-1)/2次之間。選擇排序的賦值操作介于0和3(n-1)次之間。比較次數(shù)O(n2),比較次數(shù)與關鍵字的初始狀態(tài)無關，總的比較次數(shù)N=(n-1)+(n-2)+.+1=n*(n-1)/2。 交換次數(shù)O(n),最好情況是，已經(jīng)有序，交換0次；最壞情況是，逆序，交換n-1次。 交換次數(shù)比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。堆排序堆排序的平均時間復雜度為(nlogn)，空間復雜度為(1)。由于它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數(shù)為(nlog2n)。它是對數(shù)據(jù)的有序性不敏感的一種算法。但堆排序?qū)⑿枰?/p>

26、兩個步驟：是建堆，二是排序（調(diào)整堆）。所以一般在小規(guī)模的序列中不合適，但對于較大的序列，將表現(xiàn)出優(yōu)越的性能。 歸并排序歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸并，將有無比的優(yōu)勢。其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數(shù)據(jù)的有序性不敏感。若數(shù)據(jù)節(jié)點數(shù)據(jù)量大，那將不適合?；鶖?shù)排序基數(shù)排序的時間復雜度是 O(k·n)，其中n是排序元素個數(shù)，k是數(shù)字位數(shù)。注意這不是說這個時間復雜度一定優(yōu)于O(n·log(n)，因為k的大小一般會受到 n 的影響。 以排序n個不同整數(shù)來舉例，假定這些整數(shù)以B為底，這樣

27、每位數(shù)都有B個不同的數(shù)字，k就一定不小于logB(n)。由于有B個不同的數(shù)字，所以就需要B個不同的桶，在每一輪比較的時候都需要平均n·log2(B) 次比較來把整數(shù)放到合適的桶中去，所以就有：· k 大于或等于 logB(n)· 每一輪(平均)需要 n·log2(B) 次比較所以，基數(shù)排序的平均時間T就是：T logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·l

28、og2(n)所以和比較排序相似，基數(shù)排序需要的比較次數(shù)：T n·log2(n)。 故其時間復雜度為 (n·log2(n) = (n·log n) 。七、不同條件下，排序方法的選擇(1)若n較小(如n50)，可采用直接插入或直接選擇排序。 當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插入，應選直接選擇排序為宜。 (2)若文件初始狀態(tài)基本有序(指正序)，則應選用直接插入、冒泡或隨機的快速排序為宜；(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。 快速排序是目前基于比較的內(nèi)部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短； 堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。 若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的 排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸