认识达内从这里开始

认真做教育专心促就业

美团面试，我竟然输给了冒泡排序……

发布：济南达内
来源：济南达内
时间：2019-04-23 15:52

济南达内的小编总结，前一阵子有个读者在微信里跟我聊了一件很有趣的事情，他去美团实习，面试让他哭笑不得，因为败在了冒泡排序上。
情况是这样子的，当时和面试官聊的感觉还可以，就在他觉得好像差不多快结束的时候，面试官给他扔了个题：“我这刚好有纸和笔，你来写个冒泡排序吧。”
这位读者心里一慌，为什么慌，倒并不是因为不会写，因为作为一个程序员，冒泡排序基本上没有不会写的，而是事发突然，感觉不太妙。当时他是这么写的：
public void bubbleSort（int[] a） {
for（int i = a.length - 1; i > 0; i--） {
for（int j = 0; j < i; j++） {
if（a[j] > a[j+1]）
//交换，具体实现略
swap（a, j, j+1）；
}
}
}
果不其然，他写了之后，面试官就问他，这种写法有没有什么问题？能否继续优化？结果还真没答上来。（看到这里，读者们不妨也先思考下如何优化。）
今天就这个冒泡排序，我们再多聊几句，回归一下经典。也希望以后有朋友实习也好，校招也罢，不要再栽在同样的问题上了。
冒泡排序算法的时间复杂度高，如果不清楚算法复杂度如何计算，可以参考下这篇文章：循序渐进带你学习时间复杂度和空间复杂度。但是冒泡排序简单，基本流程是：每一轮从头开始两两比较，将较大的项放在较小项的右边，这样每轮下来保证该轮最大的数在最右边。如何实现？就如上面这位朋友所写的那样，基本上大家都会写。
但是今天主要讨论的是如何优化，有人可能会说，这是再简单不过的算法了，还有什么好优化的？确实，上面这段代码没有毛病，但的确是有可优化之处的。
我们可以假设一种场景，比如 8 1 2 3 5 7,进行一次排序之后，结果就变成了 1 2 3 5 7 8,那我们还有必要再像上面代码里那样继续循环下去吗？肯定没有必要了，因为这已经是最终结果了。
那针对上面的代码，我们优化的点主要在于：假如某一趟排序之后已经有序，我们需要减少排序的趟数。否则就做了很多无用功。

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

济南达内

public void bubbleSort（int[] a） {
boolean exchange;
for（int i = a.length - 1; i > 0; i--） {
exchange = false;
for（int j = 0; j < i; j++） {
if（a[j] > a[j+1]） {
swap（a, j, j+1）；
exchange = true;
}
}
if（！exchange） return;
}
}
这样就优化完了，其实代码逻辑很简单，通过一个布尔变量即可监控一趟过程有没有进行数据交换。
冒泡排序最好的情况是初始状态是正序的，一次扫描即可完成排序，所以最好的时间复杂度为O（N）；最坏的情况是反序的，此时最坏的时间复杂度为O（N^2）。平均情况，每轮N/2次循环，N轮时间复杂度为O（N^2）。所以它并不是个好的排序算法。这个问题的讨论就到此结束，如果有更好的优化算法也欢迎留言讨论。
冒泡排序并不好，但为什么面试官还会去问？针对这件事情，我们需要注意什么呢？
1. 经典的东西，可能已经不用了，但是从经典的东西身上，我们能学到的还有很多，否则也不会成为经典。特别是那些面试经常被问到的，总有它存在的合理性。
2. 教科书上的东西不代表实战，所以很多时候考虑到非理想情况下，就可能不那么适用了。面试官往往更加注重的是在不适用的情况下，面试者是如何应对的。面试官更加看重的是面试者的思路。
3. 应届生不能浮躁，特别是在准备面试的时候，一定要步步为营，切忌好高骛远，浅尝辄止，多学习学习经典的数据结构和算法，多做做算法题还是很有必要的。
以上就是济南达内给大家做的内容详解，更多关于IT知识的学习，请继续关注济南达内

< 上一篇：我为什么要通过学C++去接触区块链？

下一篇：C++20 准备来了，看看都有哪些新特性？ >