常用算法-堆排序

堆排序

时间复杂度：O(Nlog2N)
空间复杂度：O(N)
原理：
构造一个大根堆，大根堆的顶端数为最大数，映射成数组，将首段位置与末端位置交换，剩余数组依次构建大根堆找出最大值
将待排序序列构造成一个大顶堆
此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
核心代码：
void sort()
{
for(i = n;n>0;i–)
{
bigHeap(i)；
swap(a[0],a[i-1]);
}
}
void bigHeap(int count)
{
for(int i = (count/2-1);i>=0;i–)
{
if((2i+1)<count && a[2i+1] > a[i]) swap(a[2i+1],a[i]);
if((2i+2)<count && a[2i+2] > a[i]) swap(a[2i+2],a[i]);
}
}