摘要:代码解析自见文中慢慢理解细细入深开辟分配一个辅助临时数组开辟成功之后实现归并之前的划分数组步骤利用之后立刻释放空间开辟失败每一次找中间值依次划分递归划分后左边的新一块递归划分后右边的一块合并已划分排序好的数组一直为标记左半区第一个未排序
代码解析 自见文中
慢慢理解 细细入深
#include#includevoid 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;}
祝你好运
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/121847.html
摘要:两个单元素数组的合并实际就是对这两个数进行了排序,即变为,同样再对后一组的两个数归并排序,即变为,再将两单元数组归并成四单元数组即和归并为。 前言 本周讲解两个50多年前发明,但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序,几乎每个软件系统中都可以找到其中一个或两个的实现,并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...
摘要:排序之归并排序简介归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则成为二路合并。对于一个原始的待排序数列,往往可以通过分割的方法来归结为多路合并排序。 Java排序之归并排序 1. 简介 归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则成为二路合并。对于一个原始的待排序数列,往往可以通过分割的方法来归结为多路合...
阅读 2949·2023-04-25 18:00
阅读 2195·2021-11-23 10:07
阅读 3993·2021-11-22 09:34
阅读 1206·2021-10-08 10:05
阅读 1558·2019-08-30 15:55
阅读 3337·2019-08-30 11:21
阅读 3282·2019-08-29 13:01
阅读 1336·2019-08-26 18:26