堆排序

文章中部分内容和思路来自《数据结构、算法与应用 c++语言描述》

接续上一篇文章《堆》:http://blog.csdn.net/superyang_/article/details/79235370

定义

先用n个元素初始化一个大根/小根堆，然后逐个从堆中提取提取元素并输出。

示意图

假设需要排序的n个元素已构成大根堆，以下图为例：

排序大致过程如下：

代码实现

// 排序后输出 template<typename T> void MaxHeap<T>::sortPrint() { T *arr = new T[_size]; int arrSize = _size; for (int i = _size - 1; i >= 0; i--) { T value = top(); pop(); arr[i] = value; } for (int i = 0; i < arrSize; i++) { qDebug() << arr[i]; } delete []arr; arr = NULL; }

与其他排序的比较

感觉文字定义不太好理解的，可以看看这篇文章http://blog.csdn.net/u013068377/article/details/39368029