多语言版冒泡排序及优化

简介

冒泡排序（Bubble Sort），是一种简单的交换排序方法，算法的名字是由于其排序的过程就像碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

以上内容来自 百度百科，含算法原理及算法分析部分内容，有兴趣的自行阅读一下

代码

Java版

int[] array = {27, 12, 36, 12, 24, 45, 68, 59, 91};
for (int i = 0; i < array.length - 1; i++) {
    for (int j = 0; j < array.length - i - 1; j++) {
        if (array[j] > array[j + 1]) {
            int t = array[j];
            array[j] = array[j + 1];
            array[j + 1] = t;
        }
    }
}

Python版

lst = [27, 12, 36, 12, 24, 45, 68, 59, 91]
length = len(lst)
for i in range(length - 1):
    for j in range(length - i - 1):
        if lst[j] > lst[j + 1]:
            lst[j], lst[j + 1] = lst[j + 1], lst[j]

代码分析

这里不得不说一句，Python的语法特性写起来感觉就是爽（主要指交换这块，Lua语言也支持该语法，但JavaScript不支持）。
这里分析一下代码的实现思路及缺陷：

1. 由外层循环控制比较轮数（N - 1次），以代码中的数组为例就是比较8轮
2. 每轮由第0个元素开始依次与后面的元素比较，大的元素被交换到后面的位置上，一轮交换下来，最大的元素会被交换到最后面的位置上
3. 每轮过后，最后一次交换的位置后面的元素即为有序部分，下轮不再参与比较，由代码中的length - i - 1部分控制
   下面日志描述了排序过程：

第 1 轮排序后，序列为：[12, 27, 12, 24, 36, 45, 59, 68, 91]
第 2 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 3 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 4 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 5 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 6 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 7 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 8 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
长度为 9 的序列，冒泡排序一共比较了 36 次
每轮比较次数：8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

优化

通过对每轮排序结果的观察，不难发现实际在第3轮时，整体已经有序，后面几轮都是多余的，这里引出第一个优化点，当列表整体有序时，取消多余的轮数

优化一

for (int i = 0; i < array.length - 1; i++) {
    // 假定序列已经是有序的了，如果后面发生交换，则说明为假
    boolean flag = true;
    for (int j = 0; j < array.length - i - 1; j++) {
        times++;
        if (array[j] > array[j + 1]) {
            int t = array[j];
            array[j] = array[j + 1];
            array[j + 1] = t;
            flag = false;
        }
    }
    // 如果为真，则跳出循环
    if (flag) break;
}

上述代码的输出日志（注：代码中的日志代码我删除了，需要的自行加上）：

第 1 轮排序后，序列为：[12, 27, 12, 24, 36, 45, 59, 68, 91]
第 2 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 3 轮排序后，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
长度为 9 的序列，冒泡排序一共比较了 21 次
每轮比较次数：8 + 7 + 6 = 21

代码中设置一个标志位，假定列表初始有序，每轮排序中一旦发生交换，则为假，直到整体有序后，下一轮未发生任何交换，则为真，终止所有循环，排序结束

优化二

不过观察上述代码的每轮比较次数发和列表本身，发现每轮比较的次数有点多，实际后面部分本就有序，每轮比较时根本不需要比较这么多次（视情况而定，如果后面部分本就无序，则该问题不是问题）

// 设定一个有序边界，表示该索引以后的元素已经有序，初始为最后一个元素，表示没有有序项
int border = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
    // 假定序列已经是有序的了，如果后面发生交换，则说明为假
    boolean flag = true;
    int lastIndex = -1;
    for (int j = 0; j < border; j++) {
        times++;
        if (array[j] > array[j + 1]) {
            int t = array[j];
            array[j] = array[j + 1];
            array[j + 1] = t;
            flag = false;
            // 发生了交换，则将交换的位置赋值给边界，一轮比较完后，就会得到正确的有序边界
            lastIndex = j;
        }
    }
    border = lastIndex;
    // 如果为真，则跳出循环
    if (flag) break;
}

上述代码输出日志：

第 1 轮排序后，有序边界为：6，序列为：[12, 27, 12, 24, 36, 45, 59, 68, 91]
第 2 轮排序后，有序边界为：2，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
第 3 轮排序后，有序边界为：-1，序列为：[12, 12, 24, 27, 36, 45, 59, 68, 91]
长度为 9 的序列，冒泡排序一共比较了 16 次
每轮比较次数：8 + 6 + 2 = 16

设置一个有序边界，该边界（不包含边界本身）以后的元素有序，初始值为数组最后一个元素，即没有有序部分，直到第一轮比较完成后，最后一次比较的位置即为边界，其后面的元素皆为有序（否则一定会发生交换），后面几轮比较中，比较到该边界即结束，同时更新边界值，该方法对后半部分有序的列表排序有一定的优化作用，但如果后半部分本就无序，那么该方法意义不大

优化三

除了以上优化方法以外，还有其它优化方法，比如鸡尾酒排序是一种冒泡排序的变种。通常冒泡排序，只选一边进行冒泡，但在鸡尾酒排序排序中，同时向两边冒泡，小的向左，大的向右，以减少比较的轮数。

结语

以上内容参考：漫画：什么是冒泡排序？。

总之学无止境，原来最简单的冒泡排序都有这么多的学问

知道的越多，越觉得浅薄；见得越多，越觉得渺小。