归并排序

排序算法之—二路归并排序

//归并排序：
#include<stdio.h>
#include<stdlib.h>
/*先写将两个有序表合并为一个有序表的算法merge（）
设两个有序表放在同一个数组中相邻的位置上R[lwo...mid],R[mid+1...high]
先将他们合并到一个暂时的数组R1中，待合并完成后复制回R中。
每次从两个段中取出一个关键字比较，较小的放入R1，若哪一段有剩余，则直接复制进R1
再复制回R
*/
void Merge(int R[],int low,int mid,int high)//归并两个有序数组
{
    int *R1;//变长临时数组
    int i=low ,j=mid+1, k=0;//k是R1的下标，i，j是两段的下标
    R1=(int*)malloc((high-low+1)*sizeof(int));//动态分配空间
    while(i<=mid &&j<=high)//两段都没有扫描完时执行循环
    {
        if(R[i] <= R[j])//若第一段的小则将第一段的元素放到R1中
        {
            R1[k]=R[i];
            i++;
            k++;
        }
        else
        {
            R1[k]=R[j];
            j++;
            k++;
        }
    }
    while(i<=mid)//第一段没有扫描完
    {
        R1[k]=R[i];//第1段剩下的复制到R1
        i++;k++;
    }
    while(j<=high)//第2段没有扫描完
    {
        R1[k]=R[j];//第二段剩下的复制到R1
        j++;k++;
    }
    for(k=0,i=low;i<=high;k++,i++)//把R1复制到R中去
    {
        R[i]=R1[k];
    }
    free(R1);


}

void MergeSortDC(int R[],int low,int high)//对R【low。。high】进行递归归并排序
{
    int mid;
    if(low<high)
    {
        mid=(low+high)/2;
        MergeSortDC(R,low,mid);
        MergeSortDC(R,mid+1,high);
        Merge(R,low,mid,high);
    }
}
void Mergesot1(int R[],int n)//传一个数组R,有n个元素,便于调用
{
    MergeSortDC(R,0,n-1);
}

void disp(int R[],int n)
{
    int i=0;
    for( i=0;i<n;i++)
    {
        printf("%d ",R[i]);
    }
    printf("\n\n");
}
int main()
{
int R[6]={1,9,3,0,2,5};
Mergesot1(R,6);
disp(R,6);
}