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);

解决方案 »

  1.   


    你误解我的意思了我的意思是说,某一次遍历所有的未确定顺序的元素,如果它们的位置不变,那么整个排序过程就结束当然第一次扫描未确定顺序的元素(此时是所有元素),如果不发生交换,也意味着排序结束了
    如果有辛碰到这种罕见的情况,这时的时间复杂度就是O(n)了,
    但是时间复杂度不依赖个别情况,而是最糟糕的情况,所以说,再怎么优化,冒泡排序的时间复杂度依旧是O(n^2)
      

  2.   

    为了交换两个数,“优化”成了个啥东东,抠成这样:
    a[i]=a[i]+a[j];
    a[j]=a[i]-a[j];
    a[i]=a[i]-a[j];
    可读性差了,加减溢出会不会出毛病?
    刁虫小技改变不了它的特性O(n^2),可用更好的算法(n*log(n))
      

  3.   


    static void bubbleSort(int[] arr){
    for(int i = 0; i < arr.length - 1; ++i){
    boolean flag = false;
    for(int j = 0; j < arr.length - i - 1; ++j){
    if(arr[j] > arr[j+1]){
    flag = true;
    int tmp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = tmp;
    }
    }
    if(!flag)
    return;
    }
    }