当前位置：首页 → 问答吧 → 冒泡排序优化

冒泡排序优化

时间：2011-10-24

来源：互联网

int[] a={2,6,5,7,8,9};
int size=0;

for(int i=0;i<a.length;i++){
Boolean flag=false;
for(int j=a.length-1;j>i;j--){
if(j>0&&a[j]<a[j-1]){
flag=true;
}
size++;
if(a[i]>a[j]){
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
if(!flag){
break;
}

}

for(int i=0;i<a.length;i++){
System.out.print(a[i]);
}

System.out.println(size);

作者: smallfish987 发布时间: 2011-10-24

冒泡排序，通过参数或者判断，减少循环次数。谁知道还有更优化的吗？当然，快速排序等其它算法除外

作者: smallfish987 发布时间: 2011-10-24

扫描一遍不再次冒泡，就说明排序结束
再怎么优化，复杂度依旧是O(n^2),可以说优化无济于事

作者: k3108001263 发布时间: 2011-10-24

冒泡是很经典的算法了许多大牛已经优化完了你学的是优化完了的了

作者: mengxiangyue 发布时间: 2011-10-24

引用 2 楼 k3108001263 的回复:
扫描一遍不再次冒泡，就说明排序结束
再怎么优化，复杂度依旧是O(n^2),可以说优化无济于事

扫描一遍不再次冒泡，并不意味着冒泡就结束了哦。

譬如2,6,5,7,3,4，第一次扫描一遍，不再冒泡，但排序并没有结束

作者: smallfish987 发布时间: 2011-10-24

引用 4 楼 smallfish987 的回复:

引用 2 楼 k3108001263 的回复:
扫描一遍不再次冒泡，就说明排序结束
再怎么优化，复杂度依旧是O(n^2),可以说优化无济于事

扫描一遍不再次冒泡，并不意味着冒泡就结束了哦。

譬如2,6,5,7,3,4，第一次扫描一遍，不再冒泡，但排序并没有结束

你误解我的意思了

我的意思是说，某一次遍历所有的未确定顺序的元素，如果它们的位置不变，那么整个排序过程就结束

当然第一次扫描未确定顺序的元素（此时是所有元素），如果不发生交换，也意味着排序结束了
如果有辛碰到这种罕见的情况，这时的时间复杂度就是O(n)了，
但是时间复杂度不依赖个别情况，而是最糟糕的情况，所以说，再怎么优化，冒泡排序的时间复杂度依旧是O(n^2)

作者: k3108001263 发布时间: 2011-10-25

冒泡排序优化

热门阅读

热门下载