口试必考算法题之冒泡排序 (优化脱坑版)！

近期许多童鞋在讨论大厂口试的算法题，有部门同砚表现一脸懵逼，不知从何动手，另有一部门同砚直接网上复制的。

好比网上复制冒泡排序算法，一不警惕就复制了一个伪冒泡排序。

写完了之背面试官问能优化嘛?

这个时间根本上都是一脸渺茫，不知道怎样优化。

那么接下来给各人来捋一捋冒泡排序的道理，只有搞懂排序的道理，才气更好的把握，写出真实的冒泡排序算法

1、一败涂地冒泡排序道理

冒泡排序的规则,归纳几点如下:

冒泡的规则：

◆ 每一轮获取第一个数和背面的数据举行依次比力的过程，称为一轮冒泡的过程

◆ 每一轮冒泡.都是先拿第一个数，依次比对相邻的两个数，假如前一个数比后一个数大，则互换他们的位置，这一轮比力完毕，会把最大的数放在最背面。

◆ 然后反复重复上面的步调（每一轮都能将前面数据中一个最大数，放到背面），直到一轮冒泡下来没有任何数据需交互位置,此时数据已为有序状态

冒泡的次数：

◆ 假设列表的长度为n，冒泡排序是每次拿出来第一个元素，必要拿多少次呢？

应当是列表的长度减1，意味着每一个长度为n的列表，必要冒泡 n-1 次

每次冒泡比力的次数：

◆ 第一次冒泡，必要举行依次比力的次数为n-次，每一次冒泡，都能排好一个数据的次序，那么随着次的增添排好的数据也会越多，必要比力的数据就越少。

关系图如下：

根据以上分析我们找出了冒泡次数和，比力次数的关系，接下来就可以通过代码来实现了，实当代码如下

二、Python实现冒泡排序

代码实现：

注重：上面的代码根据冒泡的思绪,实现了排序，但是从严酷意义上讲照旧由缺陷的，不能算是真实的冒泡排序，只是一个伪冒泡排序。

口试可以或许把这个伪冒泡排序写出来，大多数公司照旧能过的。

三、代码优化

尽人皆知，举行冒泡排序的时间，当一轮冒泡下来，全部数据的次序都没发生改变，那么该数据就是一个有序列表了，这个时间就不会在举行下一轮冒泡了。

比方：

当我们利用一个有序列表来举行冒泡排序，那么第一轮冒泡下来，全部的数据次序都不会发生改变。

那么就不会再举行下一轮冒泡，如许环境下时间复杂度为最优，只举行一轮冒泡，即O(n)。

1、缺陷分析

针对于时间复杂度最优的这类环境，在上面写的伪冒泡排序算法中是不大概出现的，不管被排序的数占有没有次序，都会举行n-1次冒泡，即最坏时间复杂度。

在这边上面的伪冒泡只思量了冒泡的过程，不管列表原来的次序，依次冒泡，全部去排一遍次序，没有从时间复杂度的角度去做优化。

2、代码优化

针对上述缺陷题目，接下来我们举行优化

代码如下：

代码表明：上述代码对之前的伪冒泡举行了优化，首要优化的点在于，我们每一次冒泡的时间，设置一个变量来记载，当前这次冒泡数据的次序是否有发生改变，初始值设为False,当数据属性发生改变时，就把这个值设为True。

一轮冒泡完毕后 再去判定，这个变量是否为False,假如为False则没有发生改变，即数占有序，那么接下来就可以直接返回数据，不必要再举行下一次冒泡。

提示：看完文章的小同伴，以背面试遇得手撕冒泡排序的时间不要再写伪冒泡啦！

本文由柠檬班木森老师原创，转载需注明出处！