理解冒泡排序

原理

    假定待排序的序列为5、4、3、2、1，我们最终需要排列为1、2、3、4、5，冒泡排序的原理为将序列分为待排序序列和已排序序列，默认所有的数字都在待排序的序列中，后面每1轮排序中，将最大的数字挪到最右边，比如第1轮将5挪到最右边，5就加入到了已排序的序列，第二轮将4挪到最右边，也就是5的前面，4就加入到了已排序序列里，以此类推。放到程序里，一般是通过2次for循环来实现，第1次循环是从第1个数字开始，到倒数第2个数字为止，原因是冒泡排序是当前元素跟后面的元素进行比对，如果循环到最后一个元素，后面就没有元素了。第2次循环也是从第1个数字开始，跟第1次循环不同的是第2次循环不是到倒数第2个数字为止，而是到倒数第2个数字再减外层循环的当前次数为止，原因是每次执行外层循环的时候，已经将最大值挪到了最右侧，也就是右侧已经是最大值的排序序列，所以在执行内循环时，只需要循环到待排序的末尾就行了。

图解

红色：代表每一轮冒泡的过程。
蓝色：已排序队列。
无色：待排序队列。

WX20190625-180832@2x.png

Java代码实现

    /**
     * 冒泡排序
     * @param arr
     */
    public static int[] maoPao(int[] arr) {
        // 从第1个元素开始，倒数第2个元素止。
        for(int i = 0;i<arr.length-1;i++){
            // 第1个元素开始，倒数第2个元素下标减当前外循环下标止。
            for(int j = 0;j<arr.length-1-i;j++){
                // 如果当前元素的值大于后面元素的，说明要交换。
                if(arr[j] > arr[j+1]){
                    // 将当前位置的值放到临时变量里交换。
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {5,4,2,3,1};
        int[] resultArray = SortUtils.maoPao(arr);
        String result = Arrays.toString(resultArray);
        System.out.println(result);
    }