首页 > Java开发 > 冒泡排序(Bubble Sort)原理及Java实现

冒泡排序(Bubble Sort)原理及Java实现

冒泡排序 (Bubble Sort) 算法是一种基于交换的排序算法,其思想是,依次比较相邻元素的大小,如果反序,则进行交换,然后再进行下一次排序——如果数据集合的长度为n ,则下一次对前n-1的数据进行冒泡排序。

比如:

第一趟排序 :R1 和R2 比较, R2 和 R3 比较  .... Rn-1 和Rn 比较。得到最大值或最小值Rn

第二趟排序: R1 和R2 比较, R2 和 R3 比较  .... Rn-2 和Rn-1 比较。得到最大值或最小值前n-1个数中的最值 Rn-1

..........................

直到只剩下最后一个数 R1 为有序。

 

但是,实现的时候一般换另一种方法,用R1 和后面的 n-1 个数依次比较 得到一个最值R1 ——这是第一趟冒泡排序;

第二趟冒泡排序: 用R2 和后面的n-2个数比较 ,得到一个最值 R2 ....

依次执行,直到最后剩下Rn为有序。

如对R = {37, 40, 38, 42, 461, 5, 7, 9, 12}进行冒泡排序;

 

初始序列 37 40 38 42 461 5 7 9 12
第一趟排序 5 40 38 42 461 37 7 9 12
第二趟排序 5 7 40 42 461 38 37 9 12
第三趟排序 5 7 9 42 461 40 38 37 12
第四趟排序 5 7 9 12 461 42 40 38 37
第五趟排序 5 7 9 12 37 461 42 40 38
第六趟排序 5 7 9 12 37 38 461 42 40
第七趟排序 5 7 9 12 37 38 40 461 42
第八趟排序 5 7 9 12 37 38 40 42 461

 

第九趟排序的时候已经有序。

下面分析一下每一趟排序的结果是如何来的,假设为顺序存储:

 

集合R 37 40 38 42 461 5 7 9 12
元素位置 1 2 3 4 5 6 7 8 9

 

 

在第一次排序过程中,用R1 = 37 , 和后面的 Ri ( 1<i <= 9)比较 , 发现 R1 > R6 , 交换位置,得到新的排列:

 

集合R 5 40 38 42 461 37 7 9 12
元素位置 1 2 3 4 5 6 7 8 9

发现没有比R1=5 , 小的元素,第一趟排序结束。

 

 

第二趟排序R2=40,发现R3 比R2交换得到新的排列

 

集合R 5 38 40 42 461 37 7 9 12
元素位置 1 2 3 4 5 6 7 8 9

继续比较,发现R2 比R6大 交换位置得到新的排列

 

 

集合R 5 37 40 42 461 38 7 9 12
元素位置 1 2 3 4 5 6 7 8 9

继续比较,发现R2 比R7大,交换得到新的排列

 

 

集合R 5 7 40 42 461 38 37 9 12
元素位置 1 2 3 4 5 6 7 8 9

继续比较,没有比R2 = 7 更小的元素, 第二趟排序结束。有兴趣的童鞋可以自己推到一偏。

 

以此类推,知道Ri = n-1 = 8;

以下是上述思想的Java实现版:

 

[java]
  1. public static void bubbleSort(int[] array) {
  2.         if (null == array || array.length == 0)
  3.             return;
  4.         int temp;
  5.         for (int i = 0; i < array.length - 1; i++) {
  6.             for (int j = i + 1; j < array.length; j++) {
  7.                 if (array[j] < array[i]) {
  8.                     temp = array[j];
  9.                     array[j] = array[i];
  10.                     array[i] = temp;
  11.                 }
  12.             }
  13.         }
  14.     }

 


本文固定链接: http://www.devba.com/index.php/archives/4338.html | 开发吧

报歉!评论已关闭.