[数据结构与算法]排序算法之冒泡排序

冒泡定义实现原理

定义：通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

第二趟，就把另一个7吐到倒数第二的位置；第三趟把6吐到了倒数第三位置；第四趟把5吐到倒数第四位置；第五趟把3吐到倒数第五位置；我们总共数组大小为6，所以第六趟2已经在倒数第六位置了，可省略第六趟，总共吐了5趟泡泡，即外层需要循环array.length-1次。
我们在每一趟中都要进行比较交换，需要比较交换的次数为无序的大小-1，无序的大小是多少呢？无序大小 = array.length - 有序的大小（每执行一趟，有序大小++）.

为什么最好是O(n)呢？我们明明有两层ｆｏｒ循环。这是因为数据全部有序的情况下，我们用ｆｌｇ标记一下是否数据交换过。在第一趟结束后如果ｆｌｇ不变，即我们的数据本身就有序，就直接跳出外层循环。

代码实现

public class Main {
    public static void main(String[] args) {
        int[] array = {3,6,7,7,2,5};
        bubbleSort(array);

        for (int i: array) {
            System.out.print(i + " ");
        }
    }
    //冒泡排序
    public static void bubbleSort(int[] array) {
        //外层循环执行的是：每次都把最大的放在最后面，假如有5个数字，那么就执行4次就完成了有序
        for (int i = 0; i < array.length - 1; i++) {
            //用flg标记一下，如果数组已经有序，就不用进行下一轮
            boolean flg = true;
            //内层循环：交换的次数，如果有五个数，进行判断交换4次；减i是因为外层循环一次说明排序好了一次，进行判断交换的次数也会-i
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = false;
                }
            }
            if (flg == true) {
                break;
            }
        }
    }
    public static void swap(int[] array, int a, int b) {
            int tmp = array[a];
            array[a] = array[b];
            array[b] = tmp;

    }
}