欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 国际 > 归并排序(C语言)

归并排序(C语言)

2024/11/17 12:17:09 来源:https://blog.csdn.net/N_N12/article/details/143804177  浏览:    关键词:归并排序(C语言)

归并排序的基本思想:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

一、步骤

1.首先,建立一个随机数组,如:以该数组为例

2.采用分治的思想对数组中的元素进行比较,将数组一份为二,midi = (left + right) / 2,分为[left,midi] [midi + 1,right]

3.重复第二步采用递归算法往深处递归,直到数组中只包含一个元素(不包含数组不存在的情况),故递归的结束条件是left == right

4.然后函数返回到上一层,对两个数进行比较,然后按照顺序插入临时数组tmp

5.当tmp数组有序时,拷贝到原数组中结束

归并排序的思想和二叉树的后序遍历类似

图片详述:

二、代码

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin == end){return;}int midi = (begin + end) / 2;//[begin,midi] [midi+1,end],一个数组一分为二_MergeSort(a, begin, midi, tmp);_MergeSort(a, midi + 1, end, tmp); //后序遍历递归int begin1 = begin, end1 = midi; //第一个数组int begin2 = midi + 1, end2 = end; //第二个数组int i = 0;while (begin1 <= end1 && begin2 <= end2) //只要有一个数组为空就结束{if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1) //第一个数组不为空,插入到第二个数组后面{tmp[i++] = a[begin1++];}while (begin2 <= end2) //第二个数组不为空,插入到第一个数组后面{tmp[i++] = a[begin2++];}memcpy(a + begin, tmp, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp); //由于tmp是malloc出来的,因此要建立一个子函数来递归,避免每一层都需要mallocfree(tmp);
}

若看不懂,可以画图,一层一层的调试

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com