排序算法三：堆排序
一、堆排序原理
通过最大堆的性质可以知道：一个堆中最大的元素总是在堆顶的，即数组下标0的位置。基于这一点，我们可以每次都把堆中的最大值提取出来，放到当前数组的后面。然后重新构建最大堆，重复这个过程，以此来完成一个数组的排序。
例如，一个已知的最大堆为：
把最大的元素16提取出来，放到最后。然后重新建堆，此时堆中最大的元素为15，更新后的堆为：
再把15提取出来，重新建堆，得到：
如此往复，直到最后堆中的元素只有一个，就完成了整个数组的排序。
二、代码实现
堆排序的关键点在于构造堆，如何构造堆可参考数据结构之堆。基于模板的最大堆化函数实现：
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);
}
}实现堆排序，堆排序的关键点在于从后往前排：
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代表元素个数。
