代码解析 自见文中
慢慢理解 细细入深
#include#include void Print(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d", arr[i]); } } void merge_sort(int arr[],int sz) { //开辟分配一个辅助临时数组 int* temparr = (int*)mallco(sz * sizeof(int)); if (temparr) { //开辟成功之后 实现归并之前的划分数组步骤 msort(arr,temparr, 0, sz - 1); //利用之后 立刻释放空间 free(temparr); } else//开辟失败 { printf("error:failed to allocate memory"); } } void msort(int arr[],int temparr[] ,int left, int right) { int mid = (left + right) / 2;//每一次找中间值 依次划分 if(left <= right) { msort(arr,temparr, left,mid);//递归划分后左边的新一块 msort(arr,temparr, mid + 1, right);//递归划分后右边的一块 merge(arr, temparr, left, right, mid);//合并已划分排序好的数组 } } void merge(int arr[], int temparr[], int left, int right, int mid) { //left一直为0 int L_pos = left;//标记左半区第一个未排序的数字 int R_pos = right;//标记右半区第一个未排序的数字 int pos = left;//临时数组的下标 while (L_pos <= mid && R_pos <= right) { //每次分别把左右半区的第一个元素拿出来进行比较大小 if (arr[L_pos] > arr[R_pos]) { temparr[pos] = arr[R_pos]; pos++; R_pos++; } else { temparr[pos] = arr[L_pos]; pos++; L_pos++; } } //当左半区排完之后 右半区剩余依次放进去 while (L_pos <= mid) { temparr[pos] = arr[L_pos]; pos++; L_pos++; } //同理可得 while (R_pos <= right) { temparr[pos] = arr[R_pos]; pos++; R_pos++; } //把临时数组合并后的元素放到原来的数组 while (left <= right) { //left在这同样初始为0开始 arr[left] = temparr[left]; left++; } } int main() { int arr[] = { 9,5,2,7,12,4,3,1,11 }; int sz = sizeof(arr) / sizeof(arr[0]); Print(arr, sz); printf("n"); merge_sort(arr,sz); Print(arr, sz); return 0; }
祝你好运
