【数据结构】排序算法——Lesson2

Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
个人主页：奋斗的小羊
所属专栏：数据结构

本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为记录我的学习过程及理解。文笔、排版拙劣，望见谅。

前言

本文将继续介绍两种高效的排序算法——归并排序、计算排序。
归并排序在一些场合下（如外部排序）非常有效，当数据量非常大且无法全部加载到内存时，可以将其分块处理。
而计数排序是一种非比较排序算法，适用于特定范围内的整数排序，在许多数情况下计算排序可以秒杀我们介绍过的所有排序。

一、排序算法

1、归并排序

| 算法思路：

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列间段有序。

动图演示：

代码实现：

//子函数
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
	if (begin == end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//[begin, mid]  [mid + 1, end]
	_MergeSort(arr, tmp, begin, mid);
	_MergeSort(arr, tmp, mid + 1, end);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

//归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(arr, tmp, 0, n - 1);

	free(tmp);
	tmp = NULL;
}

归并排序有几个需要特别注意的点：

• 分割区间一定要按[begin, mid] [mid + 1, end]分，不然会导致死循环
• memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
• 一定是归并一组拷贝一组，因为如果存在越界的情况还整体拷贝肯定会出错
• 归并排序算法的时间复杂度是：O(N*logN)，空间复杂度是：O(N).

2、归并非递归

递归改非递归有两种办法，一种是用栈模拟，一种是用循环处理。

上篇文章中快排非递归我们是利用栈实现的，但是归并的非递归使用栈解决不了，因为快排的递归过程是一个类似前序遍历的过程，而归并是一个类似后续的过程，它是先将区间循环分割成只有一个数据，再反向进行归并，栈是做不到这一点的。
所以归并的非递归我们考虑用循环来实现。

我们可以直接将原数组一一归并，再二二归并，再四四归并……

//归并非递归
void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	//gap是每组归并数据的个数
	int gap = 1;
	while (gap < n)
	{
		//i表示每组归并的起始位置
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			//
			memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2;//一一归，二二归，四四归
	}

	free(tmp);
	tmp = NULL;
}

• memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
• for (int i = 0; i < n; i += 2 * gap)
• int begin2 = i + gap, end2 = i + 2 * gap - 1;

但是上面的代码还不完善，仅限2的次方个数的数据归并，如果不是2的次方个数则会越界。越界无非下面三种情况：

1. [begin1, end1] [begin2, end2 ]
2. [begin1, end1] [begin2 , end2 ]
3. [begin1, end1 ] [begin2 , end2 ]

其中第二种和第三种可以归为一类，因为begin2越界说明我们需要排序的数据已经排好序了，越界的部分不是我们的区间我们根本不用管，直接退出循环就行了。
而第一种情况只需要处理一下就好，让end2变成n - 1就行了。

代码示例：

//归并非递归
void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	//gap是每组归并数据的个数
	int gap = 1;
	while (gap < n)
	{
		//i表示每组归并的起始位置
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//第二组都越界，不存在，不是我们需要排序的数据
			if (begin2 >= n)
			{
				break;
			}

			//begin2没越界，end2越界，只需要修正一下就好
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					tmp[j++] = arr[begin1++];
				}
				else
				{
					tmp[j++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			//归并一次拷贝一次
			memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

3、计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。其排序步骤为：

1. 统计相同元素出现的次数，将统计到的次数作为count数组以元素值对应下标处的值
2. 根据统计的结果将序列回收到原来的序列中
3. 动态开辟的count数组要初始化为全0

本质： 利用count数组的自然序号排序

为了保证开辟大小合适的count数组，我们可以用待排数据中最大值减最小值加一的方法来确定一个合适的范围（max - min + 1）。
然后再用元素值减去最小值的方法来和count数组形成相对映射关系（arr[i] - min），得到的值是几就在数组对应下标位置递增。
最后一步排序的时候不要忘了在原数组中插入的值还要加上最小值，并且count数组中下标对应位置的值是几就循环几次，如果对应位置是0的话说明原数组没有这个下标数，就不进入循环。

大致思想如下：

代码如下：

//计数排序
void CountSort(int* arr, int n)
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < arr[min])
		{
			min = arr[i];
		}
		if (arr[i] > arr[max])
		{
			max = arr[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}
	//统计次数
	for (int i = 0; i < n; i++)//遍历原数组
	{
		count[arr[i] - min]++;
	}
	//排序
	int j = 0;
	for (int i = 0; i < range; i++)//遍历count数组
	{
		while (count[i]--)
		{
			arr[j++] = i + min;
		}
	}
	free(count);
	count = NULL;
}

计数排序的时间复杂度为：O(N + range)，相比较前几种排序算法，计数排序效率是非常高的，但速度快的同时也有空间消耗，计数排序的空间复杂度为：O(range)，所以计数排序也算是拿空间换时间。

计数排序虽然相对其他排序算法快且稳定，但也存在一些缺陷：

• 只能排整数，不能排浮点数
• 要求数据比较集中，不然空间开销太大

4、排序算法复杂度及稳定性分析

稳定性： 如果待排序数据中有多个相同的的数据，若经过排序这些相同的数据相对位置保持不变，则称这种排序算法是稳定的。

总结

• 这些排序算法各有千秋，在某些特定的情况下某个算法的性能尤为突出，在一些复杂的排序中为了追求性能往往使用混合排序，这使得性能大大提高。