专栏首页五分钟学算法你的同龄人写不出冒泡排序

你的同龄人写不出冒泡排序

大家好,我是小吴。

昨天在朋友圈看到梁唐写的一篇文章《一半人写不出冒泡排序,你的同龄人都躺下了》,里面提到了一个例子:轮子哥毕业去参加面试的时候,第一轮笔试考察冒泡排序,结果现场的一半学生都没写出来

这个案例《编程珠玑》一书中的一个结论很相似:给予他们充足时间的情况下,有百分之九十以上的人无法编写出完全准确的二分查找法的代码。

估计不少读者看到这两个例子会觉得难以置信,这不是最基础的东西么?

但事实的确如此,上述的案例二我曾经在知乎分享过,很多人尝试了一下没写对,不信的话你可以花两分钟在留言区默写一下二分查找法的代码,然后和下面给出的一个参考答案进行对比:

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 防止溢出
            mid =  min + (max - min) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
 }

今天的主题不是二分查找法,而是冒泡排序,所以不深入聊二分法, 我想手把手带你写对冒泡排序与理解它的优化过程,毕竟,学会了就超过了一半的同龄人呀。

在这里先问大家一个问题:应该大部分人都知道冒泡排序有两个 for 循环,你是先写内循环还是外循环

这个问题先按下不表,继续往下看。

首先,我们来理解冒泡排序的原理:

1、每一次遍历数组,都去不断地比较相邻的两个元素,如果它们的顺序不对,就交换这两个元素,比如把较大的换到后面。第一次遍历可以把最大的元素确定下来,放在最后的位置。

2、第二次遍历可以确定第二大的元素,依次类推。

3、这样遍历 N 次后,整个数组就变成递增有序。

这个原理很好理解也很好记忆,所以我们按照这个原理的步骤来思考如何写代码。

一开始需要遍历数组,从头遍历到尾,代码如下:

// begin 从 0 开始和从 1 开始都是可以的,但个人习惯选择 1 开始
for (int begin = 1; begin <= array.length - 1; begin++) {

}

比较相邻的两个元素,如果它们的顺序不对,就交换这两个元素(默认增序)。

if (array[ begin ] < array[ begin - 1 ]) {
 int tmp = array[ begin ];
 array[ begin ] = array[ begin - 1 ];
 array[ begin - 1 ] =  tmp;
}

联合起来就是:

//为了方便后续的表述,我们把这段代码称为初始代码
for (int begin = 1; begin <= array.length - 1; begin++) {
  if (array[begin] < array[begin - 1]) {
     int tmp = array[begin];
     array[begin] = array[begin - 1];
     array[begin - 1] =  tmp;
 }
}

为了方便后续的表述,我们把上面这段代码称为初始代码

写到这,我们就已经把数组中最大的元素挑选出来了,同时代码也完成了 50%。

我们接下来去完成剩下的 50% 的代码,这部分代码的思考点在于如何做到在第二次遍历去确定第二大的元素

begin 从 1 开始到 array.length - 1 结束挑选出了最大的元素放到了数组的末尾,所以在接下来的遍历中,数组末尾的元素不需要去考虑,即 begin 从 1 开始到 array.length - 2 结束挑选出第二大的元素。

所以,第二次遍历的代码和第一次遍历的代码应该是一样的,唯一的区别点在于 begin 的结束值。

基于这个思考,改造初始代码

begin 的开始都是在 1 开始的,但结束的位置不是确定的位置 array.length - 1,而是一个变量,我们把它称为 end

for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
     int tmp = array[begin];
     array[begin] = array[begin - 1];
     array[begin - 1] =  tmp;
 }
}

end 范围是什么呢?

一开始是 array.length - 1,挑选出最大的元素后缩小为 array.length - 2 去挑选第二大的元素,然后再缩小为 array.length - 3 去挑选到第三大的元素,不断的递减,直到没得挑了。

什么时候没得挑?

直到下标为 1 (图中下标为 1 的元素值刚好也为 1 )的那个位置就没得挑了。

所以,end 的最小值可以为 1。

分析到这,冒泡排序的代码就完成了

//为了表述方便,我们把这块代码称为第一版代码
for (int end = array.length - 1; end >= 1; end--) {
 for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
   int tmp = array[begin];
   array[begin] = array[begin - 1];
   array[begin - 1] =  tmp;
  }
 }
}

然后回到我们之前按下不表的那个问题:冒泡排序有两个 for 循环,要先写内循环还是外循环

答案就是,按照我们最容易理解的思路,需要先去写内循环,再去写外循环。

在笔试的时候,当你顺利地写对冒泡排序的代码时,正常的流程就是面试官开始和你讨论冒泡排序的优化

一个问题需要优化,代表它的一些特殊情况没有得到很好的处理。

那么,第一版冒泡排序代码存在哪些情况没有处理好呢?

第一版冒泡排序代码的每一步操作都是在把相对最大的元素挪到最后的位置,如果一开始数组中的元素就是按照从小到大的顺序进行排列,那么第一版代码中的比较操作就是在做无用功。

所以,我们把优化的方向定在如何处理这种完全有序的情况,完全有序的情况有可能发生在一开始数组就是有序的,也有可能操作到一部分后就完全有序了,无论是哪种情况,当发现数组已经完全有序,我们就停止就行了。

怎么判断当时的情况是否完全有序呢?

先默认此时的数组是有序的,如果发生了交换操作,那么就不是有序的,继续运行代码,否则停止。

第一版的优化代码就来了:

//为了表述方便,我们把这块代码称为第一版的优化代码
for (int end = array.length - 1; end >= 1; end--) {
    boolean sorted = true;
 for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
   int tmp = array[begin];
   array[begin] = array[begin - 1];
   array[begin - 1] =  tmp;
            sorted = false;
  }
 }
    if (sorted) break;
}

接下来,再来看第二种特殊情况,排序过程中发现前面大部分是无序而尾部有序,那么 end 就不用从 array.length - 1 递减到 array.length - 2 再递减到 array.length - 3 ,而是可以骤降,直接减到array.length - 3 的位置。

对于这种情况,思考的方向在于如何定位到局部有序的初始位置

在每一轮的遍历中如果发生了交换操作,那么最后一次交换的位置是在变化的,当交换的位置不再发生改变时,意味着当前的这次遍历中最后的部分元素是有序的了。

我们需要去记录最后一次交换的位置,然后把记录到的位置赋值给 end,这样 end 可以直接略过那部分有序数组的操作。

代码如下:

for (int end = array.length - 1; end >= 1; end--) {
    int lastExchange = 1;
 for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
   int tmp = array[begin];
   array[begin] = array[begin - 1];
   array[begin - 1] =  tmp;
      lastExchange = begin;
  }
 }
    end = lastExchange;
}

好了,以上就是本文的全部内容了,如果觉得有收获,记得点赞、再看、留言、转发,我们下期再见。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 原创 | 一半人写不出冒泡排序,你的同龄人都躺下了

    前段时间在知乎上回答了一个问题“计算机学院的学生该怎样提高自己的编程能力?”,下面的回答五花八门,有些人分享各种各样的资料,什么学Java的,学操作系统的,等等...

    TechFlow-承志
  • 你知道和你不知道的冒泡排序

    我看过的很多的文章都把冒泡排序描述成我们喝的汽水,底部不停的有二氧化碳的气泡往上冒,还有描述成鱼吐泡泡,都特别的形象。

    SH的全栈笔记
  • 算法一看就懂之「 排序算法 」

    之前的文章咱们已经聊过了「 数组和链表 」、「 堆栈 」、「 队列 」和「 递归 」,这些要么是基础的数据结构,要么就是巧妙的编程方法。从今天起咱们来进入真正的...

    奎哥
  • 【整理】待毕业.Net码农就业求职储备

    声明:本文题目来源于互联网,仅供即将从学校毕业的.Net码农(当然,我本人也是菜逼一个)学习之用。当然,学习了这些题目不一定会拿到offer,但是针对就业求职做...

    Edison Zhou
  • 冒泡排序

    对于冒泡排序,很多小伙伴已经可以说很熟悉了,顺手就可以写出来,但对于一个初学者来说,小鹿想通过这篇文章,让你一次性就理解冒泡排序以及冒泡排序的优化,就不用去翻看...

    五分钟学算法
  • 选择排序就这么简单

    选择排序就这么简单 从上一篇已经讲解了冒泡排序了,本章主要讲解的是选择排序,希望大家看完能够理解并手写出选择排序的代码,然后就通过面试了!如果我写得有错误的地方...

    Java3y
  • 第一篇排序算法|冒泡排序

    其实也基本上忘完了学生时代学习的排序算法,一点也想不起来了 ,归结原因就是日常搬砖用的都是现成的方法和工具类,比如说java应用开发中常用的方法Collecti...

    码农王同学
  • 冒泡排序

    songleo
  • 十大经典排序算法 -- 动图讲解

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    互扯程序
  • 看故事,学排序

    在面试的过程中,有的面试官也会问到这个排序。今天我们看一个故事来感受一下冒泡排序的过程。

    用户1260737
  • 这或许是东半球分析十大排序算法最好的一篇文章

    本文全长 14237 字,配有 70 张图片和动画,和你一起一步步看懂排序算法的运行过程。

    五分钟学算法
  • 这或许是东半球分析十大排序算法最好的一篇文章

    本文全长 14237 字,配有 70 张图片和动画,和你一起一步步看懂排序算法的运行过程。

    乔戈里
  • 这或许是东半球分析十大排序算法最好的一篇文章

    本文全长 14237 字,配有 70 张图片和动画,和你一起一步步看懂排序算法的运行过程。

    AI科技大本营
  • 我们真的搞懂这些排序算法了吗?(一)

    或许你已经学过了这些常见的排序算法,或者你看过了别人写的文章,但是这篇文章绝对不会浪费你的时间,一定会有所收获的。

    godweiyang
  • 冒泡排序

    面试官: 写一个冒泡排序吧 冒泡排序是一个比较经典和简单的排序算法,今天我们从从算法本身,时间复杂度以及稳定性方面来看看冒泡排序,这些方面也是研究其他排序算法的...

    用户1260737
  • 坐在马桶上看算法(2):邻居好说话,冒泡排序

    原文出处: 纪磊 简化版的桶排序不仅仅有上一节所遗留的问题, 更要命的是:它非常浪费空间!例如需要排序数的范围是0~2100000000之间,那你则需要申请2...

    wangxl
  • 算法之常见排序算法-冒泡排序、归并排序、快速排序

    对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职...

    本人秃顶程序员
  • 图形图像算法中必须要了解的设计模式(2)

    AI越来越火热,人工智能已然成风!而人工智能最重要是各种算法,因此机器学习越来越受到追捧,算法越来越被重视。

    OpenCV学堂
  • 动态可视化十大排序算法之冒泡排序

    我现在还能记得自己当时在 VC++ 6.0 上按照谭浩强老师的 C 语言教材敲出第一个冒泡排序时的激动心情。满满的成就感,不得不说,编程爱好者的快乐就是如此简单...

    与你一起学算法

扫码关注云+社区

领取腾讯云代金券