归并排序(递归代码)

#includestdio.h#includestdlib.h// 归并排序非原地排序、稳定排序// 时间复杂度 O(nlogn)void merge_sort(int a[],int l,int r){// 对数组 a 的 [l,r] 区间进行归并排序// 递归终止条件// 当区间内只有一个元素或没有元素时无需排序if(lr)return;// 求中点int mid(lr)/2; // l~~~mid mid1~~r// 递归排序左半部分merge_sort(a,l,mid);// 递归排序右半部分merge_sort(a,mid1,r);// 将两个有序区间合并int il; // 指向左区间起点int jmid1; // 指向右区间起点int t[105]; // 临时数组存放合并结果int k0; // t数组下标// 同时扫描两个区间while(imidjr){if(a[i]a[j]){// 左边元素较小放入临时数组t[k]a[i];i;}else{// 右边元素较小放入临时数组t[k]a[j];j;}}// 左区间剩余元素直接复制while(imid){t[k]a[i];i;}// 右区间剩余元素直接复制while(jr){t[k]a[j];j;}// 此时两个有序区间已经全部合并到 t 中// 将 t 中的数据复制回原数组对应位置for(i0;ik;i){a[li]t[i];}}int main(){int n,a[105];// 输入元素个数scanf(%d,n);// 输入数组元素// 本程序采用 1~n 下标存储for(int i1;in;i){scanf(%d,a[i]);}// 调用归并排序merge_sort(a,1,n);// 输出排序结果for(int i1;in;i){printf(%d ,a[i]);}printf(\n);}