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