接上文
第三種：插入排序
public static int[] insertionSort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
int temp = a[i];
int j;
for (j = i - 1; j >= 0 && temp < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
return a;
}
}
算法分析： 插入排序的思想是這樣的，第一層for循環(huán)表示要循環(huán)n次，且每次循環(huán)要操作的主體是a[i]，第二層循環(huán)是對a[i]的具體操作，是從原數(shù)祖第i個位置起，向前比較，若a[i]比前面的數(shù)小，前面的數(shù)后移占去a[i]的位置，同時也為a[i]空出了插入地點(diǎn)，然后向前繼續(xù)比較，直到a[i]比前面的數(shù)來的大，插入。下一次循環(huán)開始，這樣就完成一個完整的升序插入排序。
很明顯，這種排序也是不穩(wěn)定的，
最好的情況是：順序已經(jīng)排好那么我們只要進(jìn)行n-1次比較即可。
最壞的情況是：順序恰好是逆序，慘了，我們要比較1+2+...+n-1次
平均的復(fù)雜度算起來還是比較困難的，也是很有參考價值的：
1。首先，我們來看 對于第i個元素 a[i] 的操作
從等概率角度思考：a[i]只比較 1 次的概率為 1/i;
a[i]只比較 2 次的概率為 1/i;
a[i]只比較 3 次的概率為 1/i;
。
。
。
a[i]只比較 i-1 次的概率為 1/i;
a[i]只比較 i 次的概率為 1/i;
于是又編號為i的元素平均比較次數(shù)為：(1/i)*(1+2+3+...+i)=(i+1)/2
2。然后我們來看
平均比較次數(shù)為 T=(2+3+4+...+n)/2
所以插入排序的平均時間復(fù)雜度也是O(n^2).
第四種：Rank排序
public static int[] rankSort(int[] a){
int n=a.length;
int[] r1=new int[n];
int[] r2=new int[n];
for (int i = 0; i
for(int j=i+1;j
if(a[i]
r1[j]++;
else
r1[i]++;
}
}
for(int i=0;i
r2[r1[i]]=a[i];
}
return r2;
}
算法分析：Rank排序是基于這樣的思想，建立一個和待排序數(shù)組相同大小的數(shù)組，初識化為全0，然后掃描原數(shù)組將每個數(shù)的大小排名，然后更具排名安排各自元素的位次，思路非常簡單
復(fù)雜度分析：這個算法是穩(wěn)定的一共要比較的次數(shù)為n*(n-1)/2
時間復(fù)雜度是O(n^2);