在排序算法中，一些比较简单和直观的算法的复杂度基本在O(n^2)，比如 冒泡排序，选择排序和插入排序。在处理较小的数据时，他们的性能较好。但是如果数据量变大，那么就需要性能更好的排序算法。这里来介绍一个时间复杂度为O(n log(n)) 的算法—*堆排序。

完全二叉树&堆

在介绍这个算法之前，我们先了解一下什么是完全二叉树（complete binary tree）。完全二叉树有以下特点：

  • 每个父节点只有两个子节点，并且除了最后一层，每一层的节点都是满的。
  • 所有节点靠左排列。

堆（heap）是完全二叉树的一种，他的特点是父节点总是大于子节点。

假设我们现在有这样的数据: [55, 42, 7, 93, 79, 29, 61, 43, 47] 。我们可以得到下图所示的完全二叉树。

tree.png

在此基础上，我们对里面的节点进行遍历，如果某个节点比父节点大，那么就交换彼此的位置。29 比 7 大，那么交换 29和7；61 > 29 , 交换61 和 29; 61 > 55，61交换到了根节点；93 > 42, 这时交换42和93。以此类推，我们最后得到了这样的堆。
tree2.png
由于堆的特性，根节点一定是最大的。那么我们每次把跟节点弹出到队尾，所有节点被弹出后，我们的数据就排序好了。这里又引出了另一个问题，每次我们弹出一个值，剩下的值就不能构成一个堆了。所以我们每次移除根节点后，还要对剩余的数据进行整理，重新构建堆。

Array to Heap

那么第一步就是先把数组变成堆，以下代码展示了一个数组到堆的过程。
这里需要知道的一个点是，对于某下标index的元素，他的父节点下标一定是 (index - 1) / 2。 （本文中 / 2 后自动向上取整）

  1. function makeHeap (arr) {
  2.   // 构建堆的核心在于交换子节点和父节点的位置，直到父节点总是大于子节点
  3.   for(let i = 0; i < arr.length; i++) {
  4.     let crtIndex = i
  5.     let parent = crtIndex
  6.     while (parent !== 0) {
  7.       parent = Math.floor((crtIndex - 1) / 2)
  8.       if (arr[parent] >= arr[crtIndex]) {
  9.         break // 因为我们是从根节点开始排列，所以不用每一次都回溯到最上层
  10.       }
  11.       // 交换位置
  12.       let temp = arr[parent]
  13.       arr[parent] = arr[crtIndex]
  14.       arr[crtIndex] = temp
  15.       crtIndex = parent
  16.     }
  17.   }
  18.   return arr
  19. }

HeapSort

以下是是堆排序的完整代码。

  1. **
  2.  * array => heap
  3.  * @param arr number[]
  4.  * @param end number 构建堆的终点
  5.  * @return heap number[]
  6.  */
  7. function makeHeap (arr, end) {
  8.   // 构建堆的核心在于交换子节点和父节点的位置，直到父节点总是大于子节点
  9.   for(let i = 0; i < end; i++) {
  10.     let crtIndex = i
  11.     let parent = crtIndex
  12.     while (parent !== 0) {
  13.       parent = Math.floor((crtIndex - 1) / 2)
  14.       if (arr[parent] >= arr[crtIndex]) {
  15.         break // 不用每一次都回溯到最上层
  16.       }
  17.       // 交换位置
  18.       let temp = arr[parent]
  19.       arr[parent] = arr[crtIndex]
  20.       arr[crtIndex] = temp
  21.       crtIndex = parent
  22.     }
  23.   }
  24.   return arr
  25. }
  27. /**
  28.  * 堆排序
  29.  * @param arr number[]
  30.  */
  31. function heapSort (arr) {
  32.   let heap = makeHeap(arr, arr.length)
  33.   for(let i = heap.length; i > 0; i--) {
  34.     // 因为堆总是最大的值在上面，所以交换首位位置，即可把最大的值放到队尾
  35.     let temp = heap[0]
  36.     heap[0] = heap[i - 1]
  37.     heap[i - 1] = temp
  38.     // 交换位置后，数组就不再是堆了，要重新排列，重新排列时，忽略最后一位已经排序好的数字
  39.     heap = makeHeap(heap, i - 1)
  40.   }
  41.   return heap
  42. }

我们来看这个算法，由于在排序的时候我们要遍历数组，这一步的复杂度为n，交换首位位置的数字是O(1)，可以忽略不计，每次构建堆的复杂度为 log(n) , log(n - 1) … log(1)，无限接近于log(n)，因此最终的复杂度为O(n * log(n))。