http://www.cnblogs.com/biyeymyhjob/archive/2012/07/17/2591457.html

?

排序算法匯總總結

一、插入排序

?

直接插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

代碼實現：

#include <stdio.h> #include <stdlib.h>void swap(int *p1, int *p2) {int temp;temp=*p1;*p1=*p2;*p2=temp; }void insertSort(int *a,int len) {int i,j;for(i=0;i<len;i++){for(j=i+1;j>=1;j--){if(a[j]<a[j-1])swap(&a[j],&a[j-1]); }} }

?

?

希爾排序，也稱遞減增量排序算法，是插入排序的一種高速而穩定的改進版本。它的基本思想是先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。該方法實質上是一種分組插入方法。

代碼實現：

#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 (a[j] < a[j-d]) {swap(&a[j], &a[j-d]);
}} } }void shellSort(int *a, int d, int len) {while (d >= 1) {shell(a, d, len);d = d / 2;} }

?

二、交換排序

?冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

代碼實現：(swap函數同前 以后同)

void bubbleSort(int *a,int len) {int i,j,change;for(i=0;i<len;i++){change=0;for(j=len-1;j>i;j--){if(a[j]<a[j-1]){change=1;swap(&a[j],&a[j-1]);}} if(!change)break;} }

?

快速排序是由東尼·霍爾所發展的一種排序算法?? 基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

?

代碼實現：

int partition(int *a ,int s, int e) {int roll=a[s], i, j;for (i=s+1,j=i ;i<=e; i++){if (a[i] < roll){swap(&a[i],&a[j]);j++;}}swap(&a[s],&a[j-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)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾(目前已被排序的序列)。以此類推，直到所有元素均排序完畢。

?

代碼實現：

void selectSort(int *a, int len) {int i,j,min,mark;for(i=0;i<len;i++){min=a[i];for(j=i+1;j<len;j++){if(a[j]<min){min=a[j];mark=j}}if(min!=a[i])swap(&a[i],&a[mark]);} }

?

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點

代碼實現：

void shift(int *a,int r,int len) {int j,maxid;for(j=r;j<=len/2;){maxid=j;if(2*j<len && a[2*j]>a[j])maxid=2*j;if(2*j+1<len && a[2*j+1]>a[maxid])maxid=2*j+1;if(maxid!=j){swap(&a[maxid],&a[j]);}}}void 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(&a[1],&a[len]);for(clen=len-1;clen>0;clen--){shift(a,1,clen);swap(&a[1],&a[clen]);}}

?

四、歸并排序

歸并排序（Merge sort，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

算法描述

歸并操作的過程如下：

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

重復步驟3直到某一指針達到序列尾

將另一序列剩下的所有元素直接復制到合并序列尾

代碼實現：

void merge(int *a,int start,int mid,int end) {if(start>mid || mid >end ) return;int i=start,j=mid+1,k=0;int *L=(int *)malloc((end-start+1)*sizeof(int));while(i<=mid && j<=end){if(a[i]<a[j]){L[k++]=a[i++];}else{L[k++]=a[j++];}}while(i<=mid)L[k++]=a[i++];while(j<=end)L[k++]=a[j++];for(i=start,j=0;i<=end;i++,j++){a[i]=L[j];}free(L); }void mergeSort(int *a, int start,int end) {if(start<end){int mid=(start+end)/2;mergeSort(a,start,mid);mergeSort(a,mid+1,end);merge(a,start,mid,end);} }

?

五、基數排序

基數排序(Radix sort)是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。

算法實現（未驗證正確性）：

struct DNode {int data;DNode *next; }struct Table {int id;DNode *fisrt; }int 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=a[i];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;Table *t=(Table *)malloc(10 * sizeof(Table));for(int i=0;i<10;i++){t[i]->id=i;t[i]->first=NULL;} for(int j=1;j<maxcount;j++){for(int k=0;k<len;k++){int idm=digit(a[k],j);DNode *p=t[idm]->first;while(pt->next!=NULL) p=p->next;DNode *d=(DNode *)malloc(sizeof(DNode));d->data=a[k];d->next=p->next;p->next=d;}for(int i=0,k=0;i<=9;i++){while(t[i]->first!=NULL){a[k--]=t[i]->first->data;ptemp=t[i]->first;t[i]->first=t[i]->first->next;free(ptemp);}}} }

?

六、排序算法特點，算法復雜度和比較

直接插入排序

如果目標是把n個元素的序列升序排列，那么采用直接插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。直接插入排序的賦值操作是比較操作的次數減去(n-1)次。平均來說直接插入排序算法復雜度為O(n²)。因而，直接插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么直接插入排序還是一個不錯的選擇。 插入排序在工業級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）。

?

希爾排序

希爾排序是基于插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間復雜度為?O(N*(logN)2)， 沒有快速排序算法快?
O(N*(logN))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。但是比O(N2）復雜度的算法快得多。并且希爾排序非常容易實現，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞 的情況下執行的效率會非常差。專家們提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快， 再改成快速排序這樣更高級的排序算法.

希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的

?

冒泡排序

時間復雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數為2），但是有兩個優點：1.“編程復雜度”很低，很容易寫出代碼；2.具有穩定性。

其中若記錄序列的初始狀態為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態為"逆序"，則需進行n(n-1）/2次比較和記錄移動。因此冒泡排序總的時間復雜度為O(n*n)。

?

快速排序?

在最好的情況，每次我們執行一次分割，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞回調用處理一半大小的數列。因此，在到達大小為一的數列前，我們只要作 log?n?次巢狀的調用。這個意思就是調用樹的深度是O(log?n)。但是在同一階層的兩個程序調用中，不會處理到原來數列的相同部份；因此，程序調用的每一階層總共全部僅需要O(n)的時間（每個調用有某些共同的額外耗費，但是因為在每一階層僅僅只有O(n)個調用，這些被歸納在O(n)系數中）。結果是這個算法僅需使用O(n?log?n)時間。

另外一個方法是為T(n)設立一個遞回關系式，也就是需要排序大小為n的數列所需要的時間。在最好的情況下，因為一個單獨的快速排序調用牽涉了O(n)的工作，加上對n/2大小之數列的兩個遞回調用，這個關系式可以是：

T(n) = O(n) + 2T(n/2)

解決這種關系式型態的標準數學歸納法技巧告訴我們T(n) = O(n?log?n)。

事實上，并不需要把數列如此精確地分割；即使如果每個基準值將元素分開為 99% 在一邊和 1% 在另一邊，調用的深度仍然限制在 100log?n，所以全部執行時間依然是O(n?log?n)。

然而，在最壞的情況是，兩子數列擁有大各為 1 和?n-1，且調用樹（call tree）變成為一個?n?個巢狀（nested）呼叫的線性連串（chain）。第?i?次呼叫作了O(n-i)的工作量，且遞回關系式為：

T(n) = O(n) + T(1) + T(n?- 1) = O(n) + T(n?- 1)

這與插入排序和選擇排序有相同的關系式，以及它被解為T(n) = O(n²)。

?

討論平均復雜度情況下，即使如果我們無法隨機地選擇基準數值，對于它的輸入之所有可能排列，快速排序仍然只需要O(n?log?n)時間。因為這個平均是簡單地將輸入之所有可能排列的時間加總起來，除以n這個因子，相當于從輸入之中選擇一個隨機的排列。當我們這樣作，基準值本質上就是隨機的，導致這個算法與亂數快速排序有一樣的執行時間。

更精確地說，對于輸入順序之所有排列情形的平均比較次數，可以借由解出這個遞回關系式可以精確地算出來。

在這里，n-1?是分割所使用的比較次數。因為基準值是相當均勻地落在排列好的數列次序之任何地方，總和就是所有可能分割的平均。

這個意思是，平均上快速排序比理想的比較次數，也就是最好情況下，只大約比較糟39%。這意味著，它比最壞情況較接近最好情況。這個快速的平均執行時間，是快速排序比其他排序算法有實際的優勢之另一個原因。

討論空間復雜度時 被快速排序所使用的空間，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何遞回呼叫前，僅會使用固定的額外空間。然而，如果需要產生O(log?n)巢狀遞回呼叫，它需要在他們每一個儲存一個固定數量的資訊。因為最好的情況最多需要O(log?n)次的巢狀遞回呼叫，所以它需要O(log?n)的空間。最壞情況下需要O(n)次巢狀遞回呼叫，因此需要O(n)的空間。

然而我們在這里省略一些小的細節。如果我們考慮排序任意很長的數列，我們必須要記住我們的變量像是left和right，不再被認為是占據固定的空間；也需要O(log?n)對原來一個n項的數列作索引。因為我們在每一個堆棧框架中都有像這些的變量，實際上快速排序在最好跟平均的情況下，需要O(log²?n)空間的位元數，以及最壞情況下O(n?log?n)的空間。然而，這并不會太可怕，因為如果一個數列大部份都是不同的元素，那么數列本身也會占據O(n?log?n)的空間字節。

非原地版本的快速排序，在它的任何遞回呼叫前需要使用O(n)空間。在最好的情況下，它的空間仍然限制在O(n)，因為遞回的每一階中，使用與上一次所使用最多空間的一半，且

它的最壞情況是很恐怖的，需要

空間，遠比數列本身還多。如果這些數列元素本身自己不是固定的大小，這個問題會變得更大；舉例來說，如果數列元素的大部份都是不同的，每一個將會需要大約O(log?n)為原來儲存，導致最好情況是O(nlog?n)和最壞情況是O(n²?log?n)的空間需求。

?

?

直接選擇排序

選擇排序的交換操作介于0和(n-1)次之間。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介于0和3(n-1)次之間。

比較次數O(n^2),比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交換次數O(n),最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。 交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。

?

堆排序

堆排序的平均時間復雜度為Ｏ(nlogn)，空間復雜度為Ｏ(1)。

由于它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數為Ｏ(nlog2n)。它是對數據的有序性不敏感的一種算法。但堆排序將需要做兩個步驟：－是建堆，二是排序（調整堆）。所以一般在小規模的序列中不合適，但對于較大的序列，將表現出優越的性能。

?

歸并排序

歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸并，將有無比的優勢。其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數據的有序性不敏感。若數據節點數據量大，那將不適合。

?

基數排序

基數排序的時間復雜度是 O(k·n)，其中n是排序元素個數，k是數字位數。注意這不是說這個時間復雜度一定優于O(n·log(n))，因為k的大小一般會受到 n 的影響。 以排序n個不同整數來舉例，假定這些整數以B為底，這樣每位數都有B個不同的數字，k就一定不小于log_B(n)。由于有B個不同的數字，所以就需要B個不同的桶，在每一輪比較的時候都需要平均n·log₂(B) 次比較來把整數放到合適的桶中去，所以就有：

• k?大于或等于 log_B(n)
• 每一輪(平均)需要?n·log₂(B) 次比較

所以，基數排序的平均時間T就是：

T?≥ log_B(n)·n·log₂(B) = log₂(n)·log_B(2)·n·log₂(B) = log₂(n)·n·log_B(2)·log₂(B) =n·log₂(n)

所以和比較排序相似，基數排序需要的比較次數：T?≥?n·log₂(n)。 故其時間復雜度為Ω(n·log₂(n)) =?Ω(n·log?n)?。

?

?七、不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 ??? 　

當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插入，應選直接選擇排序為宜。

(2)若文件初始狀態基本有序(指正序)，則應選用直接插入、冒泡或隨機的快速排序為宜；

(3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。 ??? 　

快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短； ??? 　

堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。 ??? 　

若要求排序穩定，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的? 排序算法并不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩定的，所以改進后的歸并排序仍是穩定的。

(4)在基于比較的排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。 ??? 　

當文件的n個關鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要O(nlgn)的時間。 ??? 　

箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用于像字符串和整數這類有明顯結構特征的關鍵字，而當關鍵字的取值范圍屬于某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有借助于"比較"的方法來排序。 ??? 　

若n很大，記錄的關鍵字位數較少且可以分解時，采用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。

(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸并、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序算法變得復雜。此時可考慮用其它排序。

(6)本章給出的排序算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸并排序、基數排序都易于在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實現，在這種情況下，可以提取關鍵字建立索引表，然后對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束后，向量t就指示了記錄之間的順序關系： ???????

R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key ?

若要求最終結果是： ??????

R[0].key≤R[1].key≤…≤R[n-1].key

則可以在排序結束后，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

?

?

八、各排序算法時間復雜度和空間復雜度

?

???????

轉載于:https://www.cnblogs.com/virusolf/p/4958051.html

總結

以上是生活随笔為你收集整理的排序算法汇总总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。