C++习题-堆排序

时间： 1ms 内存：128M

描述：

1.堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构，并同时满足堆性质：即孩子节点的键值或索引总是小于（或者大于）它的父节点。（假定一组数据的第n(n>=0)个数是一个父节点，那么对应第2n+1和第2n+2个数便是它的孩子节点,孩子节点最多两个）
2.堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(此为构建大顶堆方法，)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；（构建方法：从左到右选择一组数中最后一个有孩子节点的父节点数，让它与孩子比较，与最大的孩子互换位置，如果父节点最大，就不用换。这个执行完以后，以此父节点原来的位置为准，向左取父节点执行一样的操作，直到取的父节点到达没有可交换的孩子节点的位置为止；依次取父节点执行操作直到左边第一位，此时无序区（R[1,2,3......n]）构建完毕）
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];（此时的R[n]为已确定的最大值，将它单独拿出来即可）
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，（调堆方法：从左边第一个数开始，将它和自己的孩子节点比较，与较大的孩子互换位置，如果它本身最大，就不用换。此数到达新位置，再和新的孩子节点比较互换，重复执行直到这个数没有可以交换位置的孩子节点为止。再选取左边第二个数，重复执行上述操作。执行到最后一个有孩子节点的数为止，调堆完毕。）然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

#include<iostream>
using namespace std;
void HeapAdjust(int a[],int i,int m)//排列成“堆”的形式
{
    int k,t;
    t=a[i];     //保存处理元素
    k=2*i+1;    //左孩子
    while (k<m) //处理父亲元素
    {
        if ((k<m-1)&&(a[k]<a[k+1])) //取较大的孩子节点
            k++;
///////////////////////////////////////////////////////////////////
        /*
         请在该部分填写缺少的代码
        */
////////////////////////////////////////////////////////////////////
    }
    a[i]=t;
}
void HeapSort(int a[], int n) //堆排序函数
{
    int i,k;
    for (i=n/2-1; i>=0; i--)
        HeapAdjust(a,i,n);//处理后，a[i]是这个数组后半部分的最大值
    for (i=n-1; i>=1; i--)
    {
        k=a[0]; //把剩下元素中最大的那个放到结尾，下一次只要排剩下的数就可以
        a[0]=a[i];
        a[i]=k;
        HeapAdjust(a,0,i);
    }
}
int main()
{
    int a[100],i,n;
    cin>>n;
    for(i=0; i<n; i++)
        cin>>a[i];
    HeapSort(a,n);
    for(i=0; i<n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}