冒泡排序

冒泡排序流程：

先看动画示意：

流程如下：

1. 假设数组长度n，从左开始遍历数组，每两个进行比大小
2. 例如array[0]和array[1]比大小，如果array[0]大，则和array[1]交换位置
3. 同理依次比较array[1]和array[2]，array[2]和array[3]等，直到数组结束
4. 第一轮遍历完，数组中最大的数就跑到了数组最后一位
5. 第二轮重复上面的步骤遍历数组（最后一位排除在外）
6. 第二轮遍历之后，数组中第二大的数就跑到了数组倒数第二位
7. 依次类推，最后得到一个从小到大顺序排列的数组

代码示例：

public class Bubble {

    public static void main(String[] args) {
        int[] array = {4, 15, 8, 5, 7, 16, 3};
        bubbleSort(array);
        printArray(array);
    }

    public static void bubbleSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if(array[j] > array[i]){
                    int temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                }
            }
        }
    }

    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

改进

如果数组本身有序，在遍历之后就能知道数组已经有序了，就没必要继续后面的遍历了

因此，用一个变量标识是否遍历过程中是否发生交换，没有则说明已经有序，退出循环

public static void bubbleSort(int[] array) {
    int length = array.length;
    for (int i = 0; i < length; i++) {
        boolean swapped = false;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[i]) {
                swapped = true;
                int temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
        }
        if (swapped) {
            break;
        }
    }
}