冒泡排序

冒泡排序是一种基础的交互排序，每一个元素根据自身大小，一点点地向着数组一侧移动。比如有数字无序数列{4,3,2,1}，按照从小到大的顺序排列。按照冒泡排序的思想， 我们要把相邻的元素两两比较， 当一个元素大于右侧相邻元素时， 交换它们的位置； 当一个元素小于或等于右侧相邻元素时， 位置不变。
思路：
通过两个元素相互比较，当元素大于右侧元素时，交换位置，通过一次循环就可以将最大的值移动到数组的最右端；这仅仅将最大的值移动到数组最右端，还有其他的元素并未排序，所以我们还需要从头开始进行比较，将其他元素进行排序，不考虑性能的情况下，还需要进行数组长度-1次的循环，也就是需要双循环。那么内循环用来进行元素比较并交互位置，外循环则是需要进行内循环的次数。

冒泡排序.gif

**** 算法

    /**
     * 此排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。
     * @param arr
     */
    private static void sort_1(int[] arr){
        int count = 0;
        for (int i = 0; i < arr.length - 1 ; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                System.out.println("外层循环i:"+i+" 内层循环j:"+j);
                System.out.println("比较元素的位置: ["+j+"] vs ["+(j + 1)+"]");
                int temp = 0;
                if (arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
                count = count +1;
                System.out.println("数组:"+ Arrays.toString(arr));
            }
        }
        System.out.println("循环次数:"+count);
    }

控制台：

数组:[4, 3, 2, 1]
外层循环i:0 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[3, 4, 2, 1]
外层循环i:0 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[3, 2, 4, 1]
外层循环i:0 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[3, 2, 1, 4]
外层循环i:1 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[2, 3, 1, 4]
外层循环i:1 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[2, 1, 3, 4]
外层循环i:1 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[2, 1, 3, 4]
外层循环i:2 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[1, 2, 3, 4]
外层循环i:2 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[1, 2, 3, 4]
外层循环i:2 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[1, 2, 3, 4]
循环次数:9

**** 算法2
算法1时可以再优化的，观察算法1的日志，我们可以发现经过第一轮的排序后，最大值4移动到数组最右端；进行第二轮的排序，因为4已经是最大的值了，没必要再跟其前面的值比较了，所以这部分可以优化，也就是每一轮排序后会出现一个有序区域，有序区域的就不必比较了。也就是内层循环要去除有序区域，也就是j < arr.length - i - 1

    private static void sort_1(int[] arr){
        int count = 0;
        for (int i = 0; i < arr.length - 1 ; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                System.out.println("外层循环i:"+i+" 内层循环j:"+j);
                System.out.println("比较元素的位置: ["+j+"] vs ["+(j + 1)+"]");
                int temp = 0;
                if (arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
                count = count +1;
                System.out.println("数组:"+ Arrays.toString(arr));
            }
        }
        System.out.println("循环次数:"+count);
    }

控制台：

数组:[4, 3, 2, 1]
外层循环i:0 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[3, 4, 2, 1]
外层循环i:0 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[3, 2, 4, 1]
外层循环i:0 内层循环j:2
比较元素的位置: [2] vs [3]
数组:[3, 2, 1, 4]
外层循环i:1 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[2, 3, 1, 4]
外层循环i:1 内层循环j:1
比较元素的位置: [1] vs [2]
数组:[2, 1, 3, 4]
外层循环i:2 内层循环j:0
比较元素的位置: [0] vs [1]
数组:[1, 2, 3, 4]
循环次数:6

**** 算法3

  /**
     * 数组举例：{7,1,2,3,4,5,6}
     * 优化策略：减少循环比较趟数
     * 增加一个标记(isSorted,默认是true),每次发生交换，说明目前数组还是无序的，isSorted置为false,
     * 如果这趟循环没有发生交换，说明目前数组已经是有序的了，那么剩下的几趟排序都不需要执行了，提前结束。
     * @param arr
     */
    private static void sort_2(int[] arr){
        for (int i = 0; i < arr.length - 1 ; i++) {
            //数组有序标记位，默认为true,假设是有序的，发生交换就会标记为无序
            boolean isSorted = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                int temp = 0;
                if (arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    //因为有元素进行交换，数组不是有序的，标记为false
                    isSorted = false;
                }

            }
            if (isSorted) break;
        }
    }

**** 算法4

 /**
     * 优化策略：减少每趟的循环次数
     * 情景：每次循环后，右面的很多元素已经是有序的，算法还是会循环比较有序的元素
     * 优化：定义无序数组的边界，每次比较到边界为止，不进行后面的比较了。
     */
    private static void sort_3(int[] array){

        // 最后一次交换的下标
        int lastSwapIndex = 0;
        // 无序数组的边界，每次比较比到这里为止
        int arrBoundary = array.length - 1;

        for (int i = 0; i < array.length - 1; i++) {
            // 数组有序标记位，默认为true,假设是有序的，发生交换就会标记为无序
            boolean isSorted = true;
            for (int j = 0; j < arrBoundary; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = 0;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    // 因为有元素进行交换，数组不是有序的，标记为false
                    isSorted = false;
                    // 最后一次交换元素的位置
                    lastSwapIndex = j;
                }
            }
            // 把最后一次交换元素的位置赋值给无序数组的边界
            arrBoundary = lastSwapIndex;
            // 说明上面内层for循环中，没有交换任何元素，直接跳出外层循环
            if (isSorted) {
                break;
            }
        }
    }

**** 算法5

  /**
     * 优化策略：减少内存开销
     * 情景：每次循环都会创建temp这个变量
     * 优化：通过异或操作来交换两个元素位置
     */
    private static void sort_4(int[] array){

        // 最后一次交换的下标
        int lastSwapIndex = 0;
        // 无序数组的边界，每次比较比到这里为止
        int arrBoundary = array.length - 1;

        for (int i = 0; i < array.length - 1; i++) {
            // 数组有序标记位，默认为true,假设是有序的，发生交换就会标记为无序
            boolean isSorted = true;
            for (int j = 0; j < arrBoundary; j++) {
                if (array[j] > array[j + 1]) {
                    array[j + 1] ^= array[j];
                    array[j] ^= array[j + 1];
                    array[j + 1] ^= array[j];
                    // 因为有元素进行交换，数组不是有序的，标记为false
                    isSorted = false;
                    // 最后一次交换元素的位置
                    lastSwapIndex = j;
                }
            }
            // 把最后一次交换元素的位置赋值给无序数组的边界
            arrBoundary = lastSwapIndex;
            // 说明上面内层for循环中，没有交换任何元素，直接跳出外层循环
            if (isSorted) {
                break;
            }
        }
    }