蓝桥杯算法基础（14）：十大排序算法（归并排序）c语言版

归并排序

基于分而治之的思想，拿两个已经有序的序列重新组合成一个新的有序序列.

这是一个简单的合并函数，需要两个序列都有序

//默认a和b数组都是有序的
//temp为一个数组的首地址
void mergeSort(int a[],int,alen,int b[],int blen,int* temp){int i=0;int j=0;int k=0;while(i<alenj<blen){if(a[i]<b[j])//比大小，谁小先放谁在前{temp[k]=a[i];k++;i++;}else{temp[k]=b[j];k++;j++;}}while(i<alen){temp[k]=a[i];k++;//若是一方走完，还有一方剩下了，并且有序，那就意味着剩下的有序序列都比已经合并的最大的大，依次将剩余的数放到其中就行i++;}while(j<blen){temp[k]=b[j];k++;j++;}}

简洁一下代码

void mergeSort(int a[],int,alen,int b[],int blen,int* temp){int i=0;int j=0;int k=0;while(i<alenj<blen)temp[k++]=a[i]<b[j]?a[i++]:b[j++];while(i<alen)temp[k++]=a[i++];while(j<blen)temp[k++]=b[j++];}

最终版

//合并函数
//merge用于合并
void merge(int arr[],int low.int mid,int height,int* temp){//low~mid，mid+1~height分别为合并的两组int i=low;int j=mid+1;int k=low;while(i<=mid&&j<=height)temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];while(i<=mid)temp[k++]=arr[i++];while(j<=height)temp[k++]=arr[j++];for(i=low;i<=height;i++)arr[i]=temp[i];
}//归并法，用的是分治思想，先分后治
//merge_sort用于分割
void merge_sort(int arr[],int low,int height,int *temp){//取中间位置，设为mid//low~mid为一组，mid+1~height为一组//依次以每组边界带入递归，继续分割，//直到每组只剩一个数，然后递归开始返回，//从底层开始，最终到两个有序的序列，//再将两个有序的序列合并，即得到最终排好序的序列if(low>=height)return;int mid=low+(height-low)>>1;merge_sort(arr,low,mid,temp);merge_sort(arr,mid+1,height,temp);merge(arr,low,mid,height,temp);}//mergeSort会和merge_sort和merge,并开辟temp空间
void mergeSort(int arr[],int length){int *temp=(int *)malloc(sizeof(int)*length);//向内存开辟一个length长度，sizeof(int)*length大小的空间assert(temp);//断言assert，是一个调试程序时经常使用得宏，在程序运行时，计算括号内的表达式，如果为false(0),程序将报告错误，并终止执行，若不为零，继续执行后面的语句。
//主要用于判断，是否出现了非法数据merge_sort(arr,0.length-1,temp);free(temp);//free与malloc搭配使用，一个用于开辟空间，一个用于释放空间
}