如何给面试官写一个满意的冒泡排序

谁践踏了优雅 2023-06-06 12:30 4阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 小鹿

来源 | 一个不甘平凡的码农

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

记得之前一个读者和小鹿说去面试的时候，面试官让写一个冒泡排序，也写出来了，最后去没有通过面试。其实他的冒泡排序没有进行优化的，这也不是重点。

在学数据结构和算法我有一个重大的发现，也包括我自己前期刚接触数据结构，对于一些排序算法都是去背加理解，但是这个理解呢，如果没有很深刻的理解，在手写代码的时候容易乱，所以呢，要想快速、正确、给面试官一个满意的冒泡排序，就跟着小鹿学起来吧。

**什么是冒泡排序？**

冒泡排序，顾名思义，那就是冒泡呗。我们最先想到的是鱼在水里的冒泡的过程。“没见过鱼！”，好吧，那就让你见识一下鱼吐泡泡，哈哈！

![640?wx\_fmt=png][640_wx_fmt_png]

我们可以在图中可以发现，鱼吐的泡泡离水面越近，他的泡泡就会越大，其实我们的冒泡排序和鱼吐泡泡的原理是一模一样子的。

**设计一个冒泡排序**

如果你是设计冒泡排序的人，你打算怎么根据鱼吐泡泡的原理去设计呢？那今天我们就假设自己是设计冒泡排序的人，如何设计一个冒泡排序？

我们在鱼吐泡泡中发现的规律是，每次冒泡最大的会在最上边（离进水面），所以我们也要使得一组数据的最大值放在最上方。所给的原始数据如下：

![640?wx\_fmt=png][640_wx_fmt_png 1]

为了我们好理解，我们把数组竖起来。

![640?wx\_fmt=png][640_wx_fmt_png 2]

基本的目标我们确认了，就是让最大的数字放在数组的最尾部（我们可以想象把数组立起来，尾部在上，数组头部在下）。既然最大的放在上边，那怎么在一组数据中寻找最大值，然后放到最顶端。上边的数据就会变成下边这个样子（8位于最上边）：

![640?wx\_fmt=png][640_wx_fmt_png 3]

如果我们从底部开始，前两个数据作对比，如果上边的数据大于下边的数据，就用这个上边的数字去和它上边的数字比较大小。如果下边的数字大于上边的数字，那我们就将这两个数字交换位置。以此类推，这样一组下来之后，这组数据的最大值就跑到了最上方（数组尾部），这个过程是怎么样子的呢？如下动画：

![640?wx\_fmt=gif][640_wx_fmt_gif]

闪烁代表比较，放大为两个数最大值

每寻找一次最大值，就要从剩余的数据中寻找最大值依次放置到顶部。

我们看到上方的一组冒泡下来之后，8位于最上方了，然后将剩余的数据再进行冒泡，同样的冒泡过程。

假设 n 个数据，当冒泡 n - 1 次之后，所有的数据就已经排序完成了。

**冒泡排序优化**

我们会发现我们设计的冒泡排序中存在一个问题就是，如果这组数据已经是排好序的，如果我们还在上边所说的一样，每个数据都要进行一次冒泡，此时的性能效率会非常低下，所以我们对设计的冒泡排序进行一次优化。

如何优化呢？我们可以加一个判断，如果我们第一组数据冒泡的过程中没有数据交换，此时数据已经是有序的了，然后直接返回在这组数据就可以了，没必要再向下继续冒泡。

**手写冒泡排序**

1/**
     2 * 时间:2019/3/14 
     3 * 功能:冒泡排序
     4 * @param a:数组
     5 * @param n:数组的大小
     6 * 边界条件:
     7 * 1) 判断数组是否有数据
     8 * 算法思路:
     9 * 1)外循环 for 需要 n 个数据 n 次冒泡
    10 * 2)内循环每次冒泡的比较次数，每冒泡比较次数都 -1
    11 * 3)冒泡优化
    12 */
    13var flag = false;
    14const bubblesort = (a) =>{
    15    if(a.length < 1) return;
    16    for(let i = 0;i < a.length;i++){
    17        for(let j = 0;j < a.length-1-i;j++){
    18            if(a[j]>=a[j+1]){
    19                let temp = a[j];
    20                a[j] = a[j+1];
    21                a[j+1] = temp;
    22                flag = true;
    23            }
    24        }
    25        if(!flag){
    26            break;
    27        }
    28    }
    29}

**冒泡排序性能**

对于冒泡排序的性能的话，分析性能我么你主要从两方面入手，第一个是时间复杂度，另一个是空间复杂度。

**5.1时间复杂度**

在时间复杂度上，我们看效率，我们如果一次数据查找最大值的过程是需要交换 n - 1 次， n 个数据，需要进行 n - 1 次冒泡过程。所以时间复杂度为 （n-1）² = n² - 2n + 1 ，省略掉系数和低阶，所以时间复杂度为 O(n²)。

我们还有一种情况就是数据已经是排好序了，所以冒泡一次就可以了，时间复杂度是 O(n)。这是最好时间复杂度，但是总的来说，这种情况非常少，所以呢，冒泡排序的时间平均时间复杂度为 O(n²)。

**5.2 空间复杂度**

空间复杂度我们重点看什么？空间复杂度我们主要看额外利用的空间，比如我们在冒泡的过程中，涉及到数据交换，交换时需要申请临时的空间，它是常量级别的，其他不需开辟要额外的内存空间，所以空间复杂度为 O(1)。

**小结**

今天我们主要分享了冒泡排序，它是什么，而且我们通过鱼吐泡泡的原理，自己设计了一下冒泡排序，加深了对冒泡排序的整个过程的理解。然后我们也分解了手写冒牌排序的过程，还有冒泡的优化，让我们在面试中给面试官一个满意的冒泡排序。

通常在面试中，冒泡排序最主要的是不但写出主要过程，还要考虑到冒泡排序的优化过程，很多的应聘者往往会忽略这一点，你一定不要忘记哦！

![640?][640]

**有热门推荐?**

1.【程序员】

2.【GitHub】

3.【算法】

4.【数据结构】

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20230601/62115938b82c49b3980b106bd6a1ffa6.png
[640_wx_fmt_png]: /images/20230601/9a7bd94b81a94aa192a7ec38b37788a7.png
[640_wx_fmt_png 1]: /images/20230601/5b9e29fa0dcb4d56a646fb7843c55141.png
[640_wx_fmt_png 2]: /images/20230601/bdd99b25246c447db345a6d082862c80.png
[640_wx_fmt_png 3]: /images/20230601/ddc37b12a5b84db593fb60700ec6da91.png
[640_wx_fmt_gif]: /images/20230601/c023aeb881bf4d4c94023b16a422c623.png
[640]: /images/20230601/bca8e55676f440a5bb0a4e277c2abc23.png
[640_wx_fmt_jpeg 1]: /images/20230601/aa4795d8c9ac413d83a9e5eee0279bbb.png