写在前面：最近好久没有写blog了，这是因为前段时间在准备计算机转专业的笔试。哎，笔试成绩不容乐观啊，虽然现在还没有公布笔试成绩，但很担心自己没有60分，没有机会去面试。笔试的程序设计题型非常出乎意料，竟然有四道程序设计大题，而且还是在纸上写代码！我非常不习惯，这是因为我几乎都是在IDE码代码，而且还需要通过编译来提醒我的语法错误。我很担心在答题纸上写了一堆的bug...其中有一题是叫我写一个双冒泡排序算法的函数。什么？我只学过单冒泡啊，双冒泡这个名字也就偶然听过一两次，完全不懂得算法思想和代码的实现啊。当时一紧张，心就静不下来去想，最后也没有写出来。之后就去搜了一下这个双冒泡，发现，原来这么简单！不就是在单冒泡从左到右判断的基础上，再加一次从从右到左的判断吗？现在才知道，原来自己是如此的愚蠢...我相信，这个双冒泡我这辈子都不会忘记了。

冒泡排序

　　这个是最原始的冒泡排序，也就是单冒泡。

void bubbleSort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]);
        }
    }
}

　　我们可以对这段代码进行改进。如果在某趟循环发现没有元素进行过交换，这意味着数组中的元素已经按照顺序排列好了，剩下的循环也不必再进行了，所以直接退出整个排序就好。

　　改进的代码如下：

void bubbleSort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                flag = true;
            }
        }
        if (flag == false) break;
    }
}

　　标记域的作用就是用来记录某趟循环是否有元素进行过交换，初始化为false。如果有元素进行过交换，就把标记域改写为true，表示在这趟循环中有元素进行过交换，下一次的循环还要进行。如果没有交换过，标志域就始终记录为false，进行完这趟循环后，就会结束整一个冒泡排序。

双冒泡排序

　　双冒泡排序可以使得在一次循环结束后，最小的元素会在数组的左边，最大的元素在数组的右边。

　　也就是说，当第一次循环交换结束后，最小的元素在数组的最左边的位置a[0]，最大的元素在数组的最右边的位置a[n - 1]。第二次循环结束后，次小的元素就会在a[1]，次大的元素就会在a[n -  2]，以此类推。

　　只需要在单冒泡的基础上稍做修改，加多一次从右到左的元素判断与交换就好了。相应的代码如下：

void DoubleBubbleSort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i, k = n - 1 - i; j < n - 1 - i; j++, k--) {
            if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]);
            if (a[k] < a[k - 1]) std::swap(a[k], a[k - 1]);
        }
    }
}

　　当然，对双冒泡我们可以做出同样的改进：

void DoubleBubbleSort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = i, k = n - 1 - i; j < n - 1 - i; j++, k--) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                flag = true;
            }
            if (a[k] < a[k - 1]) {
                std::swap(a[k], a[k - 1]);
                flag = true;
            }
        }
        if (flag == false) break;
    }
}

参考资料

　　双向冒泡排序小试：https://zhuanlan.zhihu.com/p/51872712