• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

双冒泡排序

开发技术 开发技术 2周前 (04-30) 7次浏览

  写在前面:最近好久没有写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


程序员灯塔
转载请注明原文链接:双冒泡排序
喜欢 (0)