归并排序递归法和非递归法的简单简单介绍

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

归并排序核心步骤：先将数组分组，往下分直到分为1个数据，然后开始合并，两两合并，合并的时候先比较两组数据中的数据的大小，按顺序依次合并到临时数组temp中，然后再将合并到temp数组中有序的数据覆盖到原数组中。

#include <stdio.h>
// 归并排序
// 时间复杂度O(N*logN)
// 空间复杂度O(N)
void _MergeSort(int* arr, int left, int right, int* temp)
{
	if (left >= right)
		return;
    
    // 递归划分区间，直到区间内只有一个数据后开始归并
	int mid = (left + right) / 2;
	// [left,mid] [mid+1,right]
	_MergeSort(arr, left, mid, temp);
	_MergeSort(arr, mid+1, right, temp);

	// 归并[left,mid] [mid+1,right]有序,归并到temp了
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			temp[index++] = arr[begin1++];
		else
			temp[index++] = arr[begin2++];
	}

	// 可能有一段没结束，具体那一段不知道，只有一个循环可以进入
	while(begin1<=end1)
		temp[index++] = arr[begin1++];

	while (begin2 <= end2)
		temp[index++] = arr[begin2++];

	// 将归并后在temp的数据拷贝回原数组
	for (int i = left;i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

// 归并排序
void MergeSort(int* arr, int n)
{
	assert(arr);
	int* temp = malloc(sizeof(int) * n);
	
	// 传入闭区间【0，n-1】
	_MergeSort(arr, 0, n - 1, temp);

	free(temp);
}

void TestMergeSort()
{
	int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };
	MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}

void TestMergeSortNonR()
{
	int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };
	MergeSortNonR(arr,sizeof(arr) / sizeof(arr[0]));
	Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}

int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestBubbleSort();
	//TestHeapSort();
	//TestQuickSort();
	TestMergeSort();
	TestMergeSortNonR();
	
	return 0;
}

函数的递归实现图：

非递归法

从上面的递归图可以看出，合并的时候是2个数据开始合并，也就是区间【0，0】和【1，1】合并，【2，2】和【3，3】合并；然后【0，1】和【2，3】合并到这里时是两个数据两个数据之间合并，依次类推。那么非递归方法，需要控制好合并的下标即可。

// 归并排序--非递归方法
void MergeArry(int* arr, int begin1, int end1, int begin2, int end2, int* temp)
{
	int left = begin1, right = end2;
	int index = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			temp[index++] = arr[begin1++];
		else
			temp[index++] = arr[begin2++];
	}

	// 可能有一段没结束，具体那一段不知道
	while (begin1 <= end1)
		temp[index++] = arr[begin1++];

	while (begin2 <= end2)
		temp[index++] = arr[begin2++];

	// 将归并后在temp的数据拷贝回原数组
	for (int i = left;i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int* temp = malloc(sizeof(int) * n);

	int gap = 1;  // 控制几个数据的合并排序

	while (gap < n)
	{
		for (int i = 0;i < n;i += 2 * gap)
		{
			// 归并+排序的区间（数组长度不是2的次方数时第二组可能会越界访问）
			// [i,i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;    // 第一组
			int begin2 = i + gap, end2 = i + 2 * gap - 1;  // 第二组

			// 1、合并时只有第一组
			if (begin2 >= n)
				break;

			// 2、合并时第二组只有部分数据，需要修正边界
			if (end2 >= n)
				end2 = n - 1; // 只有一个数值的时候，直接让end2=最后一个数值就行了

			MergeArry(arr, begin1, end1, begin2, end2, temp);
		}
		Printarry(arr, n);
		gap *= 2;
	}

	free(temp);
}

实现图：

结论：

归并排序是一种基于分治思想的有效排序算法，其核心是通过递归将数组不断二分直至单个元素，然后按顺序合并有序子序列。算法分为递归和非递归两种实现方式：递归法通过_MergeSort函数划分区间并调用自身，然后将有序子序列合并到临时数组后回写；非递归法使用MergeSortNonR函数，通过gap变量控制合并步长，逐步扩大有序区间。两种方法都使用MergeArry函数进行具体合并操作，时间复杂度均为O(N*logN)，空间复杂度为O(N)。代码示例展示了完整的实现过程，包括边界处理和数据拷贝等关键步骤。