排序算法匯總
各類排序算法時(shí)間空間復(fù)雜度如下表所示：
1：直接選擇排序：
排序思想：
選取當(dāng)前最小（最大）的數(shù)據(jù)放置在當(dāng)前狀態(tài)下的最前面的位置窜觉，一直輪循谷炸，直到所有序列都有序?yàn)橹梗?/p>
代碼實(shí)現(xiàn)：
public void sort(int a[]){
int length = a.length;
for(int i =0;i<length;i++){
int min = i;
for(int j =i+1;j<length;j++){
if(a[min]>a[j]){
min = j;
}
}
if(min !=i){
int temp = a[i];
a[i]=a[min];
a[min]=temp;
}
}
}
}
示例：
[9,5,2,4,3]
i = 0;
根據(jù)內(nèi)部循環(huán)，選取當(dāng)前狀態(tài)(i = 0)下最小的的值為2禀挫，此時(shí)下標(biāo)j為3旬陡，將2放置在當(dāng)前狀態(tài)下的最前面a[i]處
該循環(huán)后序列為：
[2,5,9,4,3]
再進(jìn)一步循環(huán)，直到i = 5,循環(huán)終止语婴，序列有序
時(shí)間復(fù)雜度分析：
改排序需要經(jīng)過兩重循環(huán)描孟，假定有n個(gè)元素，則其需要經(jīng)歷n*n次循環(huán)才能結(jié)束砰左，所以其時(shí)間復(fù)雜度為O(n^2)
空間復(fù)雜度分析：
該排序沒有占用額外的存儲(chǔ)空間（臨時(shí)變量常數(shù)級(jí)別）匿醒，所以該排序的空間負(fù)載度為O(1)
2：插入排序
排序思想：
將整個(gè)待排序的序列分成兩個(gè)部分，前半部分是有序的序列缠导，后半部分為無需部分廉羔，然后將后半部分的元素依次添加到前半部分的有序序列中，前半部分為有序序列僻造，因此只需要將后半部分取出來的數(shù)據(jù)插入到合適的位置即可憋他，直到后半部分為空；
代碼實(shí)現(xiàn)：
public void sort(int target[]){
int length = target.length;
for(int i=1;i<length;i++){
for(int j = i;j>0;j--){
if(target[j]>target[j-1]) {
int temp = target[j];
target[j]=target[j-1];
target[j-1]=temp;
}else{
break;
}
}
}
}
示例：
[1,4,2,5,3]
將數(shù)據(jù)分成兩個(gè)序列[1] 和 [4,2,5,3]
將4 加入到前半部分中,此時(shí)序列為[1,4] 和 [2,5,3]
將2 加入到前半部分中,此時(shí)序列為[1,2髓削，4] 和 [5,3]
直到最后序列有序
時(shí)間復(fù)雜度分析：
該算法基礎(chǔ)步驟執(zhí)行的次數(shù)為：(1+n)*n/2,其數(shù)量級(jí)在n2,因此其時(shí)間復(fù)雜度為O(n2)
最好情況為整個(gè)序列有序竹挡，每次只需移動(dòng)后半部分的一個(gè)元素到前半部分，移動(dòng)次數(shù)為n立膛，故為O(n)
空間復(fù)雜度分析：
該排序沒有占用額外的存儲(chǔ)空間（臨時(shí)變量常數(shù)級(jí)別）揪罕，所以該排序的空間負(fù)載度為O(1)
3:希爾排序
排序思想：
希爾排序(Shell)是插入排序的升級(jí)版，假設(shè)一個(gè)序列是倒敘的宝泵，現(xiàn)在要求對(duì)這個(gè)數(shù)列正序排列好啰，在數(shù)組基數(shù)較大的情況下，將最后的元素移動(dòng)到最前面需要經(jīng)歷n-1次的比較鲁猩，比較次數(shù)較多，元素移動(dòng)較多罢坝，排序效率自然低下廓握，希爾排序，是在這樣的情況下產(chǎn)生的嘁酿，其實(shí)想思想是先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序隙券，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠心炙尽）時(shí)娱仔，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況）游桩，效率是很高的牲迫，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高耐朴，這樣元素移動(dòng)跨度較大，效率也自然的得到提升盹憎；
希爾排序的步長(zhǎng)可以自定義筛峭，下面，我選用步長(zhǎng)為3
代碼實(shí)現(xiàn)：
public void sort(int target[]){
int length = target.length;
int h = 1;
while(h<length/3) h = 3*h+1;（步長(zhǎng)）
while(h >=1){
for(int i = h;i<length;i++){
for(int j = i;j>=h;j-=h){
if(target[j]<target[j-h]){
int temp = target[j];
target[j]=target[j-h];
target[j-h] = temp;
}
}
}
h=h/3;
}
}
時(shí)間復(fù)雜度分析：
希爾排序的時(shí)間復(fù)雜度與選擇的步長(zhǎng)度有關(guān)
空間復(fù)雜度：
該排序沒有占用額外的存儲(chǔ)空間（臨時(shí)變量常數(shù)級(jí)別）陪每，所以該排序的空間負(fù)載度為O(1)
