算法可视化系列——排序算法——冒泡排序

排序算法可视化系列——篇五“冒泡排序”

 

冒泡排序

   基本思想分析：

       冒泡排序是大家都很熟悉的排序算法了，因为用这个排序方法的地方很多，我记得就是计算机基础的老师都讲过，冒泡排序之所以称为这样，是因为它的排序过程很像水泡从水下面到上面的过程。而且在冒泡排序中，我们可以从前往后进行冒泡，也可以从后向前进行冒泡，因为什么呢，因为冒泡排序的思想很简单，就是根据大小交换相邻的两个元素的位置，从后向前（或是从前向后）一直将相邻的两个元素进行交换，直到最大或是最小的元素处于数组的最左边或是最右边（这看你是按哪种大小顺序进行排序）。

 

   算法描述：

//我们假设对于简单的整型数组进行排序，而且按照从小到大的顺序进行排列

for(对于整个数组进行循环i=1~n-1){

  判断数组已经有序，如果有序则不进行下面的冒泡

for(从位置i元素开始进行冒泡的过程j=i~n-1){

比较相邻元素的大小，如果j大于j+1，则交换两个元素

}

}

 

    算法分析：

我们可以从上面的算法描述中可以看出，冒泡排序在最糟糕的情况下，其时间复杂度为O(n^2)，最好的情况是在排序之前数组已经有序，那么其此时的时间复杂度为

O(n)，因此冒泡排序在基本有序的数组中其效率还是可观的。

 

基本的Java语言实现：

 

/**
* 冒泡排序的基本Java语言实现
* 此处是对于基本的整型数组，按照从小到大的顺序进行排序
*/
public class AlgorithmBubleSort{
  public static void bubleSort(int[] array){
    boolean isOrdered = true;
    int length = array.length;
    /**
    * 只需要进行n - 1次循环即可，因为后面n - 1个元素有序
    * 就说明整个数组已经有序
    */
    for(int i = 0; i < length - 1; i++){
      /**
      * 进行判断是否已经有序
      */
      if(isOrdered){
	isOrdered = false;
	/**
	* 进行冒泡的过程
	*/
	for(int j = 0; j < length - i - 1; j++){
		if(array[j] > array[j + 1]){
		  array[j] += array[j+1];
		  array[j+1] = array[j] - array[j+1];
		  array[j] = array[j] - array[j+1]; 
		  isOrdered = true;
		}//end if
	}//end for
      }else{
	break;
      }
     }//end for
    }//end bubleSort
}

 

下面是关于冒泡排序的动态演示：

一、排序中。。。。。。

 二、排序中。。。。。。

 三、排序完成

 上面是对冒泡排序的动态演示，下面附源代码：

 

评论

19 楼 wojiaolongyinong 2013-05-21  

bewithme 写道

楼主你这个播放得太快了，不利于观察学习。还应加上相应的文字说明好一些。

收到。。。。嘿嘿，你可以在源代码里面改一下那个stop（）方法，把时间放慢一点。。。。

18 楼 bewithme 2013-05-21  

楼主你这个播放得太快了，不利于观察学习。还应加上相应的文字说明好一些。

17 楼 wojiaolongyinong 2013-05-21  

jeffyan 写道

闲着蛋疼也写了一个


static int[] intArraySort(int a[]) {
int swap;
int count = 0;
for (int i = 0; i < a.length; i++) {
for (int n = i; n < a.length; n++) {
if (a[i] > a[n]) {
swap = a[i];
a[i] = a[n];
a[n] = swap;
count++;
}

}

}
System.out.println("count=" + count);

return a;

}

这个个人感觉再改写一下吧，像上面说的，这个排序过程会执行（n＋1）n/2次比较，不管数组是否已经有序，所以对于基本有序数组这个排序不是很好。但很简洁，对于小量数据进行排序，很多人一般都这样写冒泡排序。

16 楼 jeffyan 2013-05-21  

闲着蛋疼也写了一个


static int[] intArraySort(int a[]) {
int swap;
int count = 0;
for (int i = 0; i < a.length; i++) {
for (int n = i; n < a.length; n++) {
if (a[i] > a[n]) {
swap = a[i];
a[i] = a[n];
a[n] = swap;
count++;
}

}

}
System.out.println("count=" + count);

return a;

}

15 楼 wojiaolongyinong 2013-05-21  

mnpqxz 写道

博主，请问那个切换单选项之后加载图片的时候你是不是将上次结束时的图片先清空，然后再加载新的图片吗？

对的。。。先清空再画。。。

14 楼 mnpqxz 2013-05-21  

博主，请问那个切换单选项之后加载图片的时候你是不是将上次结束时的图片先清空，然后再加载新的图片吗？

13 楼 wojiaolongyinong 2013-05-20  

整个源代码已更新。。。如有需要请下载AlgorithmSort.zip文件即可

12 楼 mnpqxz 2013-05-20  

所附源代码只是整个程序的一部分，其它在前面的几篇博客中。。。。

11 楼 kenchen0805 2013-05-20  

大哥，请问java 有Data类型吗？
public class AlgorithmBubleSort {
/**
* 用来存储Data数据类型的数组
*/
private Data array = new Data[20];

/**
* 接收面板的开始按钮
*/
private JButton jb = null;

/**
* 重写构造函数
* @param gr
*/

10 楼 wojiaolongyinong 2013-05-20  

mnpqxz 写道

博主，还有一个DrawLine类没有给出

奥奥。。。。是我大意了，晚上我回宿舍了给你发到邮箱，白天还有好多课呢。。。嘿嘿

9 楼 mnpqxz 2013-05-20  

博主，还有一个DrawLine类没有给出

8 楼 mnpqxz 2013-05-20  

哦，知道了，谢谢博主啊，学习博主的精华啊

7 楼 wojiaolongyinong 2013-05-20  

mnpqxz 写道

里面有几个外包没有无法运行啊，求引入包，邮箱[e-mail]

奥奥，那是因为你没有下载前面博客里面的源代码，在前面插入排序那一个里面去下就可以了。。。。嘿嘿嘿

6 楼 mnpqxz 2013-05-20  

里面有几个外包没有无法运行啊，求引入包，邮箱[e-mail]

5 楼 mnpqxz 2013-05-20  

里面有几个外包没有无法运行啊，求引入包

4 楼 jilo88 2013-05-20  

有意思，第一次看到这种展示风格的排序，以往都是直接打印得了。好。。

3 楼 wojiaolongyinong 2013-05-19  

pandaren 写道

图文并茂啊 这个好...

前面几篇博客也是说排序的。。。图文并茂哈。。。嘿嘿

2 楼 pandaren 2013-05-19  

图文并茂啊 这个好...

1 楼 wojiaolongyinong 2013-05-19  

所附源代码只是整个程序的一部分，其它在前面的几篇博客中。。。。