排序（3）【归并排序】【计数排序】【排序算法度及其稳定性分析】

一.归并排序

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

在八个数中进行排序就是这样的：

1.归并排序的实现

void MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;//求中间值，目的是为了不断的缩小区间
	MergeSort(a, tmp, begin, mid);//从左边开始，运用递归，一层一层的缩小区间
	MergeSort(a, tmp, mid + 1, end);//这里是右区间
	int begin1 = begin, end1 = mid;//[begin,mid]与[mid+1,end]
	int begin2 = mid + 1, end2 = end;
	int i = begin;//从begin开始
	while (begin1 <= end1 && begin2 <= end2)//左右区间的值依次开始比较，比较小的那个放到新的区间，下标为i
	{
		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++];
	}
	//这里因为我们单独创建了一个数组，所以我们需要把tmp里面的值拷贝到原来的数组里
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
	//因为我们的区间不一定从哪里开始（begin不确定），我们需要知道我们要从哪里开始拷贝，所以这里加了一个begin
}

这个代码的思想就是，我们把一个区间通过一半一半的分，分成更小的区间，然后对这小区间进行排序，再把小区间和小区间合成一个大区间，其中的每一个小区间都是有序的。这就像是一个二叉树后序的过程。

2.用非递归实现归并排序

上面对我们都是使用递归来实现排序，当然肯定有人不喜欢递归来实现。这里还有一种非递归的方式：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//动态创建一个数组
	if (tmp == NULL)
	{
		perror("tmp::malloc");
		return;
	}
	int gap = 1;//gap指的是每次归并几个元素
	while (gap < n)//gap不能大于等于n
	{
		for (int i = 0; i < n; i += 2 * gap)//这里的循环是把数组里的元素全部进行归并，每组数据个数是gap，还要注意i += 2 * gap指的是跳到下一组
		{
			//然后开始分区间[begin1，end1][begin2，end2]
			//归并是两组两组进行的这一个区间里的值与下一个区间里的值进行归并
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//这里需要判断三种特殊情况，后面单独说
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			//为了不影响变量i，再创建一个变量，往tmp数组里入数据
			int j = i;
			while (begin1 <= end1&&begin2<=end2)//这里就是上面说过的入数据，左区间和右区间进行比较
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			//这里就是把剩余的没有入完的数据都入进去
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while(begin2<=end2)
			{
				tmp[j++]=a[begin2++];
			}
			//因为我们创建的是临时变量tmp，所以这里用memcpy
			//每次排完两组，我们就拷贝数据，如果在for循环外部，会导致一些错误，后面说
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
			
		}
		//到这里我们就已经完全的排完序了，下面就是继续增大区间，继续循环归并
		gap = gap * 2;
	}
	//还有就是别忘了释放
	free(tmp);
	tmp = NULL;
}

这里还有一些问题要说一下就是上面没有解释的那个代码：

if (begin2 >= n)
{
	break;
}
if (end2 >= n)
{
	end2 = n - 1;
}

如果我不加上面的两个if语句的话，我们会发现只有当我们的数据个数是2的n次方的时候才可以完成排序的功能。如果我有十个数的话，它就会有越界的风险。因为我每一次跳过的距离是gap，而gap是呈2的倍数增长。那么后面我在求区间的时候就会出现越界的问题。

有三种情况：

分别代表着end2越界，begin2和end2越界，end1，begin2和end2越界。后面两种对应着第一个if语句：

if (begin2 >= n)
{
	break;
}

意思就是，如果我的begin2越界了，我就跳出这个循环，不再进行归并，因为后面的元素个数已经没有了，不需要进行归并，仅需完成前面归并的过程就行了。

然后就是第一种情况，我们只需要调整一下end2的值就行了。原本end2是越界的，我们直接让它成为最后一个元素就行了（end1之前也就是end2，在上一个过程中已经调整过了）。

如果将memcpy放在for循环外部，那么在第一次循环后就会把整个排序结果拷贝到原始数组中，导致后续的归并排序无法正确进行。比如我有11个数，那么在刚开始的时候，我有一个数就不能被拷贝进去，tmp里是10个值，此时我把tmp数组拷贝到原数组里就会出现出错。

3.归并排序的时间复杂度

归并排序的时间复杂度是O(nlogn)，其中n是要排序的元素个数。归并排序的核心操作是将待排序的数组不断地分割成两个子数组，直到每个子数组只有一个元素。然后，将两个子数组合并成一个有序数组。这个分割和合并的过程需要重复logn次，每次操作的时间复杂度是O(n)。因此，归并排序的总时间复杂度是O(nlogn)。

空间复杂度是O(n)。

二.计数排序

1.计数排序的实现

这个排序是比较特殊一点的排序，它是不用比较大小就可以把数据排好的一种方式，它所用的方式是统计。

void CountSort(int* a, int n)
{
	//先找到数组里的最大值和最小值，求出数组里数据的范围
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;
	//根据范围的大小开辟空间，注意这里用的calloc直接也可以把开辟的空间里的值初始化为0
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}
	//因为我们count数组里的值都是0，根据相对值，如果出现与count数组下标相同的值我们就加一
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	//到这里就是排序的过程，根据count数组的下标，我们把它的下标值加上min就是我们需要排序的数，依次放进数组里
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(count);
}

可能稍微用了一点比较大小的方式，但是主体我们利用了下标统计的方式来实现排序。