【算法导论】heapsort（堆排序）的代码实现

LZ还是在Qt上进行编译的。#include QCoreApplication #include algorithm #include functional #include vector #include iostream using namespace std; templatetypename Type class Heap { public: Heap(const vectorType a_array) { m_array.assign(a_array.begin(),a_array.end()); } templatetypename Compare void sort(Compare comp); void printArray(const vectorType a_array); private: vectorType m_array; //comp 为lessType 则大数下沉创建最小堆从小到大排序 //comp 为greaterType 则小数下沉创建最大堆从大到小排序 templatetypename Compare void creatHeap(Compare comp); //创建堆 templatetypename Compare void downElement(int a_elem, Compare comp); //下沉元素 }; templatetypename Type templatetypename Compare void HeapType::sort(Compare comp) { printArray(m_array); creatHeap(comp); //建堆 vectorType array; for (int i m_array.size() - 1; i 0; i--) { array.push_back(m_array[0]); //保留堆顶 swap(m_array[0], m_array[i]); //交换 m_array.pop_back(); //去掉最后一个元素 downElement(0,comp); //将新的首元素下沉 } printArray(array); m_array.assign(array.begin(),array.end()); } templatetypename Type templatetypename Compare void HeapType::creatHeap(Compare comp) { //从最后一个非叶子节点开始将每个父节点都调整为最小堆 for (int im_array.size()/2-1; i0; i--) { downElement(i, comp); } } templatetypename Type templatetypename Compare void HeapType::downElement(int a_elem, Compare comp) //下沉元素 { int min; //设置最小元素下标 int index a_elem; //当前下沉的元素下标 while (index*21 m_array.size())//存在左节点 { min index*21; if (index*22 m_array.size())//存在右节点 { //左右节点比较选出最小的 if (comp(m_array[index*22],m_array[min])) { min index*22; } } //同子节点比较若父节点最小则结束 if (comp(m_array[index],m_array[min])) { break; } else//选最小元素到父节点 { swap(m_array[min],m_array[index]); index min; } } } templatetypename Type void HeapType::printArray(const vectorType a_array) { for (int i0; ia_array.size(); i) { cout a_array[i] ; } cout endl; } int main(int argc, char *argv[]) { QCoreApplication a(argc, argv); vectorint array; for (int i1; i10; i) { array.push_back(i); } random_shuffle(array.begin(), array.end());//打乱顺序 Heapint heap(array); heap.sort(lessint()); heap.sort(greaterint()); return a.exec(); }部分代码参考来自http://www.cnblogs.com/hanxi/archive/2012/10/12/2721540.html