冒泡排序

冒泡排序的思想

把相邻的元素进行两两对比，如果左边元素比右边小，就无需变换位置，如果左边元素比右边大，则交换两个元素的位置，第一轮把最大的元素交换到最右边，总共进行n-1轮，时间复杂度为O(n2)

第一版排序

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

第二版排序

假设要进行八轮的排序遍历，到第六轮的时候已经排序完成，第七轮是没有进行元素交换的，那么此时可以设置一个标志位布尔值，来判断是否有元素交换，从而结束循环，节省运算时间

public static void sort(int array[]) {
    for (int i = 0; i < array.length -1; i++) {
        // 每一轮循环的开始都是true
        boolean isSorted = true;
        for (int j = 0; j < array.length - i - 1; j++) {
            int temp = 0;
            if (array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }
    }
}

第三版排序

假设一个长度为n的无序数组，在中间的某一个位置开始往后都是有序的，那么排序的时候则无需再进行该位置后面的元素比较了，例如：[3,5,6,1,3,7,8,9]，在该数组中，789是有序的且7比前面都大，则意味着在比较到7的位置时，后面都不会有元素交换，那么记录下7的位置，在下轮的循环中只遍历7之前的元素。

public static void sort(int array[]) {
    // 记录最后一次交换的位置
    int changeIndex = 0;
    // 无序数列的边界，每次只到这里即可
    int sortBorder = array.length - i;
    for (int i = 0; i < array.length - 1; i++) {
        // 每一轮循环的开始都是true
        boolean isSorted = true;
        for (int j = 0; j < sortBorder; j++) {
            int temp = 0;
            if (array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                isSorted = false;
                changeIndex = j;
            }
        }
        sortBorder = changeIndex;
        if (isSorted) {
            break;
        }
    }
}