排序之冒泡排序

基本思想

每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来

原理

每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推，所以我们最多只需要进行 n - 1 趟，即可完成排序， 时间复杂为：

• 最好情况：O(n)
• 最坏情况：O(n^2)

动图演示

图片来源：https://www.runoob.com/w3cnote/bubble-sort.html

代码

 public static void main(String[] args) {
        int[] number = new int[]{
                3, 8, 2, 4, 1, 9
        };

        long startTime = System.currentTimeMillis();   //获取开始时间
        //冒泡排序
        bubbleSort(number, number.length);

        long endTime = System.currentTimeMillis(); //获取结束时间

        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(number));

        return;
    }

    private static void bubbleSort(int[] number, int length) {
//        int[] arr = number;
        int[] arr = Arrays.copyOf(number, length);

        if (length <= 1) {
            return;
        }

        //Java 数组下边从 0 开始
        for (int i = 0; i <= length - 1; i++) {
            boolean bChange = false; // 交换标志

            for (int j = 0; j <= length - 1 - i; j++) {
                if (j != length - 1 && arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    bChange = true;
                }

            }
            if (!bChange) break;

            System.out.format("从小到大第 %d 趟：\n ", i);

            System.out.println(Arrays.toString(number));
            System.out.println(Arrays.toString(arr));
        }

    }

按原理讲，这次冒泡要跑 5 次，但是加上交换标志后，这个例子只需要跑 3 趟就能完成排序

为什么使用 Arrays.copyOf ，Arrays.copyOf 是重新创建了一个数组，重新创建了空间， 数组的改变不会影响之前传入的数组；而数组的引用，会影响传入的数组，可以根据代码查看输出情况