冒泡排序

冒泡排序的中心思想就是通过遍历找出数组中最小的数往前排.

import java.util.Arrays;

/**
 * 冒泡排序
 * 该排序算法的核心就是循环遍历,两两比较,找出较小的那个数往前排
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 9, 8, 2, 7};
        int temp;
        //外层循环表示遍历次数.  7个数, 只需要遍历比较6次即可,所以  i < arr.length - 1
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层循环的目的: 两两比较,大的数往后移,小的数往前移
            /*
                i = 0时,
                原始数组:     3, 4, 1, 9, 8, 2, 7
                内层循环1次:  3, 4, 1, 9, 8, 2, 7
                内层循环2次:  3, 4, 1, 9, 2, 8, 7
                内层循环3次:  3, 4, 1, 2, 9, 8, 7
                内层循环4次:  3, 4, 1, 2, 9, 8, 7
                内层循环5次:  3, 1, 4, 2, 9, 8, 7
                内层循环6次:  1, 3, 4, 2, 9, 8, 7

                i = 1时,
                内层循环1次:  1, 3, 4, 2, 9, 7, 8
                内层循环2次:  1, 3, 4, 2, 7, 9, 8
                内层循环3次:  1, 3, 4, 2, 7, 9, 8
                内层循环4次:  1, 3, 2, 4, 7, 9, 8
                内层循环5次:  1, 2, 3, 4, 7, 9, 8

                由上面的示例可知,因为第一次外层循环完成之后, 数组中的最小值1已经排在了arr[0]处,
                后面无需再与arr[0]进行比较了,所以内层跳出循环的条件是j > i (可以理解成arr[i]及之前的数已经有序了)
             */
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1]; //将大的数往后移
                    arr[j - 1] = temp;
                }
            }
            System.out.printf("第%d排序之后的数组:%s
", i, Arrays.toString(arr));
        }
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

上面交换数组中两个元素的位置使用了一个临时变量,下面再看一个比较经典的方式交换数组中两元素的位置

   /**
     * 数组中交换两个数字的位置
     * 这方法还是挺有意思的
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j];
        // 将第一行代码代入可得,arr[j] = arr[i] , 即是将arr[i]赋值给了arr[j]
        arr[j] = arr[i] - arr[j];
        // 将第一行代码代入, 由第二行代码可知 arr[j] 即是arr[i] ,所以右边等于arr[i] + arr[j] - arr[i] = arr[j]
        // 即是将arr[j]赋值给了arr[i]
        arr[i] = arr[i] - arr[j];
    }

冒泡排序的时间复杂度最坏: O(n^2)

冒泡排序的时间复杂度最好: O(n)

当数据越接近正序时,性能越好

冒泡排序优化

最开始的示例代码中,arr其实只需要两次遍历即可排序成功, 所以我们可以加入标识位, 用于排序成功后提交结束遍历,代码如下:

/**
 * 冒泡排序
 * 该排序算法的核心就是循环遍历,两两比较,找出较小的那个数往前排
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 9, 8, 2, 7};
        int temp;
        boolean exchange = false;
        //外层循环表示遍历次数.  7个数, 只需要遍历比较6次即可,所以  i < arr.length - 1
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层循环的目的: 两两比较,大的数往后移,小的数往前移
            /*
                i = 0时,
                原始数组:     3, 4, 1, 9, 8, 2, 7
                内层循环1次:  3, 4, 1, 9, 8, 2, 7
                内层循环2次:  3, 4, 1, 9, 2, 8, 7
                内层循环3次:  3, 4, 1, 2, 9, 8, 7
                内层循环4次:  3, 4, 1, 2, 9, 8, 7
                内层循环5次:  3, 1, 4, 2, 9, 8, 7
                内层循环6次:  1, 3, 4, 2, 9, 8, 7

                i = 1时,
                内层循环1次:  1, 3, 4, 2, 9, 7, 8
                内层循环2次:  1, 3, 4, 2, 7, 9, 8
                内层循环3次:  1, 3, 4, 2, 7, 9, 8
                内层循环4次:  1, 3, 2, 4, 7, 9, 8
                内层循环5次:  1, 2, 3, 4, 7, 9, 8

                由上面的示例可知,因为第一次外层循环完成之后, 数组中的最小值1已经排在了arr[0]处,
                后面无需再与arr[0]进行比较了,所以内层跳出循环的条件是j > i (可以理解成arr[i]及之前的数已经有序了)
             */
            for (int j = arr.length - 1; j > i; j--) {
                exchange = false;
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1]; //将大的数往后移
                    arr[j - 1] = temp;
                    exchange = true;
                }
            }
            System.out.printf("第%d排序之后的数组:%s
", i, Arrays.toString(arr));
            if (!exchange) {
                break;
            }
        }
        System.out.println("排序后:" + Arrays.toString(arr));
    }

第0排序之后的数组:[1, 3, 4, 2, 9, 8, 7]
第1排序之后的数组:[1, 2, 3, 4, 7, 9, 8]
第2排序之后的数组:[1, 2, 3, 4, 7, 8, 9]  // 第三次排序数据没有发生交换,直接结束
排序后:[1, 2, 3, 4, 7, 8, 9]