C++习题-堆排序

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;
}

输入:

输入n和n个整数

输出:

从小到大输出

示例输入:

10
2 1 3 4 6 5 7 9 8 10

示例输出:

1 2 3 4 5 6 7 8 9 10 

提示:

参考答案(内存最优[1096]):

#include <stdio.h>
int main()
{
    int i=0,d;
    int a[1001],b,c;
    scanf("%d",&c);
    for(i=0; i<c; i++)scanf("%d",&a[i]);
    for(i=0; i<c-1; i++)
        for(d=0; d<c-i-1; d++)
            if(a[d]>a[d+1])
            {
                b=a[d+1];
                a[d+1]=a[d];
                a[d]=b;
            }
    for(i=0; i<c; i++)printf("%d ",a[i]);
    return 0;
}

参考答案(时间最优[0]):


#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++;
        if (t<a[k])
        {
            a[i]=a[k];
            i=k;
            k=2*i+1;
        }
        else 
            break;            
    }
    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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注