「金三银四」| 手撕排序算法（JavaScript 实现）（上）

俗话说金三银四 金九银十，马上又到了求职跳槽的黄金季。但是今年的这种大环境下，前端岗位的竞争势必比往日更加激烈。

在如今的面试过程中，算法是常常被考察的知识点，而 排序 作为算法中比较基础的部分，被面试官要求当场手写几种 排序算法 也不算是过分的要求。

所以最近将十种常见的排序算法整理如下，并附上一些常见的优化方法以及一些对应的leetcode(传送门) 题目，建议大家可以申请个账号刷起来，毕竟看明白了跟能够写出来并且通过LeetCode所有的 case 是两码事:joy:，希望可以对刚接触算法以及最近需要参加面试的小伙伴有一点帮助。

毕竟手里有粮 心里不慌（逃~

• 本篇将主要讲解以下十个经典排序算法：
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 堆排序
  • 快速排序
  • 桶排序
  • 基数排序
  • 希尔排序
  • 计数排序

想看源码 戳这里 ，读者可以 Clone 下来本地跑一下。BTW，文章配合源码体验更棒哦~~~

最后，限于个人能力，如过在阅读过程中遇到问题或有更好的优化方法，可以：

• 提issue给我
• 或是pull requests
• 在本篇下评论

我都会看到并处理，欢迎Star，点赞，您的支持是我写作最大的动力。

准备

• 排序算法的稳定性：排序前后两个相等的数相对位置不变，则算法稳定。

• 时间复杂度:简单的理解为一个算法执行所耗费的时间，一般使用 大O符号表示法 ，详细解释见时间复杂度

• 空间复杂度:运行完一个程序所需内存的大小。

常见算法的复杂度（ 图片来源于网络 ）

以下算法最频繁的操作就是交换数组中两个元素的位置（按照正序或者是逆序），简单抽出一个函数如下：

/**
 * 按照正序比较并交换数组中的两项
 *
 * @param {Array} ary
 * @param {*} x
 * @param {*} y
 */
function swap(ary, x, y) {
  if (x === y) return
  var temp = ary[x]
  ary[x] = ary[y]
  ary[y] = temp
}
复制代码

冒泡排序（Bubble-Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤：假设我们最终需要的是依次递增的有序数组

1. 从数组的第一位开始，依次向后比较相邻元素的大小，如果前一个比后一个小，那么交换二者位置，直至数组末尾。
2. 下一轮比较的起始位置加1，然后重复第一步。
3. 重复1~2，直至排序结束。

function bubbleSort1(ary) {
  var l = ary.length
  for (var i = 0; i < l; i++) {
    for (var j = 0; j < l; j++) {
      if (ary[j] > ary[j + 1]) {
        swap(ary, j, j + 1)
      }
    }
  }
  return ary
}

复制代码

优化： 上述排序对于一个长度为 n 的数组排序需要进行 n * n 次排序。（内外两层循环次数都是 n ） 可以预见到的是，每进行一轮冒泡，从数组末尾起有序部分长度就会加一，这就意味着数组末尾的有序数组进行比较的操作是无用的。

改进后的算法如下：

function bubbleSort2(ary) {
  var l = ary.length
  for (var i = l - 1; i >= 0; i--) {
    // 优化的部分 arr[i]及之后的部分都是有序的
    for (var j = 0; j < i; j++) {
      if (ary[j] > ary[j + 1]) {
        swap(ary, j, j + 1)
      }
    }
  }
  return ary
}
复制代码

优化点：对于一些比较极限情况的处理，举一个比较极限的例子，假如给定的数组已经是有序数组了，那么 bubbleSort1 和 bubbleSort2 还是傻傻的去走完预定的次数 分别为 n*n 和 n!。 当然这种情况并不容易遇到，但是在排序的后段部分很容易遇到的是，理论上应该是未排序的部分其实已经是有序的了，我们需要对这种情况进行甄别并处理。 引入一个 swapedFlag ，如果在排序的上一步没有进入内层循环，那么表明剩余元素都是有序的，排序完成。

优化后的代码如下：

/**
 * 冒泡排序 优化
 *
 * @param {Array} ary
 * @returns
 */
function bubbleSort3(ary) {
  var l = ary.length
  var swapedFlag
  for (var i = l - 1; i >= 0; i--) {
    swapedFlag = false
    for (var j = 0; j < i; j++) {
      if (ary[j] > ary[j + 1]) {
        swapedFlag = true
        swap(ary, j, j + 1)
      }
    }
    if (!swapedFlag) {
      break
    }
  }
  return ary
}
复制代码

选择排序（Selection-Sort）

选择排序是先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。 复杂度分析 ：很显然，选择排序也是一个费时的排序算法，无论什么数据，都需要O(n*n) 的时间复杂度，不适宜大量数据的排序。

算法步骤：初始状态为n的无序区（数组）可经过n-1趟直接选择排序得到有序结果

1. 初始状态：无序区为R[0..n]，有序区为空；
2. 第i趟排序(i=0,1,2,3…n-1)开始时，当前有序区和无序区分别为R[0..i]和R(i+1..n）。该趟排序从当前无序区中选出关键字最小的记录的位置(下标 minPos)，将 R[minPos] 与无序区的第1个记录 R[i] 交换，所以有序区长度加 1 无序区长度减 1 。然后进行 i 加 1 并进行下一趟排序。
3. n-1趟结束，数组排序完成

function selectSort(ary) {
  var l = ary.length
  var minPos
  for (var i = 0; i < l - 1; i++) {
    minPos = i
    for (var j = i + 1; j < l; j++) {
      if (ary[j] - ary[minPos] < 0) {
        minPos = j
      }
    }
    swap(ary, i, minPos)
  }
  return ary
}
复制代码

插入排序（Insertion-Sort）

插入排序是先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；然后从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，直到所有数据都完成排序；如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

注：动图对应的是最为原始的插入排序，没有在网上找到二分法对应的动图，大家见谅。

算法步骤：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤 2~5

function insertionSort1(arr) {
    var l = arr.length;
    var preIndex, current;
    for (var i = 1; i < l; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
复制代码

优化思路：

• 二分法：即在将新增的数值插入到有序数组中时，通过二分法减少查找次数。
• 链表：将有序数组部分转为链表结构，那么插入的时间复杂度变为O(1),查找复杂度变为O(n)（因为不方便使用二分法）
• 排序二叉树（BST）： 将有序数组部分转化为排序二叉树结构，然后中序遍历该二叉树。利用排序二叉树可以兼顾插入方便以及查找的效率。但是需要占用额外空间。所以 BST 是比较平衡的一种思路， 也是空间换时间思路的体现。

简单介绍下二分法：二分查找法，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

注：准备面试的同学能够理解并记忆以下一种即可，排序二叉树和链表的实现限于篇幅就不细说，准备以后写数据结构时再详细介绍,本篇介绍下使用二分法优化拆入排序的思路：

/**
 * 插入排序
 *
 * @param {*} ary
 * @returns {Arrray} 排序完成的数组
 */
function insertSort2(ary) {
  return ary.reduce(insert, [])
}

/**
 * 使用二分法完成查找插值位置，并完成插值操作。
 * 时间复杂度 logN
 * @param {*} sortAry 有序数组部分
 * @param {*} val
 * @returns
 */
function insert(sortAry, val) {
  var l = sortAry.length
  if (l == 0) {
    sortAry.push(val)
    return sortAry
  }

  var i = 0,
    j = l,
    mid
  //先判断是否为极端值
  if (val < sortAry[i]) {
    return sortAry.unshift(val), sortAry
  }
  if (val >= sortAry[l - 1]) {
    return sortAry.push(val), sortAry
  }

  while (i < j) {
    mid = ((j + i) / 2) | 0
    //结束条件 等价于j - i ==1
    if (i == mid) {
      break
    }
    if (val < sortAry[mid]) {
      j = mid
    }
    if (val == sortAry[mid]) {
      i = mid
      break
    }
    //结束条件 统一c处理对外输出i
    if (val > sortAry[mid]) {
      i = mid
    }
  }
  var midArray = [val]
  var lastArray = sortAry.slice(i + 1)
  sortAry = sortAry
    .slice(0, i + 1)
    .concat(midArray)
    .concat(lastArray)
  return sortAry
}
复制代码

归并排序（Merge-Sort）

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

稳定性分析：归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法.

算法步骤：

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

// 采用自上而下的递归方法
function mergeSort(ary) {
  if (ary.length < 2) {
    return ary.slice()
  }

  var mid = Math.floor(ary.length / 2)
  var left = mergeSort(ary.slice(0, mid))
  var right = mergeSort(ary.slice(mid))
  var result = []

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }

  result.push(...left, ...right)

  return result
}
复制代码

堆排序（Heapsort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积结构具有如下特点：即子结点的键值总是小于（或者大于）它的父节点，据此可分为以下两类：

• 最大堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
• 最小堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤：

1. 创建一个堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，并调用 reheap 方法重新聚堆，目的是把新的数组顶端数据调整到相应位置，重新变为最大堆。

/**
 * 聚堆：将数组中的某一项作为堆顶，调整为最大堆。
 * 把在堆顶位置的一个可能不是堆，但左右子树都是堆的树调整成堆。
 *
 * @param {*} ary 待排序数组
 * @param {*} topIndex 当前处理的堆的堆顶
 * @param {*} [endIndex=ary.length - 1] 数组的末尾边界
 */
function reheap(ary, topIndex, endIndex = ary.length - 1) {
  if (topIndex > endIndex) {
    return
  }

  var largestIndex = topIndex
  var leftIndex = topIndex * 2 + 1
  var rightIndex = topIndex * 2 + 2

  if (leftIndex <= endIndex && ary[leftIndex] > ary[largestIndex]) {
    largestIndex = leftIndex
  }
  if (rightIndex <= endIndex && ary[rightIndex] > ary[largestIndex]) {
    largestIndex = rightIndex
  }

  if (largestIndex != topIndex) {
    swap(ary, largestIndex, topIndex)
    reheap(ary, largestIndex, endIndex)
  }
}

/**
 * 将数组调整为最大堆结构
 *
 * @param {*} ary
 * @returns
 */
function heapify(ary) {
  for (var i = ary.length - 1; i >= 0; i--) {
    reheap(ary, i)
  }
  return ary
}

/**
 * 堆排序
 *
 * @param {*} ary
 * @returns
 */
function heapSort(ary) {
  heapify(ary)
  for (var i = ary.length - 1; i >= 1; i--) {
    swap(ary, 0, i)
    reheap(ary, 0, i - 1)
  }
  return ary
}
复制代码

快速排序（Quicksort）

快速排序使用分治法策略来把一个数组分为两个子数组。首先从数组中挑出一个元素，并将这个元素称为「基准」，英文pivot。重新排序数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数组的中间位置。这个称为分区（partition）操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。

注意: 在 js 中实现快排中最耗费时间的就是交换，本例子中哨兵的元素是随机取得的，而上面动图中总是的取数组中的第一个值作为哨兵（pivot），那么考虑一种极限情况，在 [9,8,7,6,5,4,3,2,1] 重中例子中使用就地排序就算法复杂度就会变成 n*n。 本例中的哨兵是从数组中随机抽取的，个人认为比取首元素的方案更优。

应用：取前K大元素、求中位数 、leetcode

嗯，先整一个粗暴版本稍微了解下快排的基本思路：

//快排粗暴版本
function quickSort1(ary) {
  if (ary.length < 2) {
    return ary.slice()
  }
  var pivot = ary[Math.floor(Math.random() * ary.length)]
  var left = []
  var middle = []
  var right = []
  for (var i = 0; i < ary.length; i++) {
    var val = ary[i]
    if (val < pivot) {
      left.push(val)
    }
    if (val === pivot) {
      middle.push(val)
    }
    if (val > pivot) {
      right.push(val)
    }
  }

  return quickSort1(left).concat(middle, quickSort(right))
}

复制代码

这个是推荐掌握的， 很重要 （敲黑板）

算法步骤

1. 从数列中挑出一个元素，称为 "哨兵"（pivot）；
2. 重新排序数列，所有元素比哨兵值小的摆放在哨兵前面，所有元素比哨兵值大的摆在哨兵的后面（相同的数可以到任一边）。在这个分区退出之后，该哨兵就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地把小于哨兵值元素的子数列和大于哨兵值元素的子数列排序。

function quickSort2(ary, comparator = (a, b) => a - b) {
  return partition(ary, comparator)
}
function partition(ary, comparator, start = 0, end = ary.length - 1, ) {
  if (start >= end) {
    return
  }

  var pivotIndex = Math.floor(Math.random() * (end - start + 1) + start)
  var pivot = ary[pivotIndex]

  swap(ary, pivotIndex, end)

  for (var i = start - 1, j = start; j < end; j++) {
    if (comparator(ary[j], pivot) < 0) {
      i++
      swap(ary, i, j)
    }
  }

  swap(ary, i + 1, end)
  partition(ary, comparator, start, i)
  partition(ary, comparator, i + 2, end)
  return ary
}
复制代码

未完待续~

参考：

1. javascript-algorithms
2. 十大经典排序算法（动图演示）

「前端也要学点算法」&& 「前端进阶指北」

2019 年度准备持续更新「前端也要学点算法」和 「前端进阶指北」两个系列，本篇是算法系列的第一篇 ，算法系列计划旨在梳理学习常见的数据结构和算法知识，进阶指北系列旨在循序渐进逐个攻克前端进阶重难点，并且能够分享出来对前端同学们有一些帮助。 希望大家在阅读的过程当中可以斧正文中出现不严谨或是错误的地方，本人将不胜感激。

• 内容: 常见的数据结构和算法、前端进阶、面试必备知识。
• 目的: 这个系列的文章可以让读者有一些收获。

希望各位可以多多探讨，不吝赐教。 如果你希望对本系列有什么改进或者是相关内容的交流，可以邀请你加入新鲜的微信交流群，共同进步。添加时请注明-掘金，回复加群。微信id(gk15510618107)