黑马程序员技术交流社区

标题: 以前写过的归并排序 分享下 [打印本页]

---

作者: 夏沫的黄昏′    时间: 2014-5-29 14:38
标题: 以前写过的归并排序 分享下

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

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

分享下 曾经写过的

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

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

---

作者: 251638256    时间: 2014-5-29 17:14
:L厉害:L厉害:L厉害:L厉害

---

作者: 夏沫的黄昏′    时间: 2014-5-29 17:59

251638256 发表于 2014-5-29 17:14
厉害厉害厉害厉害

:P我是搞算法的

---

作者: mingjixiaohui    时间: 2014-5-29 20:58
将集合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);
}

---

作者: 斑马    时间: 2014-5-29 22:47
谢谢楼主分享～～

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2