【数据结构】堆排序（C代码实现 码源）

//向上调整，从child开始向上调整
void AdjustUp(HPDataType* a,int child) {
  int parent = (child - 1) / 2;
  while (child>0) {
    if (a[child] > a[parent]) {
      Swap(&a[child], &a[parent]);    //Swap(a[child], a[parent]);  
                                        //传过去的只是a[child]和a[parent]的值，该函数也只是拿形参接收，对原数组并没有产生实质性的影响
                                      //传过去的是地址
      child = parent;
      parent = (parent - 1) / 2;
    }           
    else {
      break;
    }
  }
}

void AdjustDown(HPDataType* a,int n,int parent) {
  assert(a);
  int child = parent * 2 + 1;
  while (child < n)
  {   
        //判断左右孩子节点 哪个更大 更大的上调
      //先判断右孩是否存在
      if (child + 1 < n && a[child + 1] > a[child]) {
     ++child;
      }
    if (a[child]>a[parent]) {
      Swap(&a[child], &a[parent]);
      // 继续往下调整
      parent = child;
        child = parent * 2 + 1;
    }
    else {
      break;
    }
  }
}

//传入堆结构基础——数组，数组大小是判断遍历结束的条件
void HeapSort(HPDataType* a,int n) {
  //升序——建大堆
  //降序——建小堆
  // 建堆--向上调整建堆
  for (int i = 1; i < n; i++) {
    AdjustUp(a,i);
  }
  //建大堆、小堆用AdjustUP和AdjustDown其实都可以，且不管是从前往后遍历还是从后往前遍历
  // 那么就得 建大、小堆时候改变一下a[parent]和a[child]之间的关系
  //对比AdjustUP和AdjustDown之间，Adjustdown的时间复杂度更低，效率更高
  //建堆--向下调整建堆 --O(N)
  for (int i = (n - 1) - 1 / 2; i > 0; i--) {
    AdjustDown(a,n,i);
  }
    //排序
  //升序——建大堆（这里以升序为例）
  //降序——建小堆
  int end = n - 1;
  while (end>0)
  {   
    //max换到最后
    Swap(&a[0],&a[end]);
    --end;   //让它不动，处理剩下的
    //再找到 次max的数 ——重找大堆（不会像直接删除堆顶那样，需要重建堆）
    AdjustDown(a,end,0);
  }
}