归并排序算法(C语言实现)_c语言归并排序算法代码

归并排序的步骤：
1.将序列分成左右两部分
2.排序左序列，排序右序列
3.合并两个有序的序列
需要申请额外的空间放临时的有序序列

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
void merge(char *str,char *tmpstr,int start,int mid,int end)
{
    int i=start,j=mid+1,k=start;
    while(i!=mid+1 && j!=end+1)
    {
        if(str[i] <= str[j])
        {
            //当左边的元素小于右边的元素，则将左边的元素存放在临时的序列
            tmpstr[k++] = str[i++];
        }
        else
        {
            //当右边的元素小于左边的元素，则将右边的元素存放在临时的序列
            tmpstr[k++] = str[j++];
        }
    }
    //直到左边的序列遍历完成，或者右边的序列遍历完成，剩余的元素，也按照序号存放在临时序列中
    while(i != mid+1)
    {
        tmpstr[k++] = str[i++];
    }
    while(j != end+1)
    {
        tmpstr[k++] = str[j++];
    }
    //临时序列已经时有序的了，原始序列逐个元素代替即可
    for(i=start;i<=end;i++)
       str[i] = tmpstr[i];
}
 
void msort(char *str,char *tmpstr,int start,int end)
{
    int mid;
    if(start < end)
    {
        mid = start + (end - start)/2;
        msort(str,tmpstr,start,mid);  //排序左边序列
        msort(str,tmpstr,mid+1,end);  //排序右边序列
        merge(str,tmpstr,start,mid,end);//合并两个有序的序列
    }
}
 
int main(int argc,char *argv[])
{
    char str[]="ascdshhdfc";
    char *tmpstr = NULL;
    tmpstr = malloc(strlen(str)*sizeof(char));
    printf("srcstr:%s.\n",str);
    msort(str,tmpstr,0,strlen(str)-1);
    printf("dststr:%s.\n",str);
    free(tmpstr);  
}

上述代码执行的结果：