排序动画

这是一段尘封了有十好几年的代码，那时候写前端的都还在被 IE6 折磨，没有 ES6 的新语法。

经过了这么多年的沉寂，这段古旧的代码依然还能够运行，着实算是意料之中 😎。放这里算做个纪念吧。

我当时写了四种排序算法的动画，每个算法都用相同的 5 组不同性质的数据（已排序、少量乱序、逆序、乱序、大量重复）。直接看效果：

说明一下：

1. 红色小三角：当前正在处理的元素指示（快速排序有两个）
2. 灰色线条：未挪动过位置的元素
3. 黑色线条：挪动过位置的元素
4. 双击某个图形可以重新开始对应的动画

从效果上，可以很明显地看出这四种排序算法的速度：快速排序 > 选择排序 > 插入排序 > 冒泡排序。

代码实现

写过排序的算法的一般都知道，排序其实就是一顿循环，循环无非就是 for 或 while 这些，在没有 async-await 之前，只能是一个同步的过程。

根据视觉停留的时间原理，而要让排序以动画的形式能够展现，就需要让每个循环的消耗一定的时间，50~150ms 左右。

要做到这件事情，所能想到的就是把同步循环转成异步，当年的做法就是利用 setTimeout + 递归的方法（当时还写过一篇博客，但已经不可考了）。

以下所有代码，我都基本保留之前的原汁原味，不做过多的更新，所以没有用到新的 JS 特性，而且，当时我还不会 TS，因此这里所有的代码都是纯 ES5 JS。

公用逻辑

var COMPARE_TIME = 5,
    MOVE_TIME = 50;

/**
 * Used by all sorting algorithms to swap two entries in the array.
 * @param {Array} arr
 * @param {Number} i
 * @param {Number} j
 */
function _swap(arr, i, j) {
  var tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

/**
 * Used to do setTimeout.
 * @param {Function} fn
 * @param {Number} ms
 */
function _delay(fn, ms) {
  if (ms > 0) {
    setTimeout(fn, ms);
  } else {
    fn();
  }
}

快速排序

function quickSort(arr) {
  function quick(l, r) { // l for left, r for right
    if (l >= r) {
      return;
    }
    
    var pivot = arr[l], // the first of the sub-list as the pivot
        i = l + 1,
        j = r;
    
    while (true) {
      while (i < r && arr[i] <= pivot) {
        i++;
      }
      
      while (j > l && arr[j] >= pivot) {
        j--;
      }
      
      if (i < j) {
        _swap(arr, i, j);
      } else {
        _swap(arr, l, j);
        break;
      }
    }
    
    quick(l, j - 1);
    quick(j + 1, r);
  }
  
  quick(0, arr.length - 1);
}

快速排序（递归版）

function quickSortRecursive(arr) {
  var recursiveStack = [],
      n = arr.length - 1,
      pivot, i, j, l, r, needCmp;
  
  function loopJ() {
    needCmp = j > l;
    
    if (needCmp && arr[j] >= pivot) {
      j--;
      _delay(loopJ, COMPARE_TIME);
    } else {
      if (i < j) {
        _swap(arr, i, j);
        _delay(loop, needCmp ? COMPARE_TIME + MOVE_TIME : MOVE_TIME);
      } else {
        _swap(arr, l, j);
        
        recursiveStack.push({
          l: j + 1,
          r: r
        });
        _delay(function() {
          quick(l, j - 1);
        }, needCmp ? COMPARE_TIME + MOVE_TIME : MOVE_TIME);
      }
    }
  }
  
  function loopI() {
    needCmp = i < r;
    if (needCmp && arr[i] <= pivot) {
      i++;
      _delay(loopI, COMPARE_TIME);
    } else {
      _delay(loopJ, needCmp ? COMPARE_TIME : 0);
    }
  }
  
  function loop() {
    loopI();
  }
  
  function quick(_l, _r) {// l for left, r for right
    l = _l;
    r = _r;
    
    if (l >= r) {
      var o = recursiveStack.pop();
      if (o) {
        quick(o.l, o.r);
      } // else - end of loop
      
      return;
    }
    
    pivot = arr[l];// the first of the sub-list as the pivot
    i = l + 1;
    j = r;
    
    loop();
  }
  
  quick(0, n);
}

选择排序

function selectionSort(arr) {
  var n = arr.length,
      i, j, min, minIdx;
  
  for (i = 0; i < n - 1; i++) {
    min = arr[i];
    minIdx = i;
    for (j = i + 1; j < n; j++) {
      if (arr[j] < min) {
        min = arr[j];
        minIdx = j;
      }
    }
    
    _swap(arr, i, minIdx);
  }
  
  console.info(arr);
}

选择排序（递归版）

function selectionSortRecursive(arr) {
  var n = arr.length,
      i = 0, j, min, minIdx;
  
  function loopInner() {
    if (j < n) {
      if (arr[j] < min) {// compare
        min = arr[j];
        minIdx = j;
      }
      j++;
      _delay(loopInner, COMPARE_TIME);
    } else {
      _swap(arr, i, minIdx);// move
      i++;
      _delay(loop, MOVE_TIME);
    }
  }
  
  function loop() {
    if (i < n - 1) {
      min = arr[i];
      minIdx = i;
      j = i + 1;
      loopInner();
    } // else - end of sort
  }
  
  loop();
}

插入排序

function insertionSort(arr) {
  var n = arr.length,
      i, j;
  
  for (i = 1; i < n; i++) {
    for (j = i; j >= 0 && arr[j] < arr[j - 1]; j--) {
      _swap(arr, j - 1, j);
    }
  }
}

插入排序（递归版）

function insertionSort_noloop(arr) {
  var n = arr.length,
      i = 1, j;
  
  function loopInner() {
    if (j >= 0) {
      if (arr[j] < arr[j - 1]) {// compare
        _swap(arr, j - 1, j);
        j--;
        _delay(loopInner, COMPARE_TIME + MOVE_TIME);
      } else {
        i++;
        _delay(loop, COMPARE_TIME);
      }
    } else {
      i++;
      loop();
    }
  }
  
  function loop() {
    if (i < n) {
      j = i;
      loopInner();
    } // else - end of loop
  }
  
  loop();
}

冒泡排序

function bubbleSort(arr) {
  var n = arr.length,
      i, j;
  
  for (i = n - 1; i >= 0; i--) {
    for (j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        _swap(arr, j, j + 1);
      }
    }
  }
}

冒泡排序（递归版）

function bubbleSortRecursive(arr) {
  var n = arr.length,
      i = n - 1, j;
  
  function loopInner() {
    if (j < i) {
      var needMove = arr[j] > arr[j + 1];// compare
      if (needMove) {
        _swap(arr, j, j + 1);// move
      }
      j++;
      _delay(loopInner, needMove ? COMPARE_TIME + MOVE_TIME : COMPARE_TIME);
    } else {
      i--;
      loop();
    }
  }
  
  function loop() {
    if (i >= 0) {
      j = 0;
      loopInner();
    } // else - end of sort
  }
  
  loop();
}

重新思考

如果现在去写，会怎么写？

是的，这些年前端的基础已经发生了天翻地覆的变化，个人在编程风格和技巧上，也有了一些变化。

如果现在去写的话，除了会用 TS 之外，我会考虑以下点：

1. 用 await 代替迭代，或者考虑用 Generator（我会更倾向于后者）
2. 增加更多输出，比如耗时、总循环数、比较次数、交换次数等
3. 增加更多配置，比如速度、数组大小等

有时间的话..