说透排序算法(下)

系列开篇

这几篇说什么，你能获得什么

这几篇重点是：

1. 详细描述各种排序算法的使用方式，实现方式，特点，复杂度分析。
2. 让你能清晰的了解这些排序的区别与联系、掌握排序思想的精髓。

先说下为什么分上中下3篇，因为一篇的话篇幅太长，人的接受能力、程度还有耐心分成2篇比一篇更容易吸收，而且读下篇的时候能很好的用上篇的一些基础知识来做铺垫，流水账列出全部的排序方式只会让你读一遍就忘，收藏然后永远就不看了。

我们不要流水账列举这些算法，一个个拆解他们，从简单的开始，一步步走向更复杂的逻辑。

下面我们就一个个看这些个排序算法，不要急，一个个吃透了就不担心忘记，因为理解了，忘了就直接跳到中间看就好，右边有目录，随时查阅。

先列下上/中篇链接

• 一文说透排序算法的特点（上）
• 一文说透排序算法的特点（中）

大纲-由浅入深

上：

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序

中：

• 计数排序
• 桶排序
• 基数排序

下

• 快速排序
• 归并排序
• 堆排序

总结

• 先了解各种排序后再看看动画图加深印象
• 各种排序的各维度对比
• 时间空间复杂度如何分析
• 排序的深水区拓展

下面进入主题

1. 快速排序基础

快速排序的基本思想就是分治法

快速排序的工作原理：

1. 在数组中选择一个元素，这个元素被称为基准（pivot）。
2. 重新排列数组，以使基准左侧的所有元素都小于基准，而右侧的所有元素都大于等于基准。
3. 针对基准的左侧和右侧递归重复这一过程，直到全部元素完成排序。

实现

let testArr = [1, 9, 34, 5, 1, 2]

const quickSort = (array) => {
  // 这个是递归出口, 只有一个(或0个)元素 没啥好排，直接返回
  if (array.length <= 1) {
    return array
  }
  // 取个数组第一个元素作为基准点
  let pivotPointIndex = array[0]
  // 把中间的基准点取出来 那么下面就是个拼接的过程 [基准点左边Arr + 基准点 + 基准点右边Arr]
  let pivotPoint = array.splice(pivotPointIndex, 1)[0];
  // 申请2个数组空间用来放置基准点的左边数组和右边数组
  let left = [], right = []

  // 遍历下数组，左边数组值小于基准点值 右边Arr >= 基准点值
  array.map(item => {
    if (item < pivotPoint) {
      left.push(item)
    } else {
      right.push(item)
    }
  })
  
  // 这里是返回合并的数组 左右数组需要继续 递归地调用同样的方式来排序
  return [...quickSort(left), pivotPoint, ...quickSort(right)]
}

console.log(quickSort(testArr))

等（总结）篇，我们来仔细分析下这个快排，现在我想你看完这个版本，对于快排的核心你应该有了深刻印象,并能轻松手写了。

我们先抛出一些思考问题?

1. 如何选择合适的pivot？对效率有什么影响?
2. 如何处理重复元素? 如果元素和基准相同怎么办?
3. 有没有更快的分区方法?

2. 归并排序

算法拆解过程

归并排序也是采用了分治的思想。我们再看如何分而治之

我们画个图来看

      arr = [8, 3, 6, 2]
             /   分   \
          [8, 3]    [6, 2]
            |治        |治
          [3, 8]    [2, 6]
             \   合   /
            [2, 3, 6, 8]

看出来了吗，那么我们的关注点就是下面两点：

1. 如何去治(排序子数组)
2. 又如何去合(合并两个有序的子数组)

分别给出解释

1. 治，其实你只要不断地去分，直到分到只有一个元素为止(递归出口)，一个元素自然是有序的。
2. 合，其实非常简单，我们只要不断取出两个有序数组中比较小地那个放在一个辅助数组里，（通过头指针比较），直到把两个数组中元素都取完，辅助数组就是已经排序好的结果。这个合并过程可以做这样的拆分
   1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
   2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
   3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
   4. 重复步骤 3 直到某一指针达到序列尾；
   5. 将另一序列剩下的所有元素直接复制到合并序列尾。

简单图示下

两个有序数组 [3, 8]   [2, 6]   选择arr[i]和arr[j]中较小的依次放入tempArr
            |        |
            i-->     j-->
  temp数组  [2， 3， 6， 8]

那么我们总结下算法过程：

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

我们最后放出完整代码

递归实现

let testArr = [5, 62, 12, 85, 26, 41, 6, 14, 16, 124, 12.5]

const mergeSortRecurtion = (array) => {
  let len = array.length
  // 分到只有一个元素，递归出口
  if (len < 2) {           
    return array
  }
  // 取中间数作为2分的基准
  let middle = Math.floor(len / 2)
  // 再已基准分为左右数组，做递归操作，是不是跟快速排序一个思想 —— 分治
  let left = array.slice(0, middle)
  let right = array.slice(middle)
  // 再把左右[递归已排序数组]合并起来就行
  return merge(mergeSortRecurtion(left), mergeSortRecurtion(right))
}

// 合并左右[ 已排序有序 ]数组
const merge = (left, right) => {
  let 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
}

console.log(mergeSortRecurtion(testArr))

迭代实现

let testArr = [5, 62, 12, 85, 26, 41, 6, 14, 16, 124, 12.5]

const mergeSortIteration = (array) => {
  let len = array.length
  // 刚开始合并的数组大小是1，接着是2，接着4, 8...
  for (let i = 1; i < len; i += i) {
    // 进行数组的划分
    let left = 0
    let mid = left + i - 1
    let right = mid + i
    // 进行合并，对数组大小为 i 的数组进行两两合并
    while (right < len) {
      merge(array, left, mid, right)
      left = right + 1
      mid = left + i - 1
      right = mid + i
    }
    // 小心因为元素数量不是 i 的倍数导致缺失，需要补充合并
    if (left < len && mid < len) {
      merge(array, left, mid, len - 1);
    }
  }
  return array
}

// 将 array[left...mid] 和 array[mid + 1...right] 这两个有序数组合并
// 其实这种写法和递归的写法没啥两样
const merge = (array, left, mid, right) => {
  // 用一个临时数组存放合并结果
  let tempArr = []
  let i = left
  let j = mid + 1
  for (let k = left; k <= right; k++) {
    if (i > mid) {
      tempArr[k] = array[j++]
    } else if (j > right) {
      tempArr[k] = array[i++]
    } else if (array[i] <= array[j]) {
      tempArr[k] = array[i++]
    } else {
      tempArr[k] = array[j++]
    }
  }
  // 把临时数组复制到原数组
  for (let k = left; k <= right; k++) {
    array[k] = tempArr[k];
  }
}

console.log(mergeSortIteration(testArr))

3. 堆排序

算法拆解过程

再讲排序之前，首先我们得了解什么是堆，或者更具体点什么是二叉堆(binary heap)。得先理清下面的概念：

完全二叉树

完全二叉树定义: 若设二叉树的深度为h，除第 h 层外，其它各层 (1 ～ h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，比如这就是完全二叉树:

       1       - 1层
      / \
     2   3     - 2层
    / \
   3   4       - 3层（h = 3）

而下面的不是:

       1       - 1层
      / \
     2   3     - 2层
    /     \
   3       5   - 3层（h = 3）   // 不满足最后一层节点都在左边，(左边不能缺)

       1       - 1层
      / 
     2         - 2层（h = 2）   // 不满足除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数
    / \    
   3   3       - 3层（h = 3）  

堆

堆(heap)，又称为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。堆（Heap）是一种特别的完全二叉树。

• 在队列中，我们按照元素进入队列的先后顺序取出元素。先进先出。
• 而在堆中，我们不是按照元素进入队列的先后顺序取出元素，而是按照元素的优先级取出元素。

这是wikipedia的定义

二叉堆

二叉堆本质上是一种完全二叉树，分为最大堆和最小堆(大根堆/小根堆)

• 父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
• 最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。
• 最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。

        1       
      /   \
     2     3     
    / \   / 
   5   4 4          // 最小堆

        9       
      /   \
     5     7     
    / \   / \
   3   1 6   2      // 最大堆

注意层级跟大小无关。只是根与孩子有大小关系。

最大堆和最小堆的特点，决定了:

• 最大堆的堆顶是整个堆中的最大元素；
• 最小堆的堆顶是整个堆中的最小元素。

二叉堆的基本操作

对于二叉堆，一般有这几种操作：

• 插入节点
• 删除节点
• 构建二叉堆

这几种操作都是基于堆的自我调整

下面让我们以最小堆为例，来说明二叉堆是依靠自我调整来做操作的。

1. 插入节点

插入位置是完全二叉树的最后一个位置，插入过程如下：

          3
        /   \
       5     7
      / \     
     9   6        

这是原始的最小堆，插入位置是完全二叉树的最后一个位置，比如我们在这个位置插入一个新节点 [1]

          3
        /   \
       5     7
      / \   / 
     9   6 [1]  

这时候，我们让节点 [1]的它的父节点 5 做比较，如果 [1] 小于 7，则让新节点“上浮”，和父节点交换位置。

          3
        /   \
       5    [1]
      / \   / 
     9   6 7  

继续用节点 [1] 和父节点 3 做比较，如果[1]小于 3，则让新节点继续“上浮”。最终让新节点 [1] 上浮到了堆顶位置，调整完毕。

          1
        /   \
       5     3 
      / \   / 
     9   6 7  

2. 删除节点

二叉堆的节点删除过程和插入过程正好相反，所删除的是处于堆顶的节点。

          3
        /   \
       5     4
      / \     
     9   6        

这是原始的最小堆，删除位置是处于堆顶的节点，比如现在删除的是 (3)

         (3)
        /   \
       5     4
      / \    
     9   6 
         |
    最后一个位置 

这时候，为了维持完全二叉树的结构，我们把堆的最后一个节点(6)补到原本堆顶的位置。

         (6)
        /   \
       5     4
      /    
     9  

接下来我们让移动到堆顶的节点(6)和它的左右孩子进行比较，如果左右孩子中最小的一个（显然是节点4）那么让节点(6) “下沉”。

          4
        /   \
       5    (6)
      /    
     9  
这样这个最小堆就调整好了。

3. 构建二叉堆

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。过程如下:

           8
        /    \
       7      3
      / \    / 
     6   5  4    

这是一个无序的完全二叉树。

           8
        /    \
      [7]     3
      / \     / 
     6   5   4
    叶子 叶子 叶子

首先，我们从最后一个非叶子节点开始，也就是从节点[7]开始, 大于它左右孩子中最小的一个，则节点[7]下沉。最小的是5，下沉到 5 的位置

           8
        /    \
       5      3
      / \    / 
     6  [7] 4 

然后是 3, 小于孩子，不用下沉

         【8】
        /    \
       5      3
      / \    / 
     6  7   4 
继续往上，关注【8】，比较左右孩子，取较小位置下沉

           3
        /    \
       5    【8】
      / \    / 
     6  7   4 
继续往下直到调整完毕
           3
        /    \
       5      4
      / \    / 
     6  7  【8】 
这样一来，一个无序的完全二叉树就构建成了一个最小堆。

总结下

• 插入过程
  1. 插入节点二叉树最后一个位置
  2. 依次与父级比较，然后上浮
• 删除过程
  1. 删除堆顶元素
  2. 把二叉树最后一个节点补到堆顶。
  3. 让堆顶依次比较左右孩子节点，如果比孩子大，那么取孩子中谁小，就下沉到那个孩子的位置，依次往下比较，直到二叉堆构建完毕。
• 构建二叉堆过程就是所有非叶子节点依次下沉

堆的代码实现

二叉堆虽然是一颗完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。

换句话说，二叉堆的所有节点都存储在数组当中。简单举例如图

          3
        /   \
       5     4
      / \   / 
     6  7  8 
            
           left child
            |
  [3, 5, 4, 6, 7, 8]
      |        |
    parent   right child

数组中，在没有左右指针的情况下，如何定位到一个父节点的左孩子和右孩子呢？

我们可以依靠数组下标来计算。假设父节点的下标是 parent，那么它的左孩子下标就是 2 * parent + 1；它的右孩子下标就是 2 * parent + 2 。

至于为什么，请使用完全二叉树性质和简单的数学知识思考下就明白了。

基本操作的代码实现

• 上浮调整

/**
 * @param array     待调整的堆
 */
const upAdjust = (array) => {
  // 在最后插入节点
  let childIndex = array.length - 1;
  let parentIndex = Math.floor((childIndex - 1) / 2);
  // backup保存插入子节点值，用于最后的赋值
  let backup = array[childIndex]
  // 逐步跟父节点比较，上浮
  while (childIndex > 0 && backup < array[parentIndex]) {
    // 无需真正交换，因为我们有备份
    array[childIndex] = array[parentIndex]
    childIndex = parentIndex
    parentIndex = Math.floor((childIndex - 1) / 2);
  }
  array[childIndex] = backup
}

• 下沉调整

/**
 * @param array     待调整的堆
 * @param parentIndex    要下沉的父节点
 * @param length    堆的有效大小
 */
const downAdjust = (array, parentIndex, length) => {
  // backup保存父节点值，用于最后的赋值
  let backup = array[parentIndex]
  // 左孩子坐标
  let childIndex = parentIndex * 2 + 1;
  while (childIndex < length) {
    // 右孩子的值大于左孩子的值，交换定位在右孩子
    if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
      childIndex = childIndex + 1;
    }
    // 如果父节点大于(看你排序要升要降)任何一个孩子的值，直接跳出
    if (backup >= array[childIndex]) {
      break;
    }
    // 无需真正交换，因为我们有备份
    array[parentIndex] = array[childIndex]
    parentIndex = childIndex
    childIndex = 2 * childIndex + 1
  }
  array[parentIndex] = backup
}

• 构建堆

/**
 * @param array     待调整的堆
 */
const buildHeap = (array, parentIndex, length) => {
  // 从最后一个非叶子节点开始，依次下沉调整
  for (let i = Math.floor((array.length - 2) / 2); i >= 0; i--) {
    downAdjust(array, i, array.length)
  }
}

铺垫了这么多，我觉得差不多了，别忘了主题堆排序 ^-^

其实理解非常简单了，堆顶总是最小(或最大元素)，删除了，放到尾部，调整堆，那么第二小的就是堆顶了，再删除，放尾部，再调整堆。。。就是这么个思想

堆排序算法步骤

1. 把无序数组构建成二叉堆。
2. 删除堆顶元素，移到集合尾部。
3. 调节堆产生新的堆顶。再回到2，依次循环。

堆排序实现

let testArr = [5, 62, 12, 85, 26, 41, 13, 43, 21, 3.5]

// 下沉调整方法
const downAdjust = (array, parentIndex, length) => {
  // backup保存父节点值，用于最后的赋值
  let backup = array[parentIndex]
  // 左孩子坐标
  let childIndex = parentIndex * 2 + 1;
  while (childIndex < length) {
    // 右孩子的值大于左孩子的值，交换定位在右孩子
    if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
      childIndex = childIndex + 1;
    }
    // 如果父节点大于(看你排序要升要降)任何一个孩子的值，直接跳出
    if (backup >= array[childIndex]) {
      break;
    }
    // 无需真正交换，因为我们有备份
    array[parentIndex] = array[childIndex]
    parentIndex = childIndex
    childIndex = 2 * childIndex + 1
  }
  array[parentIndex] = backup
}

const heapSort = (array) => {
  let len = array.length
  // 1. 把无序数组先构建成二叉堆
  for (let i = Math.floor((len - 2) / 2); i >= 0; i--) {
    downAdjust(array, i, len)
  }
  // console.log(array, '建堆成功打印结果')
  // 2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶，注意每次len都减少了，因为删除了元素
  for (let j = len - 1; j > 0; j--) {
    // 最后一个元素和第一元素进行交换
    [array[0], array[j]] = [array[j], array[0]]
    // 下沉调整最大堆 注意 j 每次都减一，也就是下沉操作len不断变短
    downAdjust(array, 0, j)
  }
  return array
}

console.log(heapSort(testArr))

总结篇我们来整体看下这些排序，和时间空间复杂度分析等。

上面这句话给你们，同样也给我自己前进的动力。

我是摩尔，数学专业，做过互联网研发，测试，产品
致力用技术改变别人的生活，用梦想改变自己的生活
关注我，找到自己的互联网思路，踏实地打牢固自己的技术体系
点赞、关注、评论、谢谢
有问题求助可私信 1602111431@qq.com 我会尽可能帮助你

参考

• www.runoob.com/w3cnote/sor…
• www.cnblogs.com/guoyaohua/p…
• mp.weixin.qq.com/s/KjeV_ENmV…
• zhuanlan.zhihu.com/p/42586566
• zhuanlan.zhihu.com/p/57088609