摘要：堆排序其實類似簡單選擇排序，每次找出最大最小元素，移到特定位置完成排序。排序算法平均情況最好情況最壞情況輔助空間穩(wěn)定性冒泡排序穩(wěn)定簡單選擇排序穩(wěn)定直接插入排序穩(wěn)定希爾排序不穩(wěn)定堆排序不穩(wěn)定歸并排序穩(wěn)定快速排序不穩(wěn)定參考大話數(shù)據(jù)結(jié)構(gòu)算法。
排序算法
時間復(fù)雜度O(n^2)的排序
1.冒泡排序
冒泡排序通過兩兩比較相鄰記錄的關(guān)鍵字，反序則交換，從而達到排序的效果
for(int i=0; io[j+1]){
swap(o,j,j+1);
}
}
}
上面的代碼有個小問題，設(shè)想存在待排序序列{1，3，5，7，11，9}，經(jīng)過第一遍遍歷交換11和9之后已經(jīng)達到排序效果，接下來的遍歷已無意義。考慮增加一個標志位，若上一輪遍歷沒有引起序列任何變化，則退出整個遍歷，不再做無意義的比較。
boolean flag = true;
for(int i=0; io[j+1]){
swap(o,j,j+1);
flag = true;
}
}
}
冒泡排序還有幾種變形，或是向上冒泡、向下冒泡，但都差別不大。分析時間復(fù)雜度：最好情況下無需交換，只要進行n-1次比較，時間復(fù)雜度O(n);最壞情況下，即待排序序列為逆序，需要比較n*(n-1)/2次，并作等數(shù)量級的交換，時間復(fù)雜度O(n^2)。
2.簡單選擇排序
與冒泡排序區(qū)別的是，冒泡排序只要發(fā)現(xiàn)反序就會交換相鄰的兩個數(shù)，而簡單選擇排序是先找出最小或最大的數(shù)，與特定位置交換，可以看出其優(yōu)點是交換移動次數(shù)相當少。
int min;
for(int i=0; io[j]){
min = j;
}
}
if(min != i){
swap(o,min,i);
}
}
分析簡單選擇排序的復(fù)雜度，無論最好最壞情況下，比較次數(shù)都是n*(n-1)/2，但最好情況下交換0次，最壞情況也只有n-1次，總的復(fù)雜度仍是O(n^2)。
3.直接插入排序
直接插入排序的思想是向一個有序序列逐步插入記錄，得到記錄數(shù)不斷增加的序列，若初始為亂序序列，則選取第一個元素作為一個有序序列，其他元素依次插入這個有序序列，從而達到排序效果。
int j,temp;
for(int i=1; i=0&&o[j]>temp; j--){
o[j+1] = o[j];
}
o[j+1] = temp;
}
}
直接插入與理撲克牌有點相似，最好情況下需要比較n-1次，無需交換；最壞情況下比較(n+2)(n-1)/2次，移動(n+4)(n-1)/2次。
時間復(fù)雜度O(n^3/2)的排序
1.希爾排序
希爾排序是基于直接插入排序的，直接插入排序在元素較少和元素基本有序時效率是不錯的，但隨著元素增多和有序性破壞，效率會下降的很明顯。希爾排序通過分組實現(xiàn)跳躍式移動，保證待排序序列基本有序后再排序，就能提高效率。
int j,temp;
int increment = o.length;
do{
increment = increment/3+1;
for(int i=increment; i=0&&o[j]>temp; j-=increment){
o[j+increment] = o[j];
}
o[j+increment] = temp;
}
}while(increment>1);
希爾排序的關(guān)鍵在于增量increment的選擇，最壞情況下，可以取得時間復(fù)雜度O(n^3/2)的算法。
時間復(fù)雜度O(nlgn)的排序
1.堆排序
堆是特殊的完全二叉樹，每個節(jié)點的值都大于等于（小于等于）其左右孩子節(jié)點的值。堆排序其實類似簡單選擇排序，每次找出最大最小元素，移到特定位置完成排序。堆排序相對于簡單選擇排序的優(yōu)點是，之前排序的結(jié)果得以保存，能被后面的排序利用。
//堆排序
for(int i=o.length/2-1; i>=0; i--){
//從最后一個有子節(jié)點的節(jié)點開始依次往前調(diào)整對應(yīng)節(jié)點來生成大頂堆
heapAdjust(o,i,o.length-1);
}
for(int i=0; io[i]){
swap(o,m,i);
}
i = m;
}
}
堆排序的時間復(fù)雜度主要取決于構(gòu)建堆和重建堆兩部分，構(gòu)建堆的時間復(fù)雜度O(n^2),重建堆的時間復(fù)雜度為O(nlgn),總的時間復(fù)雜度為O(nlgn)。
2.歸并排序
歸并排序的思想是逐層將序列子元素兩兩歸并成有序序列，每個子序列長度經(jīng)歷1、2、4、...、n，最后得到完整有序序列。
int[] sort(int[] o,int m,int n){
int mid;
int[] result = new int[o.length];
if(o.length == 1|| m==n){
result[0] = o[0];
}else{
mid = (m+n)/2;
int[] temp1 = new int[mid-m+1];
int[] temp2 = new int[o.length-mid+m-1];
System.arraycopy(o,0,temp1,0,mid-m+1);
System.arraycopy(o,mid-m+1,temp2,0,o.length-mid+m-1);
int[] result1 = sort(temp1,m,mid);
int[] result2 = sort(temp2,mid+1,n);
result = Merge(result1,result2);
}
return result;
}
int[] Merge(int[] i,int[] j){
int m=0,n=0,k=0;
int[] result = new int[i.length+j.length];
for(; m
上面的算法用了大量臨時數(shù)組，是一種不好的設(shè)計，其實只需要一個與原數(shù)組大小相同的臨時數(shù)組（必須有，如果只有數(shù)組本身，那么排序時可能覆蓋原有元素），就能完成歸并排序。
void sort(int[] o, int lo, int high){
if(hi <= lo) return;
int mid = lo+(high-lo)/2;
sort(o,lo,mid);
sort(o,mid+1,hi);
merge(o,lo,mid,hi);
}
void merge(int[] o,int lo,int mid,int high){
int i = lo,j = mid+1;
int[] aux = new int[hi-lo+1];
for(int k=lo; k<=hi, k++)
if(i>mid) a[k] = aux[j++];
else if(j>hi) a[k] = aux[i++];
else if(aux[j]
歸并排序需要掃描序列中所有記錄，耗費O(n)時間，整個歸并排序需要logn,因此，總的時間復(fù)雜度為O(nlgn),空間復(fù)雜度為O(n+logn)。
歸并排序可以從幾個方面優(yōu)化：對小規(guī)模子數(shù)組使用插入排序；測試數(shù)組是否已經(jīng)有序，有序就可以跳過merge方法；不將元素復(fù)制到輔助數(shù)組（復(fù)制改為排序）。
3.快速排序
快速排序的思想是分割，確保一個元素左邊的元素都小于這個元素，右邊的元素都大于這個元素，然后對這兩部分分別繼續(xù)進行分割，從而達到排序的效果。
void sort(int[] i,int low,int high){
int temp;
if(low=privotkey)
high --;
swap(i,low,high);
while(low
快速排序的時間復(fù)雜度最優(yōu)和平均都是O(nlgn),最壞情況下為O(n^2),空間復(fù)雜度為O(lgn)，快速排序很脆弱,有一些優(yōu)化手段，比如轉(zhuǎn)插入等;希爾排序效率高，代碼簡單，不需要額外空間，較為常用；
總結(jié)
直接插入排序在序列基本有序時效率較高，對于隨機排序序列，插入排序和選擇排序的運行時間是平方級別的，兩者之比應(yīng)該是一個較小的常數(shù)。
| 排序算法 |
平均情況 |
最好情況 |
最壞情況 |
輔助空間 |
穩(wěn)定性 |
| 冒泡排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
穩(wěn)定 |
| 簡單選擇排序 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
穩(wěn)定 |
| 直接插入排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
穩(wěn)定 |
| 希爾排序 |
O(nlogn)~O(n^2) |
O(n^1.3) |
O(n^2) |
O(1) |
不穩(wěn)定 |
| 堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
不穩(wěn)定 |
| 歸并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
穩(wěn)定 |
| 快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
O(logn)~O(n) |
不穩(wěn)定 |
參考：《大話數(shù)據(jù)結(jié)構(gòu)》、《算法》。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68617.html
