一、冒泡排序

1、什么是冒泡排序？

    我们把相邻的元素进行两两比较，根据大小来交换元素的位置。

    原始的冒泡排序是稳定排序，由于该排序算法的每一轮都要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O（N^2）

2、java代码实现及优化：

（1）原始的冒泡排序：

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

public static void main(String[] args){
    int[] array = new int[] {5,7,8,6,3,4,2,1};
    sort(array);
    System.out.println(Arrays.toString(array));
}

（2）冒泡排序优化一：

    从上一版代码可以很明显看出，自从经过第六轮排序，整个数列已然是有序的了。但是排序算法仍然继续执行第七轮、第八轮。这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。

private static void sort(int array[]){
    int tmp = 0;
    for(int i = 0; i < array.length; i++){
        //有序标记，判断数组是否有序，初始值为true（true表示有序，false表示无序）
        boolean isSorted = true;
        for(int j = 0; j < array.length-i-1; j++){
            if(array[j] > array[j+1]){
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //有元素交换，所以不是有序，标记变为false
                isSorted = false;
            }
        }
        //如果是有序数组，跳出循环
        if(isSorted){
            break;
        }
    }
}

public static void main(String[] args){
    int[] array = new int[] {5,7,8,6,3,4,2,1};
    sort(array);
    System.out.println(Arrays.toString(array));
}

    这一版代码利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

（3）冒泡排序优化二：

    按照上一版代码的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2，以此类推……。实际上，数列真正的有序区可能会大于这个长度，比如{3,4,2,1,5,6,7,8}数组的第二轮，后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。

    当对于{3,4,2,1,5,6,7,8}这种特殊数据时，后半部分{……,5,6,7,8}已经是有序的,因此可以通过对数列的有序区做界定，在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

private static void sort(int array[]){
    int tmp = 0;
    //记录最后一次交换的位置
    int lastExchangeIndex = 0;
    //无序数列的标记，每次只需比较到这里为止
    int sortBorder = array.length - 1;
    for(int i = 0; i < array.length; i++){
        //有序标记，判断数组是否有序，初始值为true（true表示有序，false表示无序）
        boolean isSorted = true;
        //只比较到无序数列边界
        for(int j = 0; j < sortBorder; j++){
            if(array[j] > array[j+1]){
                tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                //有元素交换，所以不是有序，标记变为false
                isSorted = false;
                //记录最后一次交换的位置
                lastExchangeIndex = j;
            }
        }
        //把无序数列的边界更新为最后一次交换元素的位置
        sortBorder = lastExchangeIndex;
        //如果是有序数组，跳出循环
        if(isSorted){
            break;
        }
    }
}

public static void main(String[] args){
    int[] array = new int[] {3,4,2,1,5,6,7,8};
    sort(array);
    System.out.println(Arrays.toString(array));
}

    这一版代码中，sortBorder就是无序数列的边界。每一轮排序过程中，sortBorder之后的元素就完全不需要比较了，肯定是有序的。

    如有错误欢迎留言！