归并排序中的递归思想理解

gzh_kevin

于 2019-06-28 22:38:08 发布

阅读量2k

点赞数 2

分类专栏：算法

本文链接：https://blog.csdn.net/kai123wen/article/details/94053027

版权

本文探讨了归并排序中的双递归思想，通过实例解析如何将无序数组逐步归并成有序。重点在于理解双递归如何在归并过程中形成递归树，并通过深度优先遍历来实现排序。通过对递归树的分析，详细阐述了从根节点到叶节点的划分、合并过程，从而帮助读者深入理解归并排序的工作原理。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

在这里插入图片描述

这是我自己理解的利用归并排序对一个无序数组进行排序的简单过程。
图中的波浪线就是每次执递归的时机。

在我学习这个算法的时候遇到的困难：

为什么使用的是双递归？

这个原因在我认为是：因为归并过程是将两个数组进行归并，那么去哪里找这两个数组呢？就是通过双递归。这里比较重要的就是双递归了，什么是双递归呢？其实我们之前很早接触过双递归：斐波那契数列：
下面是我自己的一点理解，可能解释的有点繁琐，但是大体是正确的。等我有更深的理解后再来更新。

	public void sort(int array[],int start,int end,int temp[]) {
		if(start < end) {
			int mid = (start+end)/2;
			sort(array,start,mid,temp);
			sort(array,mid+1,end,temp);
			merge(array,start,mid,end,temp);
		}
	}

我理解的双递归：过程类似一个递归树，类似于二叉树深度优先遍历中序遍历（虽然一个是生成二叉树，一个是遍历二叉树）。首先根结点是1 3 5 10 4 9 ，（接下来我们只看递归树右边一部分），&#x