前言
本文將介紹常見的9種排序算法，圍繞下面幾個問題討論每一種排序算法:
這個算法的思想是什么?這個算法的穩定性怎樣?時間復雜度是多少?在什么情況下，算法出現最好情況or最壞情況?這個算法的具體實現?以下排序算法都以從小到大排序
１.冒泡排序(交換排序)
1.1算法思想:
排序每次對相鄰的兩個元素比較,如果它們的相對排列次序與所希望的不符，便交換它們的次序,這樣,各元素就會像水中冒氣泡一樣通過交換它們的位置得到最終正確的位置.升序時,每次都把最大的元素放到n-i-1個元素的位置上,每次遍歷的元素個數-1;
1.2 時間復雜度
最好的情況下：正序有序,則只需要比較n次，故為O(n) 最壞情況下:逆序有序,則需要比較(n-1)+(n-2)+…….+1，故為O(n*n)
1.3 穩定性
排序過程中只交換兩個元素的位置,因此,當兩個數相等時，是沒有必要交換兩個數的位置的,所以，它們相對位置并沒有改變,冒泡算法是穩定的。
1.4代碼實現
void BubbleSort(int a[],int n) //升序時,每次把最大的放到n-i-1個元素的位置上,每次遍歷的元素個數-1;{ int i,j,k; for(i=0;i<n;i++){ for(j=0;j<n-i-1;j++) { if(a[j] > a[j+1]) //比較找本趟最大關鍵字. { k=a[j]; //a[j]和a[j+1]交換 a[j]=a[j+1]; a[j+1]=k; } } }}2.直接選擇排序(選擇排序)
2.1算法思想
首先在未排序序列中找到最小元素,存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小的元素,然后放到排序序列的末尾。以此類推，直到所有的元素均排序完畢,具體的做法是:選擇最小的元素與未排列部分首部交換,使得序列的前面為有序。
2.2時間復雜度
最好的情況下,交換0次,但是每次都要找到最小的元素,因此大約把必須遍歷N*N次,因此為O(N*N)，減少了交換次數。
2.3穩定性
由于每次都是選擇未排序序列A中最小元素x與A中第一個元素交換,因此跨距離了,很可能破壞了元素間的相對位置,因此選擇排序是不穩定的.
2.4代碼實現
void SelectSort(int a[],int n){ int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++){ //升序時,每次把最小的放在最前面,每次遍歷的元素-1;從前面加 if(a[k] > a[j]) { k=j; } } if(k!=i) { temp = a[i]; a[i]=a[k]; a[j]=temp; } }}3.直接插入排序(插入排序)
3.1算法思想
將一組數據分成兩組,分別將其稱為有序組和待插入組,每次從待插入組中取出一個元素,與有序組的元素進行比較,并找到合適的位置,將該元素查到有序組中,就這樣,每次插入一個元素,有序組增加,待插入組減少,直到待插入組元素的個數為0,當然,插入過程中涉及到了元素的移動。
3.2算法時間復雜度
最好的情況下:正序有序(從小到大),這樣只需要比較n次,不需要移動,因此時間愛你復雜度為O(n); 最壞的情況下:逆序有序,這樣每一個元素就需要比較n次,共有n個元素,因此實際復雜復為O(n*n) 平均情況下:O(n*n)
3.3穩定性
在插入排序中,K1是已排好序部分中的元素,當K2與K1比較時,直接插到K1的后面(沒有必要插入到K1的前面,這樣做還需要移動元素),因此,插入排序是穩定的.
代碼實現
void InsertSort(int *num,int n){ int i = 0; int j = 0; int tmp = 0; for(int i = 1;i < n;i++){ tmp = num[i]; //從待插組中取出第一個元素 j = i-1; while(j >= 0 && tmp < num[j]) //注意判斷條件為兩個,j>=0為其邊界限制,第二個為插入判斷條件 { num[j+1] = num[j]; //若不是合適的位置,有序組元素向后移動. j--; } num[j+1] = tmp; //找到合適的位置,將元素插入. }}4.快速排序(交換排序)
4.1算法思想
它是由冒泡排序改進而來的,在待排序的n個記錄中取一個記錄(通常取第一個記錄)，把該記錄放入適當位置后,數據序列被此記錄劃分成兩部分,所有關鍵字比該關鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸為),這個過程稱為一趟快速排序。
4.2算法復雜度
最好的情況下:因為每次都將序列化分為兩部分(一般二分復雜度都和logN相關),故為O(N(*logN) 最壞的情況下:基本有序時m退化為冒泡排序,幾乎要比較N*N此,故為O(N*N)
4.3 穩定性
由于每次都需要和中軸元素交換,因此原來的順序就可能被打亂,如5 3 3 4 3 8 9 10 11 會將3的順序打亂,所以說，快速排序是不穩定的。
4.4 代碼實現
void QuickSort(int a[],int low,int high){ int i=low,j=high; if(low <high) { int temp=a[low]; while( i < j ) { while(a[j] > temp && i < j){ j--; } a[i] = a[j]; while(a[i] <=temp && i<j){ i++; } a[j]=a[i]; } a[i]=temp; QuickSort(a,low,i-1); QuickSort(a,i+1,high); }}5.歸并排序
5.1算法思想:將待排序的集合一分為二,直到排序集合就剩下一個元素為止,然后不斷合并兩個排好序的數組.(先分割后合并)
5.2算法時間復雜度
最好的情況下:一趟歸并需要n次,總共需要logN次,因此為O(N*logN) 最壞的情況下:接近于平均情況下,為O(N*logN) 說明:對長度為n的文件,需要進行logN趟二路歸并,每趟歸并的時間為O(n),故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlogn).
5.3 穩定性
歸并排序最大的特色就是它是一種穩定的排序算法,歸并過程中是不會改變元素的相對位置的。 缺點：它需要O(n)的額外空間,但是很適合于多鏈表排序
5.4 代碼實現
int merge(int a[],int low,int mid,int high){ //對排好序的兩個分組進行合并 int i=low,j=mid+1,p=0; int *temp=(int *)malloc(sizeof(int)); //開辟臨時數組存合并后的元素。 if(temp == NULL){ return -1; } while(i<=mid && j<=high){ temp[p++]=((a[i]<=a[j])?a[i++]:a[j++]); } while(i<=mid){ temp[p++]=a[i++]; } while(j<=high){ temp[p++]=a[j++]; } for(p=0,i=low;i<=high;i++,p++){ a[i]=temp[p]; } free(temp);}void mergeSort(int a[],int low,int high){ int mid=(low + high)/2; if(low < high) //說明此時只剩下一個元素，不用再分。 { mergeSort(a,low,mid); //對左邊的元素依然進行分， mergeSort(a,mid+1,high); merge(a,low,mid,high); }}如下圖所示: 
6.希爾排序(插入排序)
6.1算法思想
希爾排序也是一種插入排序算法,實際上是一種分組插入方法,先取定一個小于n的整數d1作為第一個增量,把表的全部記錄分成d1個組,所有距離d1的倍數的記錄放在同一個組中,在各組內進行直接插入排序,然后,取第二個增量d2(
6.2 時間復雜度
最好情況:希爾排序的好壞和步長的選擇有關,目前還沒有得出最好的步長如何選擇,因此最好情況下的算法時間復雜度不確定. 最壞情況下:O(N*logN) 平均情況下:O(N*logN)
6.3 穩定性
由于多次插入排序,我們知道一次插入排序是穩定的,不會改變ｖｘｉａｎｇｔ元素的相對順序,但是在不同的插入排序中,相同的元素可能在各自的插入排序中移動,最后穩定性會被打亂,所以希爾排序是不穩定的. 看一個簡單的例子: 以n=10的一個數組49,38,65,97,26,13,27,49,55,4為例 第一次gap = 10 /2 =5;
6.4 代碼實現
//完全按照定義實現.void shellSort1(int a[],int n){ int i,j,gap; for(gap = n/2;gap > 0;gap/=2){ for(i=0;i<gap;i++){ for(j = i+gap;j<n;j+=gap){ if(a[j] < a[j-gap]){ int temp = a[j]; int k = j - gap; while(k >= 0 && a[k] > temp){ a[k+gap] = a[k]; k-=gap; } a[k+gap] = temp; } } } }}//簡化版的希爾排序,相當于是所有的分組同時比較,比如說當gap 為2時,第一種方法是1,3,5,7,9插入排序完，在進行2,4,6,8,10進行排序,而當前的方法是1,３排序完,接著排2,4然后又排,1,3,5，然后又是2,4,6,以此類推,所有的組同時進行。void shellSort2(int a[],int n){ int j,gap; for(gap = n/2;gap > 0;gap /=2){ for(j = gap;j<n;j++){ if(a[j] < a[j - gap]){ int temp = a[j]; int k = j - gap; while(k >= 0 && a[k] > temp){ a[k+gap] = a[k]; k-=gap; } a[k + gap] = temp; } } }}7.堆排
7.1算法解析
建初始堆(以頂堆為例),這一步驟把初始化序列建成了一個滿足大頂堆性質的序列,且每顆子樹都滿足,這個時候堆頂是本序列中最大的元素,因此將最后一個元素和堆頂元素調換,把最大值放在最終的位置上,建立好了初始堆,就保留了排序時的比較結果,后面的調整都可以再此基礎上進行,加快排序效率.由于每次將堆頂元素和最后一個對調,破壞了堆的性質,因此要從新向下調整,建立大頂堆(這里在初始化堆的基礎上,只要將堆頂元素調到合適的位置即可).調整完了之后,又將堆頂元素和未序區間的最后一個元素對調,重復2,3直到堆中剩余一個元素. 7.2 算法時間復雜度
最壞情況下,接近于最好情況下,因此是一種不穩定的排序.
穩定性
堆排序需要不斷的調整堆,因此它是一種不穩定的排序.
代碼如下
大頂堆:
void AdjustDown(int A[],int k,int len){ A[0] = A[k]; //保存子堆的父節點 for(int i=2*k;i <= len;i*=2){ if(i < len && A[i] < A[i+1]){ //尋找較大的孩子. i++; } if(A[0] > A[i]){ break; }else{ A[k] = A[i]; //孩子上調 k = i; } } A[k] = A[0];}void BuildMaxHeap(int A[],int len){ for(int i =len/2;i>0;i--){ AdjustDown(A,i,len); //向下調整. }}void HeapSort(int A[],int len){ BuildMaxHeap(A,len); for(int i = len; i>1;i--){ A[0] = A[1]; A[1] = A[i]; A[i] = A[0]; //堆頂和未序區間尾元素對調 AdjustDown(A,1,i-1); }}
