冒泡排序的两次改进

最近在学校数据库里检索到一篇有关冒泡排序的论文，感到很惊奇，对冒泡排序作改进居然也能发有论文，并被中国知网收录，仔细阅读了一下这篇仅两面的论文，发现作者对冒泡排序的改进还确实有点新意，就忍不住要写点东西来讨论讨论。

首先把冒泡的原始版本贴出来，注意本文章的代码都是自己写的，也就是说不保证正确性的，况且人家论文里也只有伪码，不过我们这里讨论思想比跑通代码更重要。之所以提前加上这么一个注意，不是因为自己写代码混乱，而是因为很难保证程序是滴水不漏的，就如《代码之美》里提到的，一个二分查找是很少有人能写到完全正确的，尽管它看似简单。回到我们的讨论吧，对于冒泡排序我就不作多解释了，任何一本C语言书上都会有，主要就是不停地进行相邻两个数之间的比较，那么较大的数就会一直往后冒。

//__p为数组地址，__n为数组大小
void bubble_sort(int *__p, int __n)
{
    for (int i=__n-1; i>=0; i--) {

        for (int j=0; j<=i-1; j++) {
            if (__p[j]>__p[j+1]) {
                swap(__p[j],__p[j+1]);//两数交换
            }
        }
    }
}

原始版本的冒泡排序是很傻的，因为它不管数组是否已经有序，或者是局部有序，它都会做(n-1)+(n-2)+...+2+1次比较，所以很早就有人对它做改进，这种改进很容易想到，思想也很简单，就是添加一个标志变量，其作用就是，一旦发现数组已经有序，那么马上跳出循环，排序完成，这就避免了大量的重复比较。具体实现如下：

void bubble_sort(int *__p, int __n)
{
    //初始化为false，表示未排序好
    bool is_sorted = false;

    //如果发现已排序，则的循环结束
    for (int i=__n-1; i>=0 && !is_sorted; i--) {
        is_sorted = true;

        for (int j=0; j<=i-1; j++) {
            if (__p[j]>__p[j+1]) {
                swap(__p[j],__p[j+1]);
                //一旦出现元素交换，就表示并没有排序好，将会进入下一轮循环
                is_sorted = false;
            }
        }
    }
}

常见的改进版本中，只是使用了一个bool型变量来标识数组是否已经排序好，不过这种改进对大致有序的数组还是表现不佳，假如我们能够记录下一轮循环中，发生交换的最后的位置，那么表示在这个位置之后的元素已经有序，这就意味着，下一轮循环，我们只需要从开始逐一比较到该位置即可以停止本轮循环，所以我们不应使用一个bool变量，而应使用一个int变量记录最后的交换位置，对于大体有序的数组会表现地更好。这种方法的提出就来自于该论文。实现代码如下：

void bubble_sort(int *__p, int __n)
{
    //用于记录最后的交换位置
    int change_pos;

    //i赋值为change_pos，以直接跳过有序的部分
    for (int i=__n-1; i>=0; i=change_pos) {
        //如果没有发生交换，则change_pos为-1，循环结束
        change_pos = -1;

        for (int j=0; j<=i-1; j++) {
            if (__p[j]>__p[j+1]) {
                swap(__p[j],__p[j+1]);
                //记录发生交换的位置
                change_pos = j;
            }
        }
    }
}

两次改进确实让冒泡排序运行地更快了，不过只是对平均情况而言，对于最坏情况，即一个序列是完全逆序，冒泡依然逃避不了O(n^2)的厄运，而且两种改进反而会带来一些运算上的小负担。论文作者确实很有创意，不过选择了冒泡，就选择了悲剧，如果作者能够把改进后的平均情况下复杂度计算出来，论文可能会让人感到更有品味，而不仅仅是一个小trick，一个没有大用途的小把戏。总之，对于这样一个小的idea能够发表成论文，我表示很有点惊叹！