算法笔记（第一部分）-- 排序之白话冒泡排序

冒泡排序，是所有排序中最简单的一种，也是效率最低的一种，时间复杂度О(n²)，空间复杂度O(n)。冒泡排序没有改变原始元素的相对位置，因此是稳定的排序。

冒泡排序动画：



冒泡排序Java代码(递增)：

public void bubble_sort(int[] data){
            for(int i=0; i<data.length; i++){
                  for(int j=0; j<data.length-1-i; j++){
                        if(data[j]>data[j+1]){
                              swap(data,j,j+1);
                        }
                  }
            }
      }

由代码我们可以看出冒泡排序的工作原理是第一个循环的作用是遍历整个数据集，第二个循环从第一个数开始顺次比较相邻两数大小，若后数比前数大则交换。需要注意的是j的条件是小于data.length-i，因为结束一次外层循环后，最大的数已经被交换到了数组的最后，所以无需再次进行比较。P.S. 冒泡排序有优化的空间，外层循环是不是只要做一半就够了呢？

评论

12 楼 hacer9791 2009-02-21  

以下是对冒泡排序的一点优化:减少了外层循环的次数


public class MaoPao{
public void showData(int[] a){
int[] shuzu=a;
int aa=1;
int b=0;
int temp=0;
while(aa>0){
  b=0;
for(int i=0;i<shuzu.length-1;i++){
   if(shuzu[i]<shuzu[i+1]){
  temp=shuzu[i];
  shuzu[i]=shuzu[i+1];
  shuzu[i+1]=temp;
  b=1;
}
}
aa=b;
}
for(int k=0;k<shuzu.length;k++){
System.out.println(shuzu[k]);
}
}

public static void main(String[] args){
int[] arr={1,2,3,4,5,6};
new MaoPao().showData(arr);
}
}

11 楼 lenky0401 2008-09-07  

冒泡排序有优化的空间，外层循环是不是只要做一半就够了呢？

确定这样的？

你这个一半是啥意思？

是不是如果data.length==5的话 外层循环只要到(5/2+1)=3就可以保证已经排序好了？【这种情况不对啊】

还是当一趟内部循环没有任何交换的话 就可以直接break了【这种情况 任何一个讲冒泡算法的都会带到吧】

10 楼 zoninge 2008-09-03  

呵呵，有意思。。。

引用

冒泡排序有优化的空间，外层循环是不是只要做一半就够了呢？

恩，之前也不知道，看C++的书，上面就说道了这个东西

9 楼 hlily2005 2008-09-02  

难怪之前的没看懂了 ，因为没看这个，呵呵~~~

8 楼 yeshucheng 2008-09-02  

图片貌似不对啊

7 楼 percent 2008-08-28  

图片不是演示冒泡的
    冒泡说,他自己的思想是每次只成功筛选一条未处理记录集合中的一个记录,直至完成所有记录

6 楼 ham 2008-08-28  

congjl2002 写道

这个图片说明了冒泡排序吗？

这个图模拟了冒泡的过程，将所有的点由高到低，比较，交换，然后将最高的移到最右边，依序排列。就出现了这种动画效果。

照语义来说，冒泡，应该是竖向的移动，这个图却让这些点进行横向的移动，让人有些摸不着头脑。

SCYForce 写道

冒泡排序有优化的空间，外层循环是不是只要做一半就够了呢？

要是只做一半，就算能够排序能够顺利进行，但那还能称之为冒泡吗？

5 楼 congjl2002 2008-08-28  

这个图片说明了冒泡排序吗？
另外你最后一句话没明白什么意思，赐教一下

4 楼 sunfengcheng 2008-08-28  

呵呵！这个。。。。大学就经常写这种东东！现在更少了...

3 楼 SCYForce 2008-08-28  

谢谢您的提醒，您看的还真仔细，动画是Wiki上摘的，我的实现是从左到右。

2 楼 mudong 2008-08-28  

你这动画完全反啦

1 楼 sunnylocus 2008-08-28  

呵呵，第一次弄这个冒泡脑子转不过来，整整想了6个小时才搞清楚，复习了。