堆排序

堆排序利用堆这种数据结构来进行排序。基本思路是：先把所有数据放进堆里构建最大堆，然后不断取出最大值放在数组末尾。

以 5 2 7 3 6 1 4 为例：

第 1 步：将所有数据存入堆，构建最大堆（子结点小于父结点，最大值在根）

      7          ← 最大值在根结点
    /   \
   6     5
  / \   /
 2   3 1 4

第 2 步：取出根结点（最大值 7），放在数组最右边

  堆:                数组:  _ _ _ _ _ _ [7]
      6
    /   \
   4     5
  / \   /
 2   3 1

第 3 步：重构堆，取出新的最大值 6，放在右数第 2 个位置

  堆:                数组:  _ _ _ _ _ [6 7]
      5
    /   \
   4     1
  / \
 2   3

继续重复：每次取出最大值，放在数组右边的下一个位置

取出 5 →  _ _ _ _ [5 6 7]
取出 4 →  _ _ _ [4 5 6 7]
取出 3 →  _ _ [3 4 5 6 7]
取出 2 →  _ [2 3 4 5 6 7]
取出 1 →  [1 2 3 4 5 6 7]

排序完成！

堆排序的时间复杂度为 O(n log n)，比冒泡、选择、插入排序的 O(n²) 都快。

#堆排序