排序 -- 冒泡

聊聊排序吧

• 冒泡排序

• 选择排序

• 插入排序

• 快速排序

• 归并排序

• 计数排序

• 桶排序

• 堆排序

本篇 冒泡排序

---

相信很多人接触到第一个排序算法就是冒泡排序了, 从头聊聊这个算法.

• 排序思想
  对一个长度为n的数组进行n次循环, 每次将那个最大的数放到其该在的位置上, 从后往前依次有序.
• 代码实现

private void doSort0(int[] arr) {
    int tmp;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // swap
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

• 代码很简单, 就两层循环, 每次将当前循环最大的数像冒泡一样一个一个排到最后面
• 可以优化吗?

---

优化思路一 提前结束

上面每层内循环都是将当前最大的那个数往下沉, 那么如果中间有一次没有数据交换, 那么

• 后面的循环还会有数据交换吗?
• 还有必要继续循环吗?
• 数组是否已经有序了呢?

优化代码

private void doSort1(int[] arr) {
    int tmp;
    boolean flag;
    for (int i = 0; i < arr.length; i++) {
        // 提前结束标志位，如果某次冒泡没有数据交换
        // 表示当前数据已经有序，可以提前结束冒泡排序
        flag = false;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // swap
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = true;
            }
        }
        if (!flag) break;
    }
    System.out.println(Arrays.toString(arr));
}

• 能否继续优化?

---

优化思路二 排序边界

其实冒泡跟选择/插入一样都是线性排序, 他们的思路都差不多, 排序过程都分为有序数组与无序数组, 那么这个有序与无序边界就可以做做文章了.

• 上次数据交换的位置就是有序与无序的分界线
• 下次内循环比较的终点就可以是这个边界

优化代码

private void doSort2(int[] arr) {
    int tmp;
    // 上次数据交换位置
    int lastChargeIndex = 0;
    // 无序数组的边界
    int sortBorder = arr.length - 1;
    boolean flag;
    for (int i = 0; i < arr.length; i++) {
        // 提前结束标志位，如果某次冒泡没有数据交换
        // 表示当前数据已经有序，可以提前结束冒泡排序
        flag = false;
        for (int j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j+1]) {
                // swap
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = true;
                // 记录最后一次更新的记录
                lastChargeIndex = j;
            }
        }
        if (!flag) break;
        // 更新无序数组的边界
        sortBorder = lastChargeIndex;
    }
    System.out.println(Arrays.toString(arr));
}

• 这两种优化较之前减少了排序总比较次数而没有增加过多额外成本, 属于成功优化.
• 但其总的时间复杂度(O(N^2))并没有发现变化, 这里只是减少了其系数与常量

排序分析

名称	原地	稳定	最好	最坏	平均
冒泡排序	是	是	O(N)	O(N^2)	O(N^2)

从下面四点来评估一个算法

• 最好/最坏/平均 时间复杂度
• 时间复杂度的 系数/低阶/常数
• 原地排序 - 空间复杂度
• 稳定排序 - 相同元素相对位置是否改变