冒泡排序（学习笔记）

冒泡排序（基于交换的排序，每一轮确定一个数的位置）

哨兵举例：
待排序序列：6 3 1 2 5
第一轮排列：
3 6 1 2 5
3 1 6 2 5
3 1 2 6 5
3 1 2 5 6（最大的数移动到了正确的位置）
第二轮排列：
3 1 2 5 6
1 3 2 5 6
1 2 3 5 6
此时已经有序，如果不加优化，排序算法还会继续，加入“哨兵”即可避免多余算法时间。

import java.util.Random;

public class BubbleSort {
    //定义常量——数组长度
    public static final int MAXLENGTH = 10;

    public static void main(String[] args) {

        //创建随机数组，数组长度需用户自定义
        int[] bubbleSortArr = createArray(MAXLENGTH);
        //打印创建好的数组(未排好序)
        printArray(bubbleSortArr);
        //排序
        bubbleSort(bubbleSortArr,bubbleSortArr.length);
        //打印排序后的数组
        printArray(bubbleSortArr);


    }
    //创建数组方法（数组中的元素随机生成）
    public static int[] createArray(int length){
        int[] arr =new int[length];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(20);//[0,20)
        }
        return arr;
    }
    //打印数组方法
    public static void printArray(int[] arr){
        for (int i=0;i<arr.length;i++) {
           if (i==0){
               if (arr.length==1){
                   System.out.println("["+arr[0]+"]");
               }else{
                   System.out.print("["+arr[i]+",");
               }
           }else if(i==arr.length-1){
               System.out.println(arr[i]+"]");
           }else {
               System.out.print(arr[i]+",");
           }

        }
        System.out.println("--------------------------------------------------------");
    }
    //冒泡排序方法
    public static void bubbleSort(int[] arr,int length){
        //冒泡排序优化————加入“哨兵”
        //flag代表本轮是否有数字进行交换，flag为1代表有，0代表本轮未进行交换，即数组已经按照顺序排序无需进行交换
        int flag = 1;

        while (length--!=0 && flag==1 ){
            flag=0;
            for (int i = 0; i <length; i++) {
                if(arr[i]>arr[i+1]){
                    flag = 1;//如果发生交换 flag=1，while循环继续，否则证明数组已经有序，无需在进行多余的排序
                    //用异或运算（位运算）交换，效率更高——不懂的话，博主有讲解位运算以及交换元素的文章，可以直接点链接或者直接在博主主页搜索
                    arr[i]=arr[i]^arr[i+1];
                    arr[i+1]=arr[i]^arr[i+1];
                    arr[i]=arr[i]^arr[i+1];
                }
            }
        }
    }

}

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

用异或运算（位运算）交换，效率更高——不懂的话，博主有讲解位运算以及交换元素的文章，可以直接点链接或者直接在博主主页搜索。
1.位运算知识点链接
2.不使用辅助变量交换两个数据的值的方法

运行效果：