排序算法——冒泡排序

基本介绍

冒泡排序（Bubble Sorting）的基本思想是：

通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序(与自己制定的顺序相反)则交换，使值较大的元素逐渐从前移向后部

优化：

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较,来达到算法优化。

冒泡过程图解：

image-20230204162842489

小结:

  1. 一共进行 数组的大小-1 次 大的循环

  2. 每一趟排序的次数在逐渐的减少

  3. 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化

代码实现

无优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 无优化的冒泡排序
 * @param arr
 */
private static void Sort ( int[] arr ) {
    System.out.println ("排序之前"+Arrays.toString ( arr ) );
    int temp = 0;
    for ( int i=0;i<arr.length-1;i++ ){
        for ( int j = 0 ; j < arr.length-1 - i ; j++ ) {
            if ( arr[j]>arr[j+1] ){
                temp = arr[ j ];
                arr[j]=arr[j+1];
                arr[ j + 1 ] = temp;
            }
        }
        System.out.printf ("第%d趟排序，结果是",i+1 );
        System.out.println ( Arrays.toString( arr ) );
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 有优化的冒泡排序
 * @param arr
 */
private static void SortPro ( int[] arr ) {
    System.out.println ("排序之前"+Arrays.toString ( arr ) );
    int temp = 0;
    for ( int i=0;i<arr.length-1;i++ ){
        boolean flag = true;
        for ( int j = 0 ; j < arr.length-1 - i ; j++ ) {
            if ( arr[j]>arr[j+1] ){
                temp = arr[ j ];
                arr[j]=arr[j+1];
                arr[ j + 1 ] = temp;
                flag = false;
            }
        }
        System.out.printf ("第%d趟排序，结果是",i+1 );
        System.out.println ( Arrays.toString( arr ) );
        if ( flag ){
            return;
        }
    }
}

优化性比较

创建80000个随机数据的数组 arr,arr1 ,分别进行排序比较优化后的代码提示多少（具体时间跟硬件有关，大致优化时间可参照）

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class BubbleSorting {
    public static void main ( String[] args ) {
       /* int arr[] = {3, 9, -1, 10, -2 };

        //将冒泡排序的演变过程展示一遍
        //每趟排序，将最大的依次从最后往前
        SortPro ( arr );
        System.out.println ("排序完结果是"+Arrays.toString( arr ) );
*/

        //测试冒泡的速度O(n^2),给80000个数据测试
        //创建80000个数据的随机数组
        int arr[] = new int[ 80000 ];
        int arr1[] = new int[ 80000 ];
        randomArr ( arr );
        randomArr ( arr1 );

        System.out.println ("无优化所用时间" );
        String date1String = Date ( );
        System.out.println ("排序前时间是："+date1String );
        Sort ( arr );
        String date2String = Date ( );
        System.out.println ("排序后时间是："+date2String );

        System.out.println ("有优化所用时间" );
        String date3String = Date ( );
        System.out.println ("排序前时间是："+date3String );
        SortPro ( arr1 );
        String date4String = Date ( );
        System.out.println ("排序后时间是："+date4String );



    }

    /**
     * 随机数组
     * @param arr
     */
    private static void randomArr ( int[] arr ) {
        for(int i = 0; i < arr.length;i++){
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format(date1 );
    }

    /**
     * 无优化的冒泡排序
     * @param arr
     */
    private static void Sort ( int[] arr ) {
//        System.out.println ("排序之前"+Arrays.toString ( arr ) );
        int temp = 0;
        for ( int i=0;i<arr.length-1;i++ ){
            for ( int j = 0 ; j < arr.length-1 - i ; j++ ) {
                if ( arr[j]>arr[j+1] ){
                    temp = arr[ j ];
                    arr[j]=arr[j+1];
                    arr[ j + 1 ] = temp;
                }
            }
//            System.out.printf ("第%d趟排序，结果是",i+1 );
//            System.out.println ( Arrays.toString( arr ) );
        }
    }

    /**
     * 有优化的冒泡排序
     * @param arr
     */
    private static void SortPro ( int[] arr ) {
//        System.out.println ("排序之前"+Arrays.toString ( arr ) );
        int temp = 0;
        for ( int i=0;i<arr.length-1;i++ ){
            boolean flag = true;
            for ( int j = 0 ; j < arr.length-1 - i ; j++ ) {
                if ( arr[j]>arr[j+1] ){
                    temp = arr[ j ];
                    arr[j]=arr[j+1];
                    arr[ j + 1 ] = temp;
                    flag = false;
                }
            }
//            System.out.printf ("第%d趟排序，结果是",i+1 );
//            System.out.println ( Arrays.toString( arr ) );
            if ( flag ){
                return;
            }
        }
    }
}

结果

image-20230204163845864

在多次实验下，结果依旧不变，大致可以确定，该优化能提升1/10的性能，但依于冒泡排序虽稳定，但时间复杂度较高，数据大时不建议用！！