首页 > 代码库 > 我实现的第一个算法----归并排序

我实现的第一个算法----归并排序

今天听了卜东坡老师的算法课,讲的是归并算法,那个动画演示,终于让我开窍了,于是乎,赶紧今天就编了个C++的程序。我知道可能这个程序还比较粗糙,但是这是第一次实现了算法导论上的东东,心里那个激动啊,,,哎,我也终于能实现个算法了,以前总认为自己很菜,其实真的很菜,,,算了,直接上程序吧,,,

#include<iostream>using namespace std;int a[100];int flag;int n;void vector_initial();void print_vector();void MERGE_sort(int p,int r);void MERGE_combine(int p,int q,int r);int main(){        vector_initial();    if(n==0)        return 0;    MERGE_sort(0,n);    print_vector();    return 0;}void vector_initial(){    int i=0;    cin>>a[i];    while(a[i]!=-1)    {        i++;        cin>>a[i];    }    n=i-1;}void print_vector(){for(int i=0;i<n;i++)    cout<<a[i]<<" ";cout<<a[n]<<endl;}void MERGE_sort(int p,int r)//归并排序{    int q;    if(p<r)    {        q=(p+r)/2;        MERGE_sort(p,q);        MERGE_sort(q+1,r);        MERGE_combine(p,q,r);    }}void MERGE_combine(int p,int q,int r){    int L[100];    int R[100];    int n1=q-p+1;    int n2=r-q;    for(int i=1;i<=n1;i++)        L[i]=a[p+i-1];    for(int j=1;j<=n2;j++)        R[j]=a[q+j];    L[n1+1]=10000;    R[n2+1]=10000;    i=1;j=1;    for (int k=p;k<=r;k++)    {        if(L[i]<=R[j])        {            a[k]=L[i];            i++;        }        else        {            a[k]=R[j];            j++;        }    }}

 

我实现的第一个算法----归并排序