《java实现各种排序算法和复杂度分》由会员分享，可在线阅读，更多相关《java实现各种排序算法和复杂度分（3页珍藏版）》请在金锄头文库上搜索。
1、JAVA 实现各种排序算法和复杂度分实现各种排序算法和复杂度分第一种：冒泡排序public static int bubbleSort(int a) for (int i = 0; i aj + 1) int temp = aj;aj = aj + 1;aj + 1 = temp;return a;复杂度分析：冒泡排序是不稳定的排序算法，一共要比较(n-1)+(n-2)+.+3+2+1)=n*(n-1)/2 次，所以时间复杂度是 O(n2)。第二种：选择排序public static int selecitonSort(int a) for (int i = 0; i = 0 j-) aj +
2、 1 = aj;aj + 1 = temp;return a;算法分析：插入排序的思想是这样的，第一层 for 循环表示要循环 n 次，且每次循环要操作的主体是 ai，第二层循环是对 ai的具体操作，是从原数祖第 i 个位置起，向前比较，若 ai比前面的数小，前面的数后移占去 ai的位置，同时也为 ai空出了插入地点，然后向前继续比较，直到 ai比前面的数来的大，插入。下一次循环开始，这样就完成一个完整的升序插入排序。很明显，这种排序也是不稳定的，最好的情况是：顺序已经排好那么我们只要进行 n-1 次比较即可。最坏的情况是：顺序恰好是逆序，惨了，我们要比较 1+2+.+n-1 次平均的复杂度算
3、起来还是比较困难的，也是很有参考价值的：1。首先，我们来看 对于第 i 个元素 ai 的操作从等概率角度思考：ai只比较 1 次的概率为 1/i;ai只比较 2 次的概率为 1/i;ai只比较 3 次的概率为 1/i;。ai只比较 i-1 次的概率为 1/i;ai只比较 i 次的概率为 1/i;于是又编号为 i 的元素平均比较次数为：(1/i)*(1+2+3+.+i)=(i+1)/22。然后我们来看平均比较次数为 T=(2+3+4+.+n)/2所以插入排序的平均时间复杂度也是 O(n2).第四种：Rank 排序public static int rankSort(int a)int n=a.length;int r1=new intn;int r2=new intn;for (int i = 0; ifor(int j=i+1;jif(air1j+;elser1i+;for(int i=0;ir2r1i=ai;return r2;算法分析：Rank 排序是基于这样的思想，建立一个和待排序数组相同大小的数组，初识化为全 0，然后扫描原数组将每个数的大小排名，然后更具排名安排各自元素的位次，思路非常简单复杂度分析：这个算法是稳定的一共要比较的次数为 n*(n-1)/2时间复杂度是 O(n2);
