【数据结构与算法】归并排序（详解：递归与非递归的归并排序 | 赠：冒泡排序和选择排序）

前言

本篇博客会对排序做一个收尾，将最经典的七大排序介绍完毕。

这次的重点正如标题，主要讲的是归并排序，还会带过相对简单很多的冒泡排序和选择排序。在最后还会给这七大排序做出一个时间复杂度和稳定性展示的总结收尾。同时，这也是初阶数据结构的最后一篇。待到再次与数据结构见面时，就会用C++来讲解，因为进阶数据结构相对复杂，用C++会相对轻松一些。话不多说，开始我们今天的内容。

归并排序

归并的思想逻辑

归并排序核心步骤：

为了更好的理解，这里有一份动图：

在上面的动图中，不知道大家有没有发现一点，归并排序算法并没有直接在原数组上执行，而是借助了一个malloc出来的临时数组。归并排序的核心在于将两个已排序的子数组合并成一个有序的数组。合并过程中，我们需要同时比较两个子数组的元素，并将它们按照大小顺序放入一个新的序列中。这个新的序列通常就是一个临时数组，它用于存储合并后的结果，并且在合并完成后会覆盖或者替换原来的子数组。

归并排序合并代码

这合并代码是归并排序中最底层最重要的逻辑，以图中两段合并为例：

合并过程中，比较两个子数组中的元素，并按照大小顺序依次放入新数组中，直到两个子数组中的所有元素都被考虑完毕。下面为此过程实现代码：

int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end, tmpn = begin;
while (begin1 <= end1 && begin2 <= end2) {
	if (a[begin1] <= a[begin2]) tmp[tmpn++] = a[begin1++];
	else tmp[tmpn++] = a[begin2++];
}
while (begin1 <= end1)tmp[tmpn++] = a[begin1++];
while (begin2 <= end2)tmp[tmpn++] = a[begin2++];
//这部分排完之后，将排好的数从临时tmp数组移回原数组
memmove(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

归并排序递归实现

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc fail:");
		exit(1);
	}
    //归并排序实现
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

上面代码的_MergeSort()是正真完成归并排序的函数，接下来我们可以看看其中的实现：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
    //当无法再细分时判断退出
	if (begin >= end)return;
	int mid = (begin + end) / 2;
    //递归过程
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end, tmpn = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] <= a[begin2]) tmp[tmpn++] = a[begin1++];
		else tmp[tmpn++] = a[begin2++];
	}
	while (begin1 <= end1)tmp[tmpn++] = a[begin1++];
	while (begin2 <= end2)tmp[tmpn++] = a[begin2++];
	memmove(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

以上就是归并排序递归实现的所有代码。

归并排序非递归实现

见到非递归，你可能会想像实现快速排序非递归那样用栈或者队列实现归并排序的非递归，但可能你需要仔细思考一下，用栈或者队列似乎不好解决二叉树的后序遍历，也就是归并排序这一过程。

归并排序非递归代码实现：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) {
		perror("malloc fail:");
		exit(1);
	}
	int gap = 1;
	while (gap < n) {
		for (int i = 0; i < n; i += gap * 2){
			int begin1 = i, end1 = begin1 + gap - 1, tmpn = begin1;
			int begin2 = end1 + 1, end2 = begin2 + gap - 1;
            //越界处理
			if (end1 >= n || begin2 >= n)break;
			if (end2 >= n) end2 = n - 1;
            //-------
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] <= a[begin2])tmp[tmpn++] = a[begin1++];
				else tmp[tmpn++] = a[begin2++];
			}
			while (begin1 <= end1)tmp[tmpn++] = a[begin1++];
			while (begin2 <= end2)tmp[tmpn++] = a[begin2++];
            //这里需要根据gap和end1的变化控制memmove的空间大小
			memmove(a + i, tmp + i, sizeof(int) * (gap + end2 - end1));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

以上就是归并排序的所有内容了，接下来两个排序的难度大大降低。

冒泡排序

冒泡排序的思想逻辑

这里有一份动图帮助理解：

冒泡排序代码实现

作为最简单好理解的排序方式之一，这里直接附上代码。

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++) {
		int exchange = 0; // 优化，如果判断无交换则排序结束
		for (int i = 1; i < n - j; i++) {
			if (a[i - 1] > a[i]) {
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)break;
	}
}

选择排序（直接选择排序）

选择排序思想逻辑

选择排序代码实现

也是作为最简单好理解的排序方式之一，这里直接附上代码。

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right) {
		int mini = left, maxi = right;
		for (int i = left; i <= right; i++) {
			if (a[i] < a[mini])mini = i;
			if (a[i] > a[maxi])maxi = i;
		}
		Swap(&a[mini], &a[left]);
		if (left == maxi) maxi = mini;
		Swap(&a[maxi], &a[right]);
		left++;
		right--;
	}
}

七大排序算法复杂度及稳定性

 什么？你说我还没讲堆排序？看看这篇博客：初阶数据结构之---堆的应用（堆排序和topk问题）-CSDN博客

你问我什么是稳定性？好吧，这里再回顾一下。

结语

本篇博客对归并排序，冒泡排序和直接插入排序做了深入分析和讲解，最后展示了七大经典排序的算法复杂度和稳定性。掌握排序是一个程序员的基本素养，对开拓思维也有很大的帮助。数据结构初阶相关的所有内容到这里就结束了，在进入进阶数据结构之前，我会写一些关于C++的基础语法的内容做一个过度，希望能帮助到大家。

感谢支持，博主后续会产出更多有意思的内容！♥