堆排序步骤+算法

堆可以看作一棵完全二叉树，利用一维数组将数据元素按照完全二叉树的形式，从上到下，从左到右，依次存放。若任何一个双亲结点值都比其左右孩子的值大，则称为大顶堆；反之称为小顶推。

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

执行步骤：

初始序列：1，9，2，6，8，5
①初始建堆：
先将序列调整为一个大顶堆，初始序列对应的完全二叉树及调整过程如下图：

在上图中这个完全二叉树中，6，8，5是叶子结点，没有左右孩子，满足堆的定义。从2开始，按照2，9，1的顺序依次进行调整，即n/2，(n/2)-1,(n/2)-2……，值取下限进行调整，n为数据元素个数。
②进行排序：
将建好的大顶堆中的堆顶元素9和最后一个元素2进行交换，这样就把最大值输出，第一趟排序完成。9到达其最终位置。将除了9之外的剩余元素2，8，5，6，1重新调整为大顶堆。然后将次大的值输出。这样反复的调整和输出，最终把元素按其序列从小到大顺序排好了。排序过程及最终结果如下图所示：

③堆排序算法程序：

void heapAdjust(int R[ ]),int low,int high)

{

int i=low,j=2*i;//R[j]是R[i]的左孩子结点
int temp=R[i];
while(j<=high)

{

if(j<high&&R[j]<R[j+1]) //若右孩子比较大，则把j指向右孩子
{
++j;
}

if(temp<R[j])

{

R[i]=R[j]; //将R[j]调整到双亲结点的位置上
i=j; //修改i和j的值，以便能继续调整 j=2*i;

}

else
{

break; //调整结束
}

}

R[i]=temp;//被调整结点的值放入最终位置

}

/*堆排序函数*/

void heapSort(int R[],int n)
{

int i,temp;
for(i=n/2;i>=1;–i ) //建立初始堆
{

heapAdjust(R,i,n);
}
for(i=n;i>=2;–i)//进行n-1次循环，完成堆排序
{
/*以下3句换出了根结点中的关键字，将其放入最终位置*/
temp=R[1];
R[1]=R[i];
R[i]=temp;
heapAdjust(R,1,i-1); //在减少了1个关键字的无序序列中进行调整

}

}