首页 > 代码库 > C++堆排序
C++堆排序
前几天处理工作方面的事情, 确实耽误了几天, 导致博客停更了, 今天上午看到算法导论的堆排序, 想用 C++ 实现下, 就当练练手了.
算法导论里使用的是起始编号为 1 的容器, 那么实现的方法要不就是把 STL 容器打包, 自己建一个起始编号为 1 的容器, 要不就按照起始编号为 0 的来. 想了一下总觉得第一种方案有种削足适履的蛋疼感, 就是写出来也只能表示我对于 STL 容器的理解而不是对算法的理解, 因此如果真正理解了堆排序的思想, 那么无论是以什么值为起始编号都是一样的. 所以我选择了第二个方案, 代码如下:
#include <iostream>#include <deque>inline int Left (int i){ return 2 * i + 1;}inline int Right (int i){ return 2 * i + 2;}void MaxHeapify (std::deque<int> &ideq, int node){ int largest = node; int limit = ideq.size (); auto SmallerThan = [&] (int child){ return (child < limit) && (ideq[largest] < ideq[child]); }; int leftNode = Left (node); if (SmallerThan (leftNode)) { largest = leftNode; } int rightNode = Right (node); if (SmallerThan (rightNode)) { largest = rightNode; } if (largest != node) { std::swap (ideq[largest], ideq[node]); MaxHeapify (ideq, largest); }}std::deque<int> BuildMaxHeap (std::deque<int> &ideq){ std::deque<int> heap (ideq); for (int i = ideq.size () / 2 - 1; i > -1; --i) { MaxHeapify (heap, i); } return std::move (heap);}void HeapSort (std::deque<int> &ideq){ auto heap = BuildMaxHeap (std::move(ideq)); for (int i = ideq.size () - 1; i > -1; --i) { ideq[i] = std::move (heap[0]); heap.pop_front (); MaxHeapify (heap, 0); }}void Print (const std::deque<int> &ideq){ for (const auto &elem : ideq) { std::cout << elem << "\t"; }}int main (){ std::ios::sync_with_stdio (false); std::deque<int> ideq{ 5, 13, 2, 25, 7, 17, 20, 8, 4}; Print (ideq); HeapSort (ideq); std::cout << "\n"; Print (ideq); std::cout << std::endl; return 0;}
其实我觉得用 forward_list 似乎更为贴切, 但是使用上没有 deque 方便, so......
其间因为有些粗心, 导致了一些小问题, 所以不得不说 VS 的调试能力就是强啊......
C++堆排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。