前端要掌握的几种排序算法

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

简单介绍及实现

以下的排序均是升序。

冒泡排序

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

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;
}

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

算法类型	平均时间复杂度	最坏时间复杂度	最佳时间复杂度	空间复杂度	稳定性
冒泡排序	O(n2)	O(n2)	O(n)	O(1)	稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
插入排序	O(n2)	O(n2)	O(n)	O(1)	稳定
希尔排序	O(nlogn)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
快速排序	O(nlogn)	O(n2)	O(nlogn)	O(logn)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定

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

各类排序算法演示

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

总结

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