工作小驿

Ninja!

BlogJava 首页 新随笔 联系 聚合 管理
  103 Posts :: 0 Stories :: 36 Comments :: 0 Trackbacks
接上文

第三种:插入排序

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);
posted on 2007-09-20 15:58 王君 阅读(784) 评论(2)  编辑  收藏 所属分类: J2SE

Feedback

# re: JAVA 实现各种排序算法和复杂度分析2 2007-09-22 00:18 千里冰封
分析得很有道理  回复  更多评论
  

# re: JAVA 实现各种排序算法和复杂度分析2 2007-09-23 00:19 黑蝙蝠
for (int i = 0; i for(int j=i+1;j
if(a[i]
r1[j]++;
else
r1[i]++;
}

Rank排序这代码写错了?
快速排序讲不?  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: