通过代码实现展示冒泡算法的动画

偶然看到一道面试题，大概是这样问的：

怎么用 css 画一堆柱子，快排怎么写，那结合起来，通过柱子描述下快排的过程。

当时看到这题感觉确实是有点爆击，还有这样的操作？

不过还是稍微思考了一下

画柱子简单，主要是要通过柱子，把数组展示出来
另外就是排序算法了，要展示过程，那当然就是要获取排序每一步的结果，但是在这里碰到了个问题，因为我们熟悉的快排，是递归实现的，递归是将问题拆成子问题，那么如果要获取每一步的结果，这里每一次都不是完整的数组，所以要获取完整的步骤结果，就不太好办了，暂时没有想到怎么搞，就先拿冒泡来练练手了

核心代码如下，react 实现

上面仅仅是自己想到的方式，在我自己15年的 Mac 上跑起来之后，风扇还是响个不停，因为也算是频繁操作 dom 了，所以应该不是特别理想的方式，后续查了一下一些专门做这种算法动画的网站（链接见文末），稍微看了下人家是用 svg 来做的，性能相对来说，好很多，而且动画的流畅性可订制程度也比普通切换整个数组的高很多但在 svg 方面自己还是比较薄弱，先留个坑后续自己来深入学习一下

通过动画演示，可以比较明显地看得出有些地方可以优化的，这里主要说两点

1. 假如本次没有任何交换，则认为是完全排序完成

因为遍历的时候，都是遍历没有排序好的元素，假如这些没有排序过的，也不需要交换位置，那么就可以认为全都是排好序的了。

function bubleSortII(arr) {
  const len = arr.length
  let isSwap = false
  for(let i = 0; i < len; i++) {
    isSwap = false
    for(let j = 0; j < len - i; j++) {
      if(arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        isSwap = true
      }
    }
    if(!isSwap) return
  }
}

2. 记录本轮最后一次交换元素的下标，下次遍历到此下标节点即可

这个优化比上面的优化更细化了一步，每一轮排序，都有可能部分是排好序的，同时这种可能是出现在本轮排序的最后面，也就是本轮结束之前，到最后一次交换位置的这一段，是不需要排序的，所以下轮遍历的终点，可以设定在本轮最后一次交换的位置上。

function bubleSortIII(arr) {
  const len = arr.length
  let isSwap = false
  let lastSwapIndex = len - 1
  let sortedIndex = 0
  for(let i = 0; i < lastSwapIndex;) {
    isSwap = false
    sortedIndex = lastSwapIndex
    for(let j = 0; j < sortedIndex; j++) {
      if(arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        isSwap = true
        lastSwapIndex = j
      }
    }
    if(!isSwap) return
  }
}

参考： visualgo

liangbus / blogging

通过代码实现展示冒泡算法的动画 #23

1. 假如本次没有任何交换，则认为是完全排序完成

2. 记录本轮最后一次交换元素的下标，下次遍历到此下标节点即可