冒泡排序Java代码实现

冒泡排序的思想:把相邻的两个元素进行比较，当元素大于其右侧的元素时交换它们的位置，当一个元素小于或者等于其右侧的元素时，位置不变。

举例说明

例如一组数列为

int[] arrays = new int[]{3,1,4,2,6,8,7,9,5};

为了直观，用下面的方式来表示数组的排列

3 1 4 2 6 8 7 9 5
第一轮排序后的结果如下

1 3 2 4 6 7 8 5 9
第二轮结果如下

1 2 3 4 6 7 5 8 9
第三轮

1 2 3 4 6 5 7 8 9
第四轮

1 2 3 4 5 6 7 8 9
第五轮

…

直到arrays.length轮结束。

用Java代码如何实现呢？如下：

package com.wbl.bubblesort;

import java.util.Arrays;

/**

• 冒泡排序训练，参考《漫画算法》
• 冒泡排序的思想，把相邻的两个元素两两比较，当一个元素大于右侧相邻元素交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

/
public class BubbleSort {
/*
* 最基本算法，外层循环控制遍历的轮数，内层循环控制元素之间比对的次数
*/
public static void sort1(int[] arrays){
System.out.println(“sort1:start:”+ System.currentTimeMillis());
for (int i=0;i < arrays.length -1;i++){

        for (int j = 0; j < arrays.length - i-1; j++) {
            int temp = 0;
            if (arrays[j] > arrays[j+1]){
                temp = arrays[j];
                arrays[j] = arrays[j+1];
                arrays[j+1] = temp;
            }
        }
        System.out.println("第" +i +"轮:"+Arrays.toString(arrays));

    }
    System.out.println("sort1:end:"+ System.currentTimeMillis());
}


public static void main(String[] args) {
    int[] arrays = new int[]{3,1,4,2,6,8,7,9,5};
    sort1(arrays);
    System.out.println(Arrays.toString(arrays));
 

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

}
如果到这里你就以为结束了的话，那你就缺乏思考了，有没有发现在上述的遍历过程中，其实到第四轮的时候，数列就已经变成有序状态了，接下来的遍历都是做无用功。所以优化的重点还是在如何减少遍历的次数，这是个关键点。

优化后的代码如下:

package com.wbl.bubblesort;

import java.util.Arrays;

/**

• 冒泡排序训练，参考《漫画算法》
• 冒泡排序的思想，把相邻的两个元素两两比较，当一个元素大于右侧相邻元素交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

/
public class BubbleSort {
/*
* 最基本算法，外层循环控制遍历的轮数，内层循环控制元素之间比对的次数
*/
public static void sort1(int[] arrays){
System.out.println(“sort1:start:”+ System.currentTimeMillis());
for (int i=0;i < arrays.length -1;i++){

        for (int j = 0; j < arrays.length - i-1; j++) {
            int temp = 0;
            if (arrays[j] > arrays[j+1]){
                temp = arrays[j];
                arrays[j] = arrays[j+1];
                arrays[j+1] = temp;
            }
        }
        System.out.println("第" +i +"轮:"+Arrays.toString(arrays));

    }
    System.out.println("sort1:end:"+ System.currentTimeMillis());
}

/**
 * 冒泡排序的优化方法，主要优化点当进行过n轮之后，有可能整个数列已经是有序排列的，这个时间就不需要再继续进行第n+1轮排序了。
 * 例如，原始数列为{5,8,6,3,9,2,1,7}
 * 经过第一轮比对后变成:{5,6,3,8,2,1,7,9}
 * 经过第二轮比对后变成:{5,6,3,2,1,7,8,9}
 * 经过第三轮比对后变成:{5,3,2,1,6,7,8,9}
 * 经过第四轮比对后变成:{3,2,1,5,6,7,8,9}
 * 经过第五轮比对后变成:{2,1,3,5,6,7,8,9}
 * 经过第六轮比对后变成:{1,2,3,5,6,7,8,9}
 * 由此可以看出，经过六轮之后，数列已经排序完成，所以此时就没有必要再进行第7轮的比对。
 * 经过n轮之后，数列已经变成了{1,2,3,4,5,6,7,8,9}
 * @param arrays 数组
 */
public static void sort2(int[] arrays){
    System.out.println("sort2:start:"+ System.currentTimeMillis());
    for (int i = 0; i < arrays.length; i++) {
        //定义一个变量，用来控制有序标记，每一轮的初始值都是true
        boolean isSorted = true;
        for (int j = 0; j < arrays.length - i - 1; j++) {
            int temp;
            if ( arrays[j] > arrays[j+1]){
                temp = arrays[j];
                arrays[j] = arrays[j+1];
                arrays[j+1] = temp;
                //当有数据交换时说明还不是有序数列，标记为false
                isSorted = false;
            }
        }
        if (isSorted )
            break;
    }
    System.out.println("sort2:end:"+ System.currentTimeMillis());
}


public static void main(String[] args) {
   
    int[] arrays = new int[]{3,1,4,2,6,8,7,9,5};
    sort2(arrays);
    System.out.println(Arrays.toString(arrays));


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

}

​