接上文
第三种：插入排序
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循环表示要循环n次，且每次循环要操作的主体是a[i]，第二层循环是对a[i]的具体操作，是从原数祖第i个位置起，向前比较，若a[i]比前面的数小，前面的数后移占去a[i]的位置，同时也为a[i]空出了插入地点，然后向前继续比较，直到a[i]比前面的数来的大，插入。下一次循环开始，这样就完成一个完整的升序插入排序。
很明显，这种排序也是不稳定的，
最好的情况是：顺序已经排好那么我们只要进行n-1次比较即可。
最坏的情况是：顺序恰好是逆序，惨了，我们要比较1+2+...+n-1次
平均的复杂度算起来还是比较困难的，也是很有参考价值的：
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的元素平均比较次数为：(1/i)*(1+2+3+...+i)=(i+1)/2
2。然后我们来看
平均比较次数为 T=(2+3+4+...+n)/2
所以插入排序的平均时间复杂度也是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排序是基于这样的思想，建立一个和待排序数组相同大小的数组，初识化为全0，然后扫描原数组将每个数的大小排名，然后更具排名安排各自元素的位次，思路非常简单
复杂度分析：这个算法是稳定的一共要比较的次数为n*(n-1)/2
时间复杂度是O(n^2);