【初阶数据结构】排序——归并排序

前言

对于常见的排序算法有以下几种：

前面我们已经学习了：

1. 【初阶数据结构】排序——插入排序
2. 【初阶数据结构】排序——选择排序
3. 【初阶数据结构】排序——交换排序

下面这节我们来看最后一个归并排序算法。

归并排序

  归并排序是一种建立在归并操作上的一种有效的排序算法，这是采用分治法的一个典型应用。想要得到完全有序的序列，就先使得每个子序列有序，再使得子区间段有序，最后整个序列有序。
基本思想：
1.首先是分：将序列不断划分，分成不能再分的字序列。
2.然后是治，将子序列不断进行排序且合并，最终得到完全有序的序列。

下面是归并排序的一个图解：

  如果想像快排一样，直接在原数组进行分解合并是行不通的，终究会将原序列中的值进行覆盖，因此在排序之前要先开辟一个新数组，将拆解的数放到新数组中排好序再拷贝回去。
代码如下：

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	//直接在这里面是递归完成不了的，因为它每次都会malloc，我们只需要malloc一次就行
	_MergeSort(a, 0, n - 1, tmp);//[0,n-1]是需要排序的区间
	free(tmp);
	tmp = NULL;
}

void _MergeSort(int* a, int left, int right, int* tmp)
{
	//递归结束条件
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	//划分区间
	// [left, mid] [mid+1, right]
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
	//排序
	//.....
}

我们画图来看看递归的过程：

  知道是如何递归的以后我们来看看是怎么进行排序的：
  对两个序列进行比较，其实就像是前面做过的一个题叫合并有序数组，思路是完全一致的，有疑惑的可以回去看看。
下面直接上代码：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	//递归结束条件
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	//划分区间
	// [left, mid] [mid+1, right]
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
	//排序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = begin1;//注意不能直接写0，要比较的区间不一定直接从0开始
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])//把小的值放到tmp中
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//有一个序列已经全部放入tmp中，此时把另一个序列中的值放入即可
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//同样，拷贝时也不能少写left
	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

归并排序特性总结：

1. 时间复杂度：O(NlogN)
2. 空间复杂度：O(N)
3. 稳定性：稳定

归并排序的非递归写法

非递归写法的重点是对于区间的划分掌控，我们直接上图讲解：

两个gap组序列即可完成一次归并，后再将gap×2即可。
排序的过程同样要建立新数组来排。
直接看代码：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	int begin1, end1, begin2, end2;
	while (gap < n)
	{
		for (int j = 0; j < n; j += 2 * gap)
		{
			begin1 = j, end1 = begin1 + gap - 1;//下标
			begin2 = end1 + 1, end2 = begin2 + gap - 1;
			int i = j;
			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 + j, tmp + j, sizeof(int) * (end2 - j + 1));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

当我们对下面这组数排序时：

int a[] = { 8,5,6,1,3,7,4,2 };

排序正确。
但当对下面一组数排序时：

int a[] = { 8,5,6,1,3,7,4,2,9,0 };

程序却出现了崩溃：

我们来分析一下这组数：

找到了程序崩溃的原因，我们只需要避免这个问题即可：

1. 越界主要是end1，begin2，end2这三个中一个越界
2. 如果end1越界，则后面都越界，就不会进行归并了，begin2也是同理
3. 如果是end2越界，则直接修正end2到最末尾的下标即可

具体代码如下：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	int begin1, end1, begin2, end2;
	while (gap < n)
	{
		for (int j = 0; j < n; j += 2 * gap)
		{
			begin1 = j, end1 = begin1 + gap - 1;//下标
			begin2 = end1 + 1, end2 = begin2 + gap - 1;
			//处理越界问题
			if (end1 > n - 1 || begin2 > n - 1)
				break;
			else if (end2 > n - 1)
				end2 = n - 1;
			int i = j;
			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 + j, tmp + j, sizeof(int) * (end2 - j + 1));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

计数排序

前面所讲的所有排序都是通过比较两者大小来实现的，但是排序也存在非比较排序，有如下几种：

1. 计数排序
2. 基数排序
3. 桶排序

这三种都是非比较排序，但是在实践中应用较少，我们调用的最多的计数排序讲讲。

基本思想：
1.先将待排序序列的最大值和最小值算出
2.通过最大值与最小值可得到这个序列的区间，以及这个区间的个数
3.创建一个和这个区间一样大的新数组
4.遍历原数组，将值减去最小值得到新数组的下标，将该位置++，即可统计出原数组区间的数对应到新数组中每个值有几个
5.再遍历新数组，从小到大，通过个数即可得出排序。

代码如下：

void CoundSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}
	int range = max - min + 1;//找到最大值与最小值所组成的区间
	int* tmp = (int*)calloc(range, sizeof(int));
	if (tmp == NULL)
	{
		perror("calloc fail");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			a[j++] = i + min;
		}
	}
}

通过上面的了解，我们发现计数排序的一些缺陷：它只适合数据范围较为集中的数组进行排序，不适合数据分散的数组。

排序总结

综上，已经把所有排序讲完了，在各个排序的特性总结中，有一个稳定性的点，这里解释一下稳定性是什么：

就如奖学金有3个名额，但是第三名和第四名成绩一样，此时就要有另一个标准来判断第三名的成绩比第四名好，否则随意把第四名排到第三名前面会引发公愤。

感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。