前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >美团面试,我竟然输给了冒泡排序。。。

美团面试,我竟然输给了冒泡排序。。。

作者头像
Java团长
发布2019-07-01 16:05:24
7261
发布2019-07-01 16:05:24
举报
文章被收录于专栏:微信公众号:Java团长

来源:程序员私房菜(ID:eson_15)

前一阵子有个读者在微信里跟我聊了一件很有趣的事情,他去美团实习,面试让他哭笑不得,因为败在了冒泡排序上。

情况是这样子的,当时和面试官聊的感觉还可以,就在他觉得好像差不多快结束的时候,面试官给他扔了个题:“我这刚好有纸和笔,你来写个冒泡排序吧。”

这位读者心里一慌,为什么慌,倒并不是因为不会写,因为作为一个程序员,冒泡排序基本上没有不会写的,而是事发突然,感觉不太妙。当时他是这么写的:

代码语言:javascript
复制
public void bubbleSort(int[] source) {
    for(int i = source.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1])
                 //交换,具体实现略
                 swap(source, j, j+1); 
        }
    }
}

果不其然,他写了之后,面试官就问他,这种写法有没有什么问题?能否继续优化?结果还真没答上来。(看到这里,读者们不妨也先思考下如何优化。)

今天就这个冒泡排序,我们再多聊几句,回归一下经典。也希望以后有朋友实习也好,校招也罢,不要再栽在同样的问题上了。

冒泡排序算法的时间复杂度高,但是冒泡排序简单,基本流程是:每一轮从头开始两两比较,将较大的项放在较小项的右边,这样每轮下来保证该轮最大的数在最右边。如何实现?就如上面这位朋友所写的那样,基本上大家都会写。

但是今天主要讨论的是如何优化,有人可能会说,这是再简单不过的算法了,还有什么好优化的?确实,上面这段代码没有毛病,但的确是有可优化之处的。

我们可以假设一种场景,比如 8 1 2 3 5 7,进行一次排序之后,结果就变成了 1 2 3 5 7 8,那我们还有必要再像上面代码里那样继续循环下去吗?肯定没有必要了,因为这已经是最终结果了。

那针对上面的代码,我们优化的点主要在于:假如某一趟排序之后已经有序,我们需要减少排序的趟数。否则就做了很多无用功。

针对这个问题,我们可以考虑在算法中加入一个布尔变量,来标识该轮有没有进行数据的交换,若在某一趟排序中未发现数据位置的交换,则说明待排序的无序区中所有的项均已满足排序后的结果。那么就没有必要再次排序下去了。可以如下改造:

代码语言:javascript
复制
public void bubbleSort(int[] source) {
    boolean exchange;
    for(int i = source.length - 1; i > 0; i--) {
        exchange = false;
        for(int j = 0; j < i; j++) {
            if(a[j] > a[j+1]) {
                swap(source, j, j+1);
               exchange = true;
            }
        }
        if(!exchange) return;
    }
}

这样就优化完了,其实代码逻辑很简单,通过一个布尔变量即可监控一趟过程有没有进行数据交换。

冒泡排序最好的情况是初始状态是正序的,一次扫描即可完成排序,所以最好的时间复杂度为O(N);最坏的情况是反序的,此时最坏的时间复杂度为O(N^2)。平均情况,每轮N/2次循环,N轮时间复杂度为O(N^2)。所以它并不是个好的排序算法。这个问题的讨论就到此结束,如果有更好的优化算法也欢迎留言讨论。

冒泡排序并不好,但为什么面试官还会去问?针对这件事情,我们需要注意什么呢?

1. 经典的东西,可能已经不用了,但是从经典的东西身上,我们能学到的还有很多,否则也不会成为经典。特别是那些面试经常被问到的,总有它存在的合理性。

2. 教科书上的东西不代表实战,所以很多时候考虑到非理想情况下,就可能不那么适用了。面试官往往更加注重的是在不适用的情况下,面试者是如何应对的。面试官更加看重的是面试者的思路。

3. 应届生不能浮躁,特别是在准备面试的时候,一定要步步为营,切忌好高骛远,浅尝辄止,多学习学习经典的数据结构和算法,多做做算法题还是很有必要的。

PS:如果觉得我的分享不错,欢迎大家随手点赞、转发。

END

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-11-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Java团长 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档