归并排序的步骤：
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); }
上述代码执行的结果：
