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

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

堆排序的基本思想为：

1、升序排列，保持大堆；降序排列，保持小堆；

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

下面我将简单分析一下：

第一步建立堆：

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

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

3、实现向下调整算法，时间复杂度为O（lgn）；

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

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

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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。