Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1559673
  • 博文数量: 3500
  • 博客积分: 6000
  • 博客等级: 准将
  • 技术积分: 43870
  • 用 户 组: 普通用户
  • 注册时间: 2008-05-03 20:31
文章分类

全部博文(3500)

文章存档

2008年(3500)

我的朋友

分类:

2008-05-04 19:01:11

一起学习
接上文 第三种:插入排序 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 下载本文示例代码


JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2JAVA 实现各种排序算法和复杂度分析2
阅读(212) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~