因为之前面试有问到快排，昨天笔试又有做到关于排序算法的题，所以特地看了一下关于排序算法。前端对算法的要求不高，但是下面这几种易理解的排序算法还是要掌握。

简单介绍及实现

以下的排序均是升序。

冒泡排序

冒泡排序是最简单的排序，即比较前后两个数的大小。

function bubble(arr) {
  for(let i = 0, len = arr.length; i < len; i++) {
    for(let j = 0; j < len; j++) {
      if(arr[j] > arr[j + 1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  
  return arr;
}

选择排序

选择排序首先要选择一个最小值，拿这个最小值与后面未排序的数进行比较，比它更小则调换位置。

function selection(arr) {
  let min;
  for(let i = 0, len =arr.length; i < len; i++) {
    min = arr[i];
    for(let j = i+1; j < len; j++) {
      if(arr[j] < min) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  
  return arr;
}

插入排序

插入排序原理与打扑克时候把牌按顺序插入差不多：从第二张牌开始往前看，数字是否小于第二张牌，处理完以后从第三张牌看，以此类推，从第 n 张牌往前看 n 前面的牌是否小于第 n 个位置的牌。

function insert(arr) {
  for(let i = 1, len = arr.length; i < len; i++) {
    let target = arr[i];
    for(let j = i; j >=0; j--) {
      if(arr[j-1] > target) {
        arr[j] = arr[j-1];
      } else {
        arr[j] = target;
        break;
      }
    }
  }
  
  return arr;
}

希尔排序

希尔排序是在插入排序的基础上改进的，它会设定一个间隔，而不是每次只有 1 的距离，间隔由大到小，最后为1。

在《算法（第四版）》中 Robert Sedgewick 提出了动态定义间隔序列。（为了方便理解，这里没有动态定义）

function shell(arr) {
  let gaps = [5, 3, 1];
  
  gaps.forEach((gap) => {
    for(let i = gap, len = arr.length; i < len; i++) {
      let target = arr[i];
      for(let j = i; j >=0; j -= gap) {
        if(arr[j - gap] > target) {
          arr[j] = arr[j - gap];
        } else {
          arr[j] = target;
          break;
        }
      }
    }
  });
  
  return arr;
}

快速排序

快速排序就是选定一个基准，然后把大于这个基准的作为一边，小于这个基准的作为另一边，再把这两边以相同的规则处理。类似于二分法。

function quick(arr) {
  if(arr <= 1) {
    return arr;
  }
  // 假定基准 mid 为 arr 的第一个数
  var mid = arr.shift();
  var left = [];
  var right = [];

  arr.forEach((value) => {
    if(value <= mid) {
      left.push(value);
    } else {
      right.push(value);
    }
  });

  return quick(left).concat(mid, quick(right));
}

归并排序

这个我也不好解释，复制官方的说法：

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

下面是我找的一个比较形象的演示了归并排序的图：

这里是一个图片演示

function merge(arr) {
  var len = arr.length;
  if(len <= 1) {
    return arr;
  }
  var midIndex = Math.floor(len/2);
  var left = arr.slice(0, midIndex);
  var right = arr.slice(midIndex);
  
  return mergeSort(merge(left), merge(right));
}

function mergeSort(left, right) {
  var res = [];
  while(left.length && right.length) {
    if(left[0] < right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  
  while(left.length) {
    res.push(left.shift());
  }
  while(right.length) {
    res.push(right.shift());
  }
  
  return res;
}

各个排序算法复杂度及稳定性的比较

（目前还不能理解堆排序，有时间看完二叉树再研究一下堆排序会更新堆排序的内容。）

各类排序算法演示

点这里可以看各类排序算法演示

总结

前端要理解的算法虽然不多，但尽量多学习算法对一些代码优化有帮助，同时方便以后学习其他语言或者深入学习。