一、堆排序原理
通过最大堆的性质可以知道：一个堆中最大的元素总是在堆顶的，即数组下标 0 的位置。基于这一点，我们可以每次都把堆中的最大值提取出来，放到当前数组的后面。然后重新构建最大堆，重复这个过程，以此来完成一个数组的排序。
例如，一个已知的最大堆为：
把最大的元素 16 提取出来，放到最后。然后重新建堆，此时堆中最大的元素为 15，更新后的堆为：
再把 15 提取出来，重新建堆，得到：
如此往复，直到最后堆中的元素只有一个，就完成了整个数组的排序。
二、代码实现
堆排序的关键点在于构造堆，如何构造堆可参考数据结构之堆。基于模板的最大堆化函数实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
template <typename T> static void max_heapify(T *data, size_t len, size_t idx) { size_t largest, lchild, rchild; lchild = LCHILD(idx); rchild = RCHILD(idx); if (lchild < len && data[lchild] > data[idx]) largest = lchild; else largest = idx; if (rchild < len && data[rchild] > data[largest]) largest = rchild; if (idx != largest) { my_swap(data[idx], data[largest]); max_heapify(data, len, largest); } } |
实现堆排序，堆排序的关键点在于从后往前排：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
template <typename T> static void heap_sort(T *data, size_t len) { size_t i, mid; mid = len / 2; // 建堆 for (i = mid - 1; i >= 0 && i < len; i--) { max_heapify(data, len, i); } // 堆排序，从后往前 for (i = len - 1; i >= 1; i--) { my_swap(data[i], data[0]); max_heapify(data, --len, 0); } } |
时间复杂度
堆排序的时间主要消耗再建堆上面，每次拿掉一个元素之后，都重新执行最大堆化。
每次构造最大堆的时间复杂度为 O(log(n))，因此堆排序的总时间复杂度为 n(log(n))，n 代表元素个数。