归并排序有多简单?一幅图教你看懂【C语言】
【摘要】 归并排序的递归实现代码实现归并排序的非递归实现代码实现归并排序的思想很简单——分治法。简单地说,归并排序的是将序列拆分成几段子序列,将每一段子序列分别进行排序,排好之后再将有序的子序列归并(有点像合并两个有序数组)成为一个有序的序列。
目录
归并排序的思想很简单——分治法。简单地说,归并排序的是将序列拆分成几段子序列,将每一段子序列分别进行排序,排好之后再将有序的子序列归并(有点像合并两个有序数组)成为一个有序的序列。
例如要排序数列:10、6、7、1、3、9、4、2;
将序列拆分为 2 个子序列;
继续拆分;
继续拆分;
至此,每个子序列的长度都为 1 ,因为只有一个数,所以可认为是有序序列;
现将子序列两两归并,即合并两个有序序列;
继续归并;
继续归并;
以上就是归并排序的整个过程,很显然归并排序的实现应该离不开递归的思想。
归并排序的递归实现
归并排序的递归实现较为简单,需要注意的有两点:
1. 归并的过程并非在原数组上直接改动,而是开辟一个临时数组,在临时数组上进行排序,排好之后将临时数组的内容全部拷贝到原数组;
2. 代码中使用的是二路归并(如上图所示,每次将序列拆分为两个子序列)。
代码实现
归并排序的非递归实现
非递归与递归作用思想基本相同。递归实现时,因为拆分序列时采用的是递归的方式,所以通过传递参数就可以控制子序列的长度。但是非递归不行,非递归通过变量 rangeN 来控制序列的长度(或间隔),每次让 rangeN *= 2 例如:
但是由于 rangeN 每次都 *2 ,而我们排序的序列长度不可能总是 2 的倍数,所以 可能会有数组越界访问的风险。例如:
现将两个子序列归并,并将数据拷贝回原数组时,就会发生越界:
当然这只是其中一种越界的可能情况——第二段序列发生越界,原因是右边界 end2 大于 n;
实际操作中,一共会有三种情况导致越界:
两段序列的区间分别为: [begin1,end1] [begin2,end2]
1. end1 > n;
2. begin > n;
3.end2 > n;
所以,当这三种情况发生时,需要修正区间,以上述用例为例, end2 大于 n 时,令 end2 = n-1即可;
代码实现
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)