[C++] #yyds干货盘点#算法给小码农堆排序至尊骨

把数组中的元素全都push到小堆中，然后再取堆顶元素重新给数组，就可以达到升序的效果了

//升序
void HeapSort(HPDataType* a,int n)
{
  HP hp;
  HeapInit(&hp);
  int i = 0;
  //建立一个小堆
  for (i = 0; i < n; i++)
  {
    HeapPush(&hp, a[i]);
  }
  //然后把堆顶的元素重新放到数组里面
  for (i = 0; i < n; i++)
  {
    a[i] = HeapTop(&hp);
    //用完pop掉
    HeapPop(&hp);
  }
  HeapDestroy(&hp);
}

testHeapSort()
{
  int a[] = { 40,2,0,12,5,454,2323 };
  //堆排序
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  int i = 0;
  for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  {
    //把数组里面的元素取出来
    printf("%d ",a[i]);
  }
  printf("\n");
}

（这里的插入不是真正的插入，因为这些数据原本就在里面，我们就是在调堆，类似插入）

//真正玩法
void HeapSort(HPDataType* a, int n)
{
  assert(a && n>=0);
  //把数组a构建成堆
  int i = 0;
  for (i = 0; i < n; i++)
  {
    AdjustUp(a,n,i);
  }
}

//真正玩法
void HeapSort(HPDataType* a, int n)
{
  assert(a && n>=0);
  //把数组a构建成堆
  int i = 0;
  //向上调整
  for (i = 0; i < n; i++)
  {
    AdjustUp(a,i);
  }
  //根与最后一个数交换并每次都找到次大的数
  int tail = n - 1;
  while (tail)
  {
    Swap(&a[0], &a[tail]);//根与最后一个数交换
    tail--;
    for (i = 0; i <= tail; i++)
    {
      AdjustUp(a, i);
    }
  }   
}

testHeapSort()
{
  int a[] = { 40,2,50,12,5,454,2323,};
  //堆排序
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  int i = 0;
  for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  {
    //把数组里面的元素取出来
    printf("%d ",a[i]);
  }
  printf("\n");
}

有种就是这样玩的

//真正玩法
void HeapSort(HPDataType* a, int n)
{
  assert(a && n>=0);
  //把数组a构建成堆
  int i = 0;
  ////向上调整
  //for (i = 0; i < n; i++)
  //{
  //  AdjustUp(a,n,i);
  //}
  //向下调整
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  //根与最后一个数交换并每次都找到次大的数
  int tail = n - 1;
  for (i = tail; i > 0; i--)
  {
    Swap(&a[0],&a[i]);//根与最后一个数交换
    AdjustDown(a, i, 0);//向下调整每次都找到次大的数
  }   
}

testHeapSort()
{
  int a[] = { 40,2,50,12,5,454,232,30,3,10 };
  //堆排序
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  int i = 0;
  for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  {
    //把数组里面的元素取出来
    printf("%d ",a[i]);
  }
  printf("\n");
}

3.2.3 建堆时间复杂度因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

</div>
    
    <div id="asideoffset"></div>