1.冒泡算法
抱歉。上个版本的文章确实有很大问题，大家的回复颠覆了我对冒泡排序的想法，在此谢谢大家。有个热心观众写的比我好些，他写了三种很好的优化方法。传送门
- 所谓冒泡算法(Bubble)就是每次找出最大（小）的值，将其放到最后，然后再对剩余的数进行重复操作。
第一个for循环：排除最后一个或几个已经排序好的数。a.length-1是因为数组从0开始。
第二个for循环：找出剩余的数里的最大（小），放在最后。减去i，是为了排除已经排序好的元素。
代码如下:
for(inti=0;i<a.length-1;i++){
for(intj=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
时间复杂度为O(n^2)，太高了。
2.一层优化
- 但是还是不够，因为有时候我们冒泡排序时，可能已经排好了，任然还在比较。这时候就需要一个flag进行判定。是否已经排好了，如果排好了就不进比较了。
int a[n];
int t;//交换容器
bool flag=true;//判定
for(inti=0;i<a.length-1;i++){
flag=false;
for(intj=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=true;
}
}
}
if(!flag){
break;
}
}
这样子就会效率很多。
3.最后结论
冒泡算法简单但并不好，主要是时间复杂度太高。
疑问：
int a[n];
int t;//交换容器
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (a[i] > a[j]) {
t = a[j];
a[j] = a[i];
a[i] = t;
}
}
}
- 这种算法是什么排序呢？有没有热心观众解答一下。
