堆排序的基本思想及步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

1. 构建初始堆（升序建大堆，降序建小堆）
   a.给定一个无序数组：
   
   b.创建一个大堆
   

2. 将根节点与最后一个叶子节点进行交换，然后堆尾减1，重新构建大堆，重复上述操作直至有序
   
   最后结果：
   

算法如下：

void AdjustDown(DataType* a, size_t n, int parent)//向下调整
{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(DataType* a, size_t n)//堆排序，升序，建大堆
{assert(a);for (int i = (n - 2) / 2; i >= 0; i--)//i定义为int ,不能定义为size_t,否则死循环，{                       //n为元素个数，不是最后一个元素的下表，所以用（n-2）/2AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);//从堆顶开始向下调整，因为有一半已经有序--end;}
}
void TestHeapSort()
{DataType a[] = { 4, 6, 8, 5, 9 };HeapSort(a, sizeof(a) / sizeof(DataType));PrintfBuff(a, sizeof(a) / sizeof(DataType));
}

时间复杂度

N*logN