C++STL之堆排序算法

概述C++STL之堆排序算法

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

/**************************优先队列的实现选择：            链表（表头插入为O(N)，删除时遍历O(N)）或者让表插入时保持排序            二叉树（删除和插入都是O(logN)）     可以达到NlogN 的时间复杂度的排序，就是使用二叉堆实现使用的排序算法就是堆排序使用一个附加数组，存储空间增加一倍  （或者将删除的最小数放入堆的最后） //??因为只会复制一次，时间复杂度并不会显著增加                                                       //??***************************/ // heapSort.h////#pragma once#include "stdafx.h"#include <vector> using namespace std;   int leftChild(int hole)  //查找节点的左子树{    return hole*2 + 1;}// 最小值堆template <typename T>voID percolateMinDown(int hole,vector<T>& vec) // vec为原数组，hole为当前要排序的堆的空穴{    int child;    T temp = vec[hole];    for (; leftChild(hole)< vec.size(); hole = child)     {        child = leftChild(hole); //chlID为hole的左子树，child+1为hole的右子树        if (leftChild(hole) != vec.size() && vec[child+1] < vec[child])   //注意数组访问不要越界        {            child ++;   //取左子树和右子树中的最小值        }        if ( temp > vec[child])   //如果左子树和右子树中的最小值仍然比要空穴的值小，则其将最小值移到当前空穴        {            vec[hole] = vec[child];        }        else                     //如果左子树和右子树中的最小值仍然比要空穴的值大，则当前空穴就是其最终位置            break;    }    vec[hole] = temp;} template <typename T>voID heapMinSort(vector<T>& vec){//     vector<T> tempVector(vec.size()+1);//     for (int i = 0; i < vec.size(); i++)//     {//         tempVector[i] = vec[i];   //这里并没有用到附加数组//     }    int hole = vec.size()/2;    for (; hole >= 0; hole--) // 从大到小依次计算空穴的值    {        percolateMinDown(hole,vec);    }  } // 最大值堆 template <typename T>voID percolateMaxDown(int hole,vector<T>& vec){    int child;    T temp = vec[hole];    for (;leftChild(hole) < vec.size(); hole = child)    {        child = leftChild(hole);        if ( leftChild(hole) != vec.size() && vec[child] < vec[child+1]) //大根堆中取两个子树的较大者        {            child++;        }        if (temp < vec[child])                                            //将左子树和右子树中的较大者移入空穴        {            vec[hole] =  vec[child];        }        else            break;     }    vec[hole] = temp;}template <typename T>voID heapMaxSort(vector<T>& vec){    int hole = vec.size()/2;    for (; hole >= 0; hole--) // 从大到小依次计算空穴的值    {        percolateMaxDown(hole,vec);    }  }

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的C++STL之堆排序算法全部内容，希望文章能够帮你解决C++STL之堆排序算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。