一、堆排序原理

通过最大堆的性质可以知道：一个堆中最大的元素总是在堆顶的，即数组下标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代表元素个数。