• 热门专题

数据结构记录 排序

作者:  发布日期:2016-01-05 19:28:46
Tag标签:数据结构  
Home Web Board ProblemSet Standing Status Statistics

Problem J: 排序

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 482 Solved: 206
[Submit][Status][Web Board]

Description

请分别应用堆排序方法(大顶堆)和归并排序方法实现一组非常大的数据的递增排序,分别输出每次堆整序之后对应的堆顶的值和每次归并之后的局部序列。(考查堆排序算法和归并排序算法)

Input

第一行输入为n(0 <= n <= 10000)为n个要排序的数字;
接下来输入一行,包括n个要排序的数字,保证所有的数字都在int范围内。

Output

前n行每行输出一次堆整序后堆顶的值(初建堆的堆顶元素在第一个输出,之后n - 1行每行输出一次堆整序后堆顶元素的值)。
接下来输出每一次归并后的局部序列,具体内容见输出样例。

Sample Input

55 4 3 2 1

Sample Output

54321[1, 1]: 5[2, 2]: 4[1, 2]: 4 5[3, 3]: 3[1, 3]: 3 4 5[4, 4]: 2[5, 5]: 1[4, 5]: 1 2[1, 5]: 1 2 3 4 5

HINT

Append Code

[Submit][Status][Web Board]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxsize 10005
using namespace std;
static int H[maxsize],M[maxsize],c[maxsize],num[maxsize];
void HeapAdjust(int List[],int s,int m);
void HeapSort(int List[],int n);

void HeapAdjust(int List[],int s,int m)
{
    int r=List[s];
    int i=2*s;
    while(i<=m)
    {
        if(i<m&&List[i]<List[i+1])
        {
            ++i;
        }
        if(r>=List[i])
        {
            break;
        }
        List[s]=List[i];
        s=i;
        i*=2;
    }
    List[s]=r;
}
void CreatHeap(int List[],int n)
{
    int i=n/2;
    while(i!=0)
    {
        HeapAdjust(List,i,n);
        i--;
    }
}

void Msort(int array[],int l,int h)
{
    if(l!=h)
    {
        int m=(l+h)/2;
        int f=l;
        int F=m+1;
        int s=h;

        Msort(array,f,m);
        Msort(array,m+1,s);

        int k=l;
        int ans=f;
        int Ans=F;

        while(ans<=m&&Ans<=s)
        {
            if(array[ans]<array[Ans])
            {
                num[k++]=array[ans++];
            }
            else
            {
                num[k++]=array[Ans++];
            }
        }

        while(ans<=m)
        {
            num[k++]=array[ans++];
        }

        while(Ans<=s)
        {
            num[k++]=array[Ans++];
        }

        int x=l;
        while(x<=h)
        {
            array[x]=num[x];
            x++;
        }
    }

    int y=l;
    printf("[%d, %d]:",l+1,h+1);
    while(y<=h)
    {
        printf(" %d",array[y]);
        y++;
    }
    cout<<endl;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&H[i]);
            M[i]=H[i];
        }
        int i=n/2;
        while(i>=0)
        {
            HeapAdjust(H,i,n);
            i--;
        }
        printf("%d\n",H[0]);
        int j=n-1;
        while(j>=1)
        {
            int temp=H[0];
            H[0]=H[j];
            H[j]=temp;
            HeapAdjust(H,0,j-1);
            printf("%d\n",H[0]);
            j--;
        }
        Msort(M,0,n-1);
    }
    return 0;
}

延伸阅读:

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规