堆排序
堆排序
(Heapsort)
是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
直接选择排序的特性总结：
1.
堆排序使用堆来选数，效率就高了很多。
2.
时间复杂度：
O(N*logN)
3.
空间复杂度：
O(1)
4.
稳定性：不稳定
比希尔排序效率更好
1.建堆
2.排序
堆顶元素与最后一个元素交换，向下调整，最后一个元素不看做堆里的数据，下标减一
升序建大堆
降序建小堆
void AdjustDown(int* a, int 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(int* a, int n)
{
// 建大堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
