八种排序算法可以按照如图分类,本文主要介绍冒泡排序。

交换排序算法之冒泡排序 算法 第1张

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

交换排序

所谓交换,就是序列中任意两个元素进行比较,根据比较结果来交换各自在序列中的位置,以此达到排序的目的。


冒泡排序

冒泡排序是一种简单的交换排序算法,以升序排序为例,其核心思想是:

  1. 从第一个元素开始,比较相邻的两个元素。如果第一个比第二个大,则进行交换。
  2. 轮到下一组相邻元素,执行同样的比较操作,再找下一组,直到没有相邻元素可比较为止,此时最后的元素应是最大的数。
  3. 除了每次排序得到的最后一个元素,对剩余元素重复以上步骤,直到没有任何一对元素需要比较为止。

交换排序算法之冒泡排序 算法 第2张

用 Java 实现的冒泡排序如下

/**
 * 冒泡排序常规版
 *
 * <p>没有经过任何优化操作的版本
 * @param arr 待排序的整型数组
 * @return 比较次数
 */
public static int bubbleSortOpt1(int[] arr) {

    if (arr == null) {
        throw new NullPointerException();
    } else if (arr.length == 0) {
        return 0;
    }

    int temp;
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
            count++;
        }
    }
    return count;
}

算法优化

现在有个问题,假如待排序数组是 2、1、3、4、5 这样的情况,按照上述代码实现,第一次循环即可得出正确结果。但循环并不会停止,而是继续执行,直到结束为止。显然,之后的循环遍历是没有必要的。

为了解决这个问题,我们可以设置一个标志位,用来表示当前次循环是否有交换,如果没有,则说明当前数组已经完全排序。

/**
 * 冒泡排序优化第一版
 *
 * <p>设置了一个标志位,用来表示当前次循环是否有交换,如果没有,则说明当前数组已经完全排序
 * @param arr 待排序的整型数组
 * @return 比较次数
 */
public static int bubbleSortOpt2(int[] arr) {

    if (arr == null) {
        throw new NullPointerException();
    } else if (arr.length == 0) {
        return 0;
    }

    int temp;
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        int flag = 1;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = 0;
            }
            count++;
        }
        // 没有发生交换,排序已经完成
        if (flag == 1) {
            return count;
        }
    }
    return count;
}

算法还可以再优化,比如 3、4、2、1、6、7、8 这个数组,第一次循环后,变为 3、2、1、4、6、7、8 的顺序,我们发现,1 之后的 4 、6、7、8 已经有序了,第二次循环就没必要对后面这段再遍历比较。

假设一次循环后数组第 i 个元素后所有元素已经有序,优化目标就是下次循环不再花费时间遍历已经有序的部分。关键在于如何定位 i 这个分界点,其实并不难,可以想象,由于 i 之前的元素是无序的,所以一定有交换发生,而 i 之后的元素已经有序,不会发生交换,最后发生交换的地点,就是我们要找的分界点。

/**
 * 冒泡排序优化第二版
 *
 * <p>定位最后发生交换的分界点,之后的元素无需遍历。
 * @param arr 待排序的整型数组
 * @return 比较次数
 */
public static int bubbleSortOpt3(int[] arr) {

    if (arr == null) {
        throw new RuntimeException();
    } else if (arr.length == 0) {
        return 0;
    }

    int temp;
    int count = 0;
    int len = arr.length - 1;
    for (int i = 0; i < arr.length - 1; i++) {
        // 记录最后一次交换位置
        int lastChange = 1;
        for (int j = 0; j < len; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 每交换一次更新一次
                lastChange = j;
            }
            count++;
        }
        len = lastChange;
    }
    return count;
}

整合第一版和第二版,得到最终版本的冒泡算法

/**
 * 冒泡排序优化最终版
 *
 * <p>整合第一版和第二版
 * @param arr 待排序的整型数组
 * @return 比较次数
 */
public static int bubbleSortOpt4(int[] arr) {

    if (arr == null) {
        throw new RuntimeException();
    } else if (arr.length == 0) {
        return 0;
    }

    int temp;
    int count = 0;
    int len = arr.length - 1;
    for (int i = 0; i < arr.length - 1; i++) {
        // 记录最后一次交换位置
        int lastChange = 1;
        int flag = 1;
        for (int j = 0; j < len; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 每交换一次更新一次
                lastChange = j;
                flag = 0;
            }
            count++;
        }
        // 没有发生交换,排序已经完成
        if (flag == 1) {
            return count;
        }
        len = lastChange;
    }
    return count;
}

各位可以自行设计测试数据,看看返回的比较次数大小是否减少。


性能分析

分析最优版本算法,最好的情况是一开始已经排好序,那就没必要交换了,直接返回,此时只走了外层的第一次循环,最优时间复杂度为 O(n)。

最坏的情况当然是数组是逆序的,这样里外两层循环都走了遍,最坏时间复杂度为 O( n^2 )。

空间复杂度则是用于交换的临时变量,至于标志位和其他的因算法的不同实现有差异。


扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄