排序算法之堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构（通常堆是通过一维数组来实现的），并同时满足堆的性质：即子结点的键值总是小于（或者大于）它的父节点。

我们可以很容易的定义堆排序的过程：

1.创建一个堆

2.把堆顶元素(最大值)和堆尾元素互换

3.把堆的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整

4.重复步骤2，直到堆的尺寸为1

分类--------------内部比较排序

数据结构----------数组

最差时间复杂度---- O(nlogn)

最优时间复杂度---- O(nlogn)

平均时间复杂度---- O(nlogn)

所需辅助空间------ O(1)

稳定性------------不稳定

#include

usingnamespacestd;

intheapsize;//堆大小

voidexchange(intA[],inti,intj)//交换A[i]和A[j]

{

inttemp = A[i];

A[i] = A[j];

A[j] = temp;

}

voidheapify(intA[],inti)//堆调整函数(这里使用的是最大堆)

{

intleftchild =2* i +1;//左孩子索引

intrightchild =2* i +2;//右孩子索引

intlargest;//选出当前结点与左右孩子之中的最大值

if(leftchild A[i])

largest = leftchild;

else

largest = i;

if(rightchild A[largest])

largest = rightchild;

if(largest != i)

{

exchange(A, i, largest);//把当前结点和它的最大(直接)子节点进行交换

heapify(A, largest);//递归调用，继续从当前结点向下进行堆调整

}

}

voidbuildheap(intA[],intn)//建堆函数

{

heapsize= n;

for(inti =heapsize/2-1; i >=0; i--)//对每一个非叶结点

heapify(A, i);//不断的堆调整

}

voidheapsort(intA[],intn)

{

buildheap(A, n);

for(inti = n -1; i >=1; i--)

{

exchange(A,0, i);//将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)

heapsize--;//从堆中去掉最后一个元素

heapify(A,0);//从新的堆顶元素开始进行堆调整

}

}

intmain()

{

intA[] = {5,2,9,4,7,6,1,3,8};//从小到大堆排序

intn =sizeof(A) /sizeof(int);

heapsort(A, n);

printf("堆排序结果：");

for(inti =0; i < n; i++)

{

printf("%d ", A[i]);

}

printf("\n");

return0;

}