入门算法：冒泡排序

上手难度：★

算法复杂度：O(n^2)

BubbleSort.gif

排序思想：

两层循环，外层是n-1次循环，同时设定一个标记flag，内层是从0到arr.length - i次循环；
内层逻辑是把大值往后交换，第一次外层循环走完后，最大的值自然就放到最后一位了，所以内存循环是arr.length-1的写法；
每次一轮外循环都会把剩余最大的值安排好位置，如果在某次循环中，flag没有变化，说明不需要交换已经排好序了，可以结束排序。

代码实现：

public class BubbleSort {
    /**
     * 交换数组中两个元素的位置
     */
    private static void swap(int[] arr, int x, int y){
        if(x < 0 || y < 0 || x > arr.length || y > arr.length){
            return;
        }
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    public static int[] bubbleSort(int[] arr){
        // 对 arr 进行拷贝，不改变参数内容
//        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        for (int i = 1; i < arr.length; i++) {
            //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return arr;
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        bubbleSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}

优点：

逻辑简单，易上手
特点：当输入的数据是反序时，时间复杂度最高为O(n^2)