前端面试之排序和VUE死循环

Author Avatar
EmptinessBoy 5月 23, 2021
  • 在其它设备中阅读本文章

这周末出去兜了一波风,吹了吹海风。翻了翻朋友圈,感觉除了我以外的所有人周末都在学习😭

这不,大三就要结束了,内卷的风气已经在班上悄无声息的蔓延开了。面试的忙着找书记的实习,考研的忙着最后半年的冲刺,算下来我算是那个最“颓废”的人啦。

恰巧,最近同学面试的时候,被面试官问到了各种问题。这里就给大家简单的整理一波啦。(不定时更新

排序问题

排序问题可以说是程序设计里最基础的算法了。恰巧我一朋友在面试的时候就被问到了冒泡排序,结果可能是因为太紧张,一时大脑空白,就没写出来。

那么这里就整理下 JS 中排序的最简单的三种实现方式。这里我采用了 一个空白的 VUE 项目为大家进行演示(因为可以用 ES6 语法)。

模板代码:

<template>
  <div class="home">
    <p>list_origin:{{list0}}</p>
  </div>
</template>

<script>
export default {
  name: "Home",
  data() {
    return {
      list0: [3, 1, 4, 6, 8, 5],
      list1: [3, 1, 4, 6, 8, 5],
      list2: [3, 1, 4, 6, 8, 5],
    };
  },
};
</script>

自带排序方法

在上面发模板代码中,我新建了一个名为 list 的数组,里面随便放了一些数字,并通过模板绑定到我们的 HTML 中进行显示。

如果一切顺利,就会看到网页上显示了原始数组的内容:

image-20210522225529353

而对于 JavaScript 来说,使用其数组自带的排序方法无疑是最简单快捷的。

我们只需要在需要排序的数组对象后面使用自带的 sort() 即可将原数组进行从小到大的排序。而对于需要反向排序的数组,可以在使用完 sort() 方法后调用 reverse() 方法进行倒序处理。

这里我们修改示例代码的 mounted 部分,使得页面挂载后就调用 sort 和 reverse 方法对 list1 和 list2 进行排序:

mounted() {
  this.list1.sort();
  this.list2.sort().reverse();
},

然后修改上方 html 模板,将 list1 和 list2 进行展示:

<template>
  <div class="home">
    <p>list_origin:{{ list0 }}</p>
    <p>array_sort_method:{{ list1 }}</p>
    <p>array_sort_reverse:{{ list2 }}</p>
  </div>
</template>

以上代码在运行后,可以看到 list1 和 list2 已经完成了排序:

image-20210522232912916

冒泡排序 JS实现

那么如果不使用 JS 自带的函数,如何使用传统的冒泡排序方法对数组进行排序呢?

这里偷一张冒泡排序的原理图(来源菜鸟教程)

img

  1. 从原理图我们可以看到,冒泡排序的实质是按顺序依次比较相邻的两个数,如果发现左侧的大于右侧,就将这两个数交换顺序。
  2. 如此一轮交换下来后,整个序列的最后一位就一定是整个数组中最大的那个数。那么下一次循环的时候,我们就用同样的方式找到倒数第二大的数。
  3. 这样的过程一共重复 n-1 次,就完成了整个排序过程。

那么用 JS 应该怎么实现呢?其实很简单,我们只需要用两层 for 循环嵌套即可:

methods: {
  bubbleSort(list) {
    for (let i = 0; i < list.length - 1; i++) {
      for (let j = 0; j < list.length - i - 1; j++) {
        if (list[j] > list[j + 1]) {
          let temp = list[j];
          list[j] = list[j + 1];
          list[j + 1] = temp;
        }
      }
    }
    return list;
  },
},

如果使用 es6 的解构赋值,则内层 for 循环的两个变量的交换还可以写的更简单:

methods: {
  bubbleSort(list) {
    for (let i = 0; i < list.length - 1; i++) {
      for (let j = 0; j < list.length - i - 1; j++) {
        if (list[j] > list[j + 1]) {
          //  借用数组解构赋值
          [list[j], list[j + 1]] = [list[j + 1], list[j]];
        }
      }
    }
    return list;
  },
},

然后我们修改 html 模板,调用刚才写的排序方法:

<template>
  <div class="home">
    <p>list_origin:{{ list0 }}</p>
    <p>array_sort_method:{{ list1 }}</p>
    <p>array_sort_reverse:{{ list2 }}</p>
    <p>bubble_sort:{{ this.bubbleSort(list0) }}</p>
  </div>
</template>

运行后,我们可以在网页中看到,我们使用冒泡排序函数成功将数组从小到大进行了排列:

image-20210523002355390

选择排序 JS实现

如果你能够理解冒泡排序的原理,那么相信选择排序对你来说一定不难理解。

继续从菜鸟教程偷一张动图:

img

不难从图中看出,选择排序的原理就是依次遍历数组,从中找到最小的那个数,把它排到数组的第一位。然后从第二位开始继续以同样的方式寻找除去第一位以外最小的数放在第二位。

同样,选择排序的 JS 实现也需要使用两层 for 循环的嵌套使用:

methods: {
  selectionSort(list) {
    for (let i = 0; i < list.length; i++) {
      for (let j = i + 1; j < list.length; j++) {
        if (list[i] > list[j]) {
          //  解构赋值
          [list[i], list[j]] = [list[j], list[i]];
        }
      }
    }
    return list;
  },
},

这里,我们再修改下 html 模板:

<template>
  <div class="home">
    <p>list_origin:{{ list0 }}</p>
    <p>array_sort_method:{{ list1 }}</p>
    <p>array_sort_reverse:{{ list2 }}</p>
    <p>bubble_sort:{{ this.bubbleSort(list0) }}</p>
    <p>selection_sort:{{ this.selectionSort(list0) }}</p>
  </div>
</template>

可以在浏览器看到选择排序的结果也已经正确显示了:

image-20210523115030134

VUE 死循环

这里会有好奇的小伙伴发现了我在上面的例子中将 array 对象的 sort() 和 reverse() 方法放在 vue 生命周期的 mounted 阶段进行调用,那么为什么 JS 的 sort() 和 reverse() 方法不能放在 html 模板里呢?像下面这样:

<p>array_sort_method:{{ list1.sort() }}</p>
<p>array_sort_reverse:{{ list2.sort().reverse() }}</p>

这里咱们不讨论原因,先看下结果,如果在 html 模板语法里直接使用了 array 对象的内置方法会怎么样呢?

image-20210523115819222

可以看到,虽然浏览器显示的页面里输出了正确的排序结果,但是控制台出现了报错,发生了死循环问题。那么这个问题究竟是怎么产生的呢?

其实如果通俗易懂的来说的话,可以解释为:因为 sort 方法操作的是源对象本身,也就是直接修改了 list1 和 list2 的值。而 vue 中 html 模板在对数据进行绑定的同时有对数据的监听。

也就是说,因为 html 模板里的 sort 方法修改了 list 的值,而 list 的值改变又使得 html 模板中监听的 list 发生变化,使得 vue 重新调用了 sort 方法对当前的 list 再次排序。而再次排序又改变了绑定的 list 的值,使得 vue 重新调用了 sort 方法对当前的 list 再次排序。而再次排序又改变了绑定的 list 的值,使得 vue 重新调用了 sort 方法对当前的 list 再次排序。而再次排序又改变了绑定的 list 的值,使得 vue 重新调用了 sort 方法对当前的 list 再次排序。……

img

那么到这里你就能理解为什么将这些方法放到生命周期里了吧?如果小伙伴对 vue 生命周期还不熟的话,可以看我之前的文章哦!

传送门:VUE的生命周期是啥?

尾图4

This blog is under a CC BY-NC-ND 4.0 Unported License
本文链接:https://coding.emptinessboy.com/2021/05/%E5%89%8D%E7%AB%AF%E9%9D%A2%E8%AF%95%E4%B9%8B%E6%8E%92%E5%BA%8F%E5%92%8CVUE%E6%AD%BB%E5%BE%AA%E7%8E%AF/