解读堆排序算法及用C++实现基于最大堆的堆排序示例

最终的堆排序算法中，build_max_heap的复杂度是已知的， 迭代部分和build_max_heap的实现类似，而且不难看出， 交换后的根元素在下一次建堆过程中必然下沉到堆底，因此无论情况好坏， 该迭代过程时间复杂度都是O(nlogn)O(nlog⁡n)， 所以整个算法的最好最坏和平均时间复杂度都是O(nlogn)O(nlog⁡n)。
堆排序算法的空间复杂度是O(1)O(1)，从实现上很容易看出来。