冒泡排序.

基本介绍

冒泡排序(Bubble Sorting)的基本思想:通过对待排序序列从前向后(从下标较小的元素开始,依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的气泡一样逐渐向上冒.
因为排序过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行交换,说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较,(这里说的是优化,之后在基本的学完之后再说)

冒泡排序引用实例

冒泡排序算法的一个过程.(对数组进行排序,原始数组:3,9,-1,10,20)
第一趟排序:

• (1):3,9,-1,10,-2 (如果相邻的两个原始逆序就交换,此时3与9没有逆序)
• (2):3,-1,9,10,-2 (此时比较9,与-1,他们逆序)
• (3):3,-1,9,10,-2 (此时比较9和10,没有逆序,不用交互)
• (4):3,-1,9,-2,10.(第一趟排序我们找到了最大的数)
  第二趟排序
• (1):-1,3,9,-2,10
• (2):-1,3,9,-2,10
• (3):-1,3,-2,9,10(第二个最大的数确定下来)
  第三趟排序
• (1):-1,3,-2,9,20
• (2):-1,-2,3,9,10
  第四趟排序
• (1)::-1,-2,3,9,10
• (2):-2,-1,3,9,10
  小结冒泡排序
  1.一共要进行数组的大小-1次大的循环
  2.每一趟排序的次数在逐渐的减少.
  3,如果我们发现在某趟排序中,没有发生一次交换,可以提交接受冒泡排序.(这样可以对冒泡进行优化)
  例子
  第一趟排序:
• (1):3,9,-1,10,20 (如果相邻的两个原始逆序就交换,此时3与9没有逆序)
• (2):3,-1,9,10,20 (此时比较9,与-1,他们逆序)
• (3):3,-1,9,10,20 (此时比较9和10,没有逆序,不用交互)
• (4):3,-1,9,10,20.(第一趟排序我们找到了最大的数)
  第二趟排序(这一趟排序我们就开始没有进行交换,那么我们可以选择提前退出.)
• (1):-1,3,9,10,20
• (2):-1,3,9,10,20
• (3):-1,3,9,10,20(第二个最大的数确定下来)
  第三趟排序
• (1):-1,3,9,10,20
• (2):-1,3,9,10,20
  第四趟排序
• (1)::-1,3,9,10,20
• (2):-1,3,9,10,20

代码实现

我们演示一下这个过程(用代码)

package sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2};

        //为了容易理解我们把冒泡排序的演变过程进行展示
        /**
         * 第一趟排序就是将最大的那个数,排到最后.
         */
        int temp = 0;//临时变量
        for (int j = 0; j < arr.length - 1; j++) {
            //如果前面的数比后面的数大则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

        System.out.println("第一趟排序后的数组:" + Arrays.toString(arr));


        /**
         * 第二趟排序就是将最大的那个数,排到最后.
         */
        for (int j = 0; j < arr.length - 2; j++) {
            //如果前面的数比后面的数大则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

        System.out.println("第二趟排序后的数组:" + Arrays.toString(arr));




        /**
         * 第三趟排序就是将最大的那个数,排到最后.
         */
        for (int j = 0; j < arr.length - 3; j++) {
            //如果前面的数比后面的数大则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

        System.out.println("第四趟排序后的数组:" + Arrays.toString(arr));

        /**
         * 第三趟排序就是将最大的那个数,排到最后.
         */
        for (int j = 0; j < arr.length - 3; j++) {
            //如果前面的数比后面的数大则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }

        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
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

BubbleSort

package sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2};
       //这里两个循环,可以看出冒泡排序的时间复杂度.O(n^2)
        int temp = 0;//临时变量
        for(int i=0;i<arr.length-1;i++){
        for (int j = 0; j < arr.length - i; j++) {
            //如果前面的数比后面的数大则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
            System.out.println("第("+(i+1)+")趟排序:"+ Arrays.toString(arr));
        }
          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

冒泡排序的优化

package sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {-1,3, 9, 10, 20};
        int temp = 0;//临时变量
        boolean flag=false;//标识变量(表示是否进行过交换)
        for(int i=0;i<arr.length-1;i++){
        for (int j = 0; j < arr.length - i; j++) {
            //如果前面的数比后面的数大则交换
            if (arr[j] > arr[j + 1]) {
                flag=true;//如果flag进来过这个循环,那么就一定进行过交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
            System.out.println("第("+(i+1)+")趟排序:"+ Arrays.toString(arr));
         if(!flag){//在这一趟排序中,一次交换都没有发生过
             break;
         }else {
             flag=false;//将flag重置,不重置的话会没有用的flag
         }
        }
            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
25
26
27
28

封装成一个方法,进行调用

package sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {-1, 3, 9, 10, -2};
        int[] arr1={-1, 3, 9, 10, 20};
         BubbleSorts(arr);
         BubbleSorts(arr1);
    }

//将前面的冒泡排序封装成一个方法
        public static void BubbleSorts ( int[] arr){     
            int temp = 0;//临时变量
            boolean flag = false;//标识变量(表示是否进行过交换)
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - i; j++) {
                    //如果前面的数比后面的数大则交换
                    if (arr[j] > arr[j + 1]) {
                        flag = true;//如果flag进来过这个循环,那么就一定进行过交换
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                System.out.println("第(" + (i + 1) + ")趟排序:" + Arrays.toString(arr));
                if (!flag) {//在这一趟排序中,一次交换都没有发生过
                    break;
                } else {
                    flag = false;//将flag重置,不重置的话会没有用的flag
                }
            }
   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
25
26
27
28
29
30
31
32
33
34
35
36