C++数据结构堆排序的实现-创新互联

堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据。我将用c++实现一个堆来简单分析一下。

成都创新互联公司网站建设由有经验的网站设计师、开发人员和项目经理组成的专业建站团队,负责网站视觉设计、用户体验优化、交互设计和前端开发等方面的工作,以确保网站外观精美、成都做网站、网站制作易于使用并且具有良好的响应性。

堆排序的基本思想为:

1、升序排列,保持大堆;降序排列,保持小堆;

2、建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整;直到堆中只剩下一个有效值;

下面我将简单分析一下:

第一步建立堆:

1、我用vector顺序表表示数组;

2、用仿函数实现大小堆随时切换,实现代码复用;

3、实现向下调整算法,时间复杂度为O(lgn);

下面是我用某教材中的一个建最小堆的过程图,希望能更直观一些:

C++ 数据结构 堆排序的实现

为了保证复用性,用仿函数重载了(),下面是复用的向下调整算法:

void _AdjustDown(int root,int size) 
{ 
  Camper camper;    //仿函数 
  int parent = root; 
  int child = parent * 2 + 1; 
  while (child <= size) //保证访问不越界 
  { 
    if (child < size && camper(_vec[child+1] , _vec[child])) //保证存在右子树、同时判断右子树是否大于或小于左子树 
    { 
      child++; 
    } 
    if (camper(_vec[child], _vec[parent])) 
    { 
      swap(_vec[parent], _vec[child]); 
      parent = child; 
      child = parent * 2 + 1; 
    } 
    else 
    { 
      break; 
    } 
  } 
 
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


当前标题:C++数据结构堆排序的实现-创新互联
文章转载:http://scyanting.com/article/ioihh.html