工作小驿

Ninja!

BlogJava 首页 新随笔 联系 聚合 管理
  103 Posts :: 0 Stories :: 36 Comments :: 0 Trackbacks
第一种:冒泡排序

public static int[] bubbleSort(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < (a.length - i) - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
return a;
}

复杂度分析:冒泡排序是不稳定的排序算法,一共要比较((n-1)+(n-2)+...+3+2+1)=n*(n-1)/2次,所以时间复杂度是O(n^2)。




第二种:选择排序

public static int[] selecitonSort(int[] a) {
for (int i = 0; i < a.length; i++) {
int max = a[0];
int count = 0;
int k = a.length - i - 1;
for (int j = 0; j < a.length - i; j++) {
if (max < a[j]) {
max = a[j];
count = j;
}
}
a[count] = a[k];
a[k] = max;
}
return a;
}


复杂度分析:选择排序是不稳定算法,最好的情况是最好情况是已经排好顺序,只要比较
n*(n-1)/2次即可,最坏情况是逆序排好的,那么还要移动 O(n)次,由于是低阶故而不考虑
不难得出选择排序的时间复杂度是 O(n^2)



第三种:插入排序
待续。。。
posted on 2007-09-20 15:57 王君 阅读(749) 评论(0)  编辑  收藏 所属分类: J2SE

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


网站导航: