乐趣区

关于javascript:使用vue实现排序算法演示动画

jiezi

缘起

最近做的一个小需要波及到排序，界面如下所示：

因为我的项目是应用 vue 的，所以实现形式很简略，视图局部不必管，实质上就是操作数组，代码如下：

{
    // 上移
    moveUp (i) {
        // 把地位 i 的元素移到 i - 1 上
      let tmp = this.form.replayList.splice(i, 1)
      this.form.replayList.splice(i - 1, 0, tmp[0])
    },

    // 下移
    moveDown (i) {
        // 把地位 i 的元素移到 i + 1 上
      let tmp = this.form.replayList.splice(i, 1)
      this.form.replayList.splice(i + 1, 0, tmp[0])
    }
}

这样就能够失常的替换地位了，然而是渐变的，没有动画，所以不显著，于是一个码农的自我涵养（实际上是太闲）让我关上了 vue 的网站，看到了这个示例：https://cn.vuejs.org/v2/guide/transitions.html#%E5%88%97%E8%A1%A8%E7%9A%84%E6%8E%92%E5%BA%8F%E8%BF%87%E6%B8%A1

这个示例我已看过多遍，然而始终没用过，这里刚好就是我要的成果，于是一通复制粘贴大法：

<template>
    <transition-group name="flip-list" tag="p">
        <!-- 循环生成列表局部，略 -->
    </transition-group>
</template>

<style>
.flip-list-move {transition: transform 0.5s;}
</style>

这样就有替换的过渡成果了，如下：

嗯，难受了很多，这个需要到这里就完了，然而事件并没有完结，我忽然想到了以前看一些算法文章的时候通常会配上一些演示的动画，感觉跟这个很相似，那么是不是能够用这个来实现呢，当然是能够的。

实现算法演示动画

先写一下根本的布局和款式：

<template>
  <div class="sortList">
      <transition-group name="flip-list" tag="p">
        <div
          class="item"
          v-for="item in list"
          :key="item.index"
          :style="{height: (item.value / max * 100) +'%'}"
        >
          <span class="value">{{item.value}}</span>
        </div>
      </transition-group>
    </div>
</template>

<style>
.flip-list-move {transition: transform 0.5s;}
</style>

list是要排序的数组，当然是通过解决的，在真正的源数组上加上了惟一的index，因为要能失常过渡的话列表的每一项须要一个惟一的 key：

const arr = [10, 43, 23, 65, 343, 75, 100, 34, 45, 3, 56, 22]

export default {data () {
    return {list: arr.map((item, index) => {
        return {
          index,
          value: item
        }
      })
    }
  }
}

max是这个数组中最大的值，用来按比例显示高度：

{
    computed: {max () {
            let max = 0
            arr.forEach(item => {if (item > max) {max = item}
            })
            return max
        }
  }
}

其余款式能够自行施展，显示成果如下：

简洁而不简略~，当初万事俱备，只欠让它动起来，排序算法有很多，然而自己比拟菜，所以就拿冒泡算法来举例，最最简略的冒泡排序算法如下：

{mounted(){this.bubbleSort()
    },
    methods: {bubbleSort() {
          let len = this.list.length

          for (let i = 0; i < len; i++) {for (let j = 0; j < len - i - 1; j++) {if (this.list[j] > this.list[j + 1]) {  // 相邻元素两两比照
                let tmp = this.list[j]        // 元素替换
                this.$set(this.list, j, this.list[j + 1])
                this.$set(this.list, j + 1, tmp)
              }
            }
          }
        }
    }
}

然而这样写它是不会动的，霎时就给你排好了：

试着加个延时：

{mounted () {setTimeout(() => {this.bubbleSort()
        }, 1000)
    }
}

刷新看成果：

有动画了，不过这种不是咱们要的，咱们要的应该是上面这样的才对：

所以来革新一下，因为 for 循环是只有开始执行就不会停的，所以须要把两个 for 循环改成两个函数，这样能够管制每个循环什么时候执行：

{bubbleSort () {
      let len = this.list.length
      let i = 0
      let j = 0
      // 内层循环
      let innerLoop = () => {
        // 每个内层循环都执行结束后再执行下一个外层循环
        if (j >= (len - 1 - i)) {
          j = 0
          i++
          outLoop()
          return false
        }
        if (this.list[j].value > this.list[j + 1].value) {let tmp = this.list[j]
          this.$set(this.list, j, this.list[j + 1])
          this.$set(this.list, j + 1, tmp)
        }
        // 动画是 500 毫秒，所以每隔 800 毫秒执行下一个内层循环
        setTimeout(() => {
          j++
          innerLoop()}, 800)
      }
      // 外层循环
      let outLoop = () => {if (i >= len) {return false}
        innerLoop()}
      outLoop()}
}

这样就实现了每一步的动画成果：

然而这样不太直观，因为有些相邻不必替换的时候啥动静也没有，不晓得以后具体排到了哪两个，所以须要突出以后正在比拟替换的两个元素，首先模板局部给以后正在比拟的元素加一个类名，用来高亮显示：

<div
     :class="{sortingHighlight: sorts.includes(item.index)}"
     >
    <span class="value">{{item.value}}</span>
</div>

js 局部定义一个数组 sorts 来装载以后正在比拟的两个元素的惟一的 index 值：

{data() {
        return {sorts: []
        }
    },
    methods: {bubbleSort () {
            // ...
            // 内层循环
            let innerLoop = () => {
                // 每个内层循环都执行结束后再执行下一个外层循环
                if (j >= (len - 1 - i)) {
                    // 清空数组
                    this.sorts = []
                    j = 0
                    i++
                    outLoop()
                    return false
                }
                // 将以后正在比拟的两个元素的 index 装到数组里
                this.sorts = [this.list[j].index, this.list[j + 1].index]
                // ...
            }
            // 外层循环
            // ...
        }
    }
}

批改后成果如下：

最初，再参考方才他人的示例把已排序的元素也加上高亮：

{data() {
        return {sorted: []
        }
    },
    methods: {bubbleSort () {
            // ...
            // 内层循环
            let innerLoop = () => {
                // 每个内层循环都执行结束后再执行下一个外层循环
                if (j >= (len - 1 - i)) {this.sorts = []
                    // 看这里，把排好的元素加到数组里就 ok 了
                    this.sorted.push(this.list[j].index)
                    j = 0
                    i++
                    outLoop()
                    return false
                }
                // ...
            }
            // 外层循环
            // ...
        }
    }
}

最终成果如下：

接下来看一下抉择排序，这是抉择排序的算法：

{selectSort() {for (let i = 0; i < len - 1; i++) {
            minIndex = i
            for (let j = i + 1; j < len; j++) {if (this.list[j].value < this.list[minIndex].value) {minIndex = j}
            }
            tmp = this.list[minIndex]
            this.$set(this.list, minIndex, this.list[i])
            this.$set(this.list, i, tmp)
        }
    }
}

抉择排序波及到一个以后最小元素，所以须要新增一个高亮：

<div
     :class="{minHighlight: min === item.index , sortingHighlight: sorts.includes(item.index), sortedHighlight: sorted.includes(item.index)}"
     >
    <span class="value">{{item.value}}</span>
</div>
{data () {
        return {min: 0}
    },
    methods: {selectSort () {
            let len = this.list.length
            let i = 0; let j = i + 1
            let minIndex, tmp
            // 内层循环
            let innerLoop = () => {if (j >= len) {
                    // 高亮最初要替换的两个元素
                    this.sorts = [this.list[i].index, this.list[minIndex].index]
                    // 延时是用来给高亮一点工夫
                    setTimeout(() => {
                        // 替换以后元素和比以后元素小的元素的地位
                        tmp = this.list[minIndex]
                        this.$set(this.list, minIndex, this.list[i])
                        this.$set(this.list, i, tmp)
                        this.sorted.push(this.list[i].index)
                        i++
                        j = i + 1
                        outLoop()}, 1000)
                    return false
                }
                // 高亮以后正在寻找中的元素
                this.sorts = [this.list[j].index]
                // 找到比以后元素小的元素
                if (this.list[j].value < this.list[minIndex].value) {
                    minIndex = j
                    this.min = this.list[j].index
                }
                setTimeout(() => {
                    j++
                    innerLoop()}, 800)
            }
            let outLoop = () => {if (i >= len - 1) {this.sorted.push(this.list[i].index)
                    return false
                }
                minIndex = i
                this.min = this.list[i].index
                innerLoop()}
            outLoop()}
    }
}

成果如下：

其余的排序也是同样的套路，将 for 循环或 while 循环改写成能够管制的函数模式，而后可能须要略微批改一下显示逻辑，如果你也有打算写排序文章的话当初就能够给本人加上动图展现了！

总结

之前看到这些动图的时候也有想过怎么实现，然而都没有深究，这次业务开发无心中也算找到了其中的一种实现形式，其实外围逻辑很简略，要害是很多时候没有想到能够这么做，这兴许是框架带给咱们的另一些益处吧。

退出移动版