【排序】冒泡，你真得了解嘛？｜Java 刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、前言

冒泡排序（Bubble Sort）原理是：每一次遍历数组，都去不断地比较相邻的两个元素，如果它们的顺序不对，就交换这两个元素，比如把较大的换到后面。

第一次遍历可以把最大的元素确定下来，放在最后的位置
第二次遍历可以确定第二大的元素，依次类推
这样遍历 N 次后，整个数组就变成递增有序

举栗，动图如下：

二、知识点

知识点，如下：

时间复杂度
逆序对
实现：简单实现
- 改进版：哨兵模式，减少无效比较
- 改进版：减少无效比较

PS: 实习生的面试，会遇到

（1）时间复杂度

最好情况：顺序，时间复杂度 O(N)
最好情况：逆序，时间复杂度 O(N ^ 2)
稳定性：稳定，即原数组中，元素b 在元素a 后面，再排序过程中，元素b 不会到元素a 前面

排序总图，如图：

（2）逆序对

逆序对（inversion）：对于下标 i < j，如果 arr[i] > a[j]，则称 (i, j) 是一对逆序对。

举个栗子，序列 {34, 8, 64, 51, 32, 21} 有多少逆序对？

有9对：

(34, 8), (34, 32), (34, 21), (64, 51), 

(64, 32), (64, 21), (51, 32), (51, 21), (32, 21)
复制代码

可得定理：

定理：任意 N 个不同元素组成的序列平均具有 N(N-1)/4 个逆序对
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为 O(N^2)

那么逆序对，有什么用呢？

代表了，需要交换的次数。
为提高算法效率提供基础

那么要提高算法效率，必须：

每次消去不止 1个逆序对
每次交换相隔较远的 2个元素

（3）实现

每次确定末尾元素位置。

简单实现，如下：

public class BubbleSort {

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        for (int end = n - 1; end > 0; --end)
            for (int i = 0; i < end; ++i)
                if (arr[i] > arr[i+1])
                    swap(arr, i, i+1);
    }
}
复制代码

1）改进版：哨兵模式，减少无效比较

如果一次遍历没有发生交换，则表明已经有序了。

只需增加一个标识位，代码如下：

public class BubbleSort {

    // Time: O(n^2), Space: O(1)
    public void sortEarlyReturn(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        boolean swapped;
        for (int end = n-1; end > 0; --end) {
            swapped = false;
            for (int i = 0; i < end; ++i) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                    swapped = true;
                }
            }
            // 如果全程没有交换，则退出
            if (!swapped) return;
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
复制代码

2）改进版：减少无效比较

使用最后固定的位置，代码如下：

public class BubbleSort {

    // Time: O(n^2), Space: O(1)
    public void sortSkip(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        // 最后固定的位置
        int newEnd;
        for (int end = n-1; end > 0;) {
            newEnd = 0;
            for (int i = 0; i < end; ++i) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                    newEnd = i;
                }
            }
            end = newEnd;
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
复制代码