A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 夏沫的黄昏′ 中级黑马   /  2014-5-29 14:38  /  1589 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

昨天看到有人问排序的问题了,

个人感觉归并排序是比较强大的 适用于很多情况

分享下 曾经写过的

归并排序: 以分治为主要思想 不断二分, 两个相邻的 数组进行归并 得出最小步数。

#include<cstdio>

#include<cstring>


long long a[500010],b[500010],num;


long long merge_sort(long long *A,int x,int y,long long *T)
{
    if(y-x>1)
    {
        int m = (x+y)/2;
        int p = x,q = m,i = x;
        merge_sort(A,x,m,T);
        merge_sort(A,m,y,T);
        int ps=x;
        while(p<m||q<y)
        {


            if(q>=y||(p<m&&A[p]<=A[q]))
                T[i++] = A[p++],ps++;
            else
            {
                num+=m-p;
                //printf("%d.%d.%d.\n",num,A[p],A[q]);
                T[i++] = A[q++];
            }
        }
        for(int i = x; i < y; i++)
            A = T;
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        for(int i = 0; i < n; i++)
            scanf("%lld",&a);
        num=0;
        memset(b,0,sizeof(b));
        merge_sort(a,0,n,b);
        printf("%lld\n",num);
    }
    return 0;
}

4 个回复

倒序浏览
:L厉害:L厉害:L厉害:L厉害
回复 使用道具 举报
251638256 发表于 2014-5-29 17:14
厉害厉害厉害厉害

:P我是搞算法的
回复 使用道具 举报
将集合LA和集合LB归并到LC中(按非递减,或非递增顺序)
int mian(){
int i=1,j=1,k=0;//k表示LC表的长度(LC为0的空表)
for(;i<=lengthLA,j<=lengthLB;i++,j++,k++)//k++表示表长加1
    if(getchar(i)<=getchar(j))//位序为i的元素和位序为j的元素进行比较
   (k+1)=getchar(i);//k+1表示表尾,将位序为i的元素放到LC的表尾
        else
        (k+1)=getchar(j);//k+1表示表尾,将位序为j的元素放到LC的表尾
     

//如果LB执行完后将LA余下的元素放到LC的表尾
for(;i<=lengthLA;k++,i++)
k+1=getchar(i);
//如果LA执行完后将LB余下的元素放到LC的表尾
for(;j<=lengthLA;k++,j++)
k+1=getchar(j);
}
回复 使用道具 举报
谢谢楼主分享~~
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马