13-算法题-冒泡排序

排序算法，一般来说，让面试者当场手写还是挺考验功底的。

所以，我们以前会让面试者自己选择任意一个排序算法，所以你准备好了吗？

1，首先，冒泡排序的定义

每次冒泡排序都会对相邻的两个元素进行比较，
如果前面的元素比后面的元素大，则进行互换，
一次冒泡会至少让一个元素移动到它应该在的位置。
重复n次，就完成n个元素的排序工作。

2，图例

3，关于上面的优化思考

其实，当某次冒泡操作没有数据交换时，说明已经达到了完全有序，
不用再继续后续的冒泡操作。

4，所以，我们最终的冒泡排序可以这么写

public void bubbleSort(int[] array){
    if(array.length <= 1){
        return;
    }

    //重复n次冒泡
    for(int i=0;i<array.length;i++){
        //是否可以提交退出冒泡的标记
        boolean flag = false;
        //相邻之间两两比较，并且每次减少一位参与比较
        for(int j=0;j<array.length-i-1;j++){
            if(array[j] > array[j+1]){
                //需要交换
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                //
                flag = true;//有数据交换，不能提前退出
            }
        }
        if(!flag){
            //没有数据交换，提前退出冒泡比较
            break;
        }
    }
}