堆排序是从 二叉堆结构 衍生出来的排序算法，复杂度为 $O(NlogN)$。堆排序主要分两步，第一步是在待排序数组上原地创建二叉堆（Heapify），然后进行原地排序（Sort）。
想法
堆排序的两个关键步骤：
1、原地建堆（Heapify）：直接把待排序数组原地变成一个二叉堆。
2、排序（Sort）：将元素不断地从堆中取出，最终得到有序的结果。
下面这些函数就是从 二叉堆实现优先级队列 中的优先级队列实现里抠出来的，把数组作为函数参数传入，其他的逻辑完全一样：
def min_heap_swim(heap, node):
# 小顶堆的上浮操作，时间复杂度是树高 O(logN)
while node > 0 and heap[parent(node)] > heap[node]:
swap(heap, parent(node), node)
node = parent(node)
def min_heap_sink(heap, node, size):
# 小顶堆的下沉操作，时间复杂度是树高 O(logN)
while left(node) < size or right(node) < size:
# 比较自己和左右子节点，看看谁最小
min_index = node
if left(node) < size and heap[left(node)] < heap[min_index]:
min_index = left(node)
if right(node) < size and heap[right(node)] < heap[min_index]:
min_index = right(node)
if min_index == node:
break
# 如果左右子节点中有比自己小的，就交换
swap(heap, node, min_index)
node = min_index
def max_heap_swim(heap, node):
# 大顶堆的上浮操作
while node > 0 and heap[parent(node)] < heap[node]:
swap(heap, parent(node), node)
node = parent(node)
def max_heap_sink(heap, node, size):
# 大顶堆的下沉操作
while left(node) < size or right(node) < size:
# 小顶堆和大顶堆的唯一区别就在这里，比较逻辑相反
# 比较自己和左右子节点，看看谁最大
max_index = node
if left(node) < size and heap[left(node)] > heap[max_index]:
max_index = left(node)
if right(node) < size and heap[right(node)] > heap[max_index]:
max_index = right(node)
if max_index == node:
break
swap(heap, node, max_index)
node = max_index
def parent(node):
# 父节点的索引
return (node - 1) // 2
def left(node):
# 左子节点的索引
return node * 2 + 1
def right(node):
# 右子节点的索引
return node * 2 + 2
def swap(heap, i, j):
# 交换数组中两个元素的位置
heap[i], heap[j] = heap[j], heap[i]
简单直接的堆排序实现
def sort(nums):
# 第一步，原地建堆，注意这里创建的是大顶堆
# 只要从左往右对每个元素调用 swim 方法，就可以原地建堆
for i in range(len(nums)):
max_heap_swim(nums, i)
# 第二步，排序
# 现在整个数组已经是一个大顶了，直接模拟删除堆顶元素的过程即可
heap_size = len(nums)
while heap_size > 0:
# 从堆顶删除元素，放到堆的后面
swap(nums, 0, heap_size - 1)
heap_size -= 1
# 恢复堆的性质
max_heap_sink(nums, 0, heap_size)
# 现在 nums[0..heap_size) 是一个大顶堆，nums[heap_size..) 是有序元素
这里面一个关键点是要用大顶堆来完成 nums 从小到大的排序，因为从堆顶删除的元素是从后往前填到 nums 数组中的，最终 nums 中的元素是从小到大排序的。
如果你用小顶堆的话，最终 nums 中的元素是从大到小排序的，还需要再翻转一下数组，没有大顶堆的效率高。
堆排序的复杂度分析
我们来分析一下上述代码的时间复杂度，假设 nums 的元素个数为 N：
- 第一步建堆的过程中，
swim方法的时间复杂度是
$O(logN)$，算法对每个元素调用一次swim方法，所以总时间复杂度是 $O(NlogN)$。 - 第二步排序的过程中，每次
sink方法的时间复杂度是 $O(logN)$，算法对每个元素调用一次sink方法，所以总时间复杂度是 $O(NlogN)$。
综上，整个堆排序的时间复杂度是 $2NlogN$，用 Big O 表示就是 $O(NlogN)$。与 快速排序、归并排序 是一个级别的排序算法。
堆排序的稳定性
堆排序是一种不稳定的排序算法，原因在于它在排序过程中交换元素时，可能会改变相同元素的相对顺序。
