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