02冒泡排序

原理

一个数组，a[n]，即lenght=n
口语描述：第一个和第二个比，从小到大排，第二个和第三个比，从小到大排，。。。。。。一直到倒数第二个和最后一个比，从小到大排。这样一次循环就找到了最大值，放最后面。再将剩下的数用这种方法找到最大值放最后面。

1. 循环整个数组a[0]~a[n-1]。
   a[0]和a[1]比较，发现a[0] > a[1]，则交换位置，再让a[1]和a[2]比较，发现a[1] > a[2]，则交换位置，一直到a[n-2]和a[n-1]，这样一个循环下来可以找到最大的值，让它到数组的最后一位。

2. 接着以同样的方法，循环a[0]~a[n-2]，又可以找到第二大的值，并放到数组的倒数第二位。

3. 一直到a[0]~a[1]。

代码

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {2, 15, 7, 9, 30, 1, 5};
        bubbleSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

    }
    
    
    /**
     * i ∈ [7,2]
     * i = 7时
     * j ∈ [0, 5]，即a[0]-a[5]，最后a[5]和a[5+1]比较，得到最大的值，放到a[6]位置
     * i = 6时
     * j ∈ [0, 4]，即a[0]-a[4]，最后a[4]和a[4+1]比较，得到第二大的值，放到a[5]位置
     * ...
     * i = 2时
     * j ∈ [0, 0]，即a[0]-a[0]，最后a[0]和a[0+1]比较，得到第二小的值，放到a[1]位置
     * 循环结束
     * a[0]就是剩下的最小的值了
     *
     * 数组lenght=n时
     *
     * 外层取值[n, 2]
     * 当最坏情况，内层循环中，交换方法执行的次数为(n -1)+(n-2)+...+1=(n² - n)/2
     *
     * 忽略低次项，忽略常数项，取最高次n²
     * 得到时间复杂度为：O(n²)
     */
    public static void bubbleSort(int[] array) {
        for (int i = array.length; i > 1; i--) {
            for (int j = 0; j < i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }

            }
        }
    }

}

打印结果：

1 2 5 7 9 15 30