计数排序&&归并排序（递归版本&&非递归版本）

1.计数排序

????????计数排序是一种非比较排序算法，其核心思想是通过统计每个元素出现的次数，然后根据统计结果将元素按照顺序放置在输出数组中。

以下是计数排序的逻辑思想（C语言版）：

1. 首先，遍历待排序的数组，找到数组中的最大值max，确定计数数组的大小为max+1。

2. 创建一个大小为max+1的计数数组count，并初始化为0。

3. 遍历待排序的数组，将每个元素的值作为计数数组count的索引，并将对应索引位置的值

加1，表示该元素出现的次数。

4. 对计数数组count进行累加操作，使得每个索引位置的值表示小于等于该索引的元素个数。

5. 统计完次数之后就往原数组内覆盖回写

????????计数排序是一种就地排序算法，这意味着它不需要任何额外的空间来对数据进行排序。它也是一个稳定的排序算法，这意味着输入中相等元素的顺序在输出中得以保留。

????????计数排序是一种十分高效的排序，时间复杂度为O(n + k)，其中n是列表中元素的数量，k是列表中任何元素的最大值。计数排序的空间复杂度为O(k)。

? ? ? ? 计数排序是不适合分散的数据，更适合集中的数据；不适合浮点数，字符串，结构体数据排序，只适合整数。

eg：如果有一组数据是从1000开始的连续的数据，那么是不是就意味着前面1000个空间就浪费了，如何解决？

? ? ? ? 我是数据是多少就映射到哪个位置上，这种映射叫做绝对映射，这可能会导致大量空间的浪费，大多情况下我们都是使用相对映射的方法。（相对最小值）我们在使用计数排序前，可以先找到改组数据的最小值和最大值，这就是该组数据的范围，这样就可以有效的节省空间了。

代码：

// 计数排序
// 时间：O(N+range)
// 空间：O(range)
void CountSort(int* a, int n)
{
	int min = a[0], 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;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;//使得下标从0开始
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;//回到原数组范围
		}
	}
}

2.归并排序?

递归版本

基本思想：

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

它将待排序的数组递归地分成两个子数组，然后对这两个子数组分别进行排序，最后将两个有序的子数组合并成一个有序的数组。

递归版本的归并排序的具体步骤如下：

1. 将待排序的数组分成两个子数组，每个子数组的大小为 n/2。

2. 对这两个子数组分别进行递归排序。

3. 将两个有序的子数组合并成一个有序的数组。

合并两个有序的子数组可以通过以下步骤实现：

1. 创建一个新的数组，用于存储合并后的结果。

2. 将两个子数组中的元素依次比较，将较小的元素放入新的数组中。

3. 重复步骤 2，直到两个子数组中的所有元素都被放入新的数组中。

下面是归并排序的递归版本的算法步骤：

1. **分解**：将待排序的数组分成两个子数组，通过计算数组的中间位置来实现。可以使用递归将左右两个子数组继续分解，直到子数组的大小为1。

2. **排序**：对分解得到的子数组进行排序，可以通过递归调用归并排序函数来实现。

3. **合并**：将排序好的两个子数组合并成一个有序的数组。比较两个子数组的第一个元素，将较小的元素放入结果数组中，并将相应子数组的指针向后移动，重复这个过程直到其中一个子数组为空，然后将另一个子数组中剩余的元素直接放入结果数组中。

递归版本的归并排序的关键在于递归地将数组分解为较小的子数组，并在合并阶段将它们逐步合并成一个有序的数组。这个过程会一直递归下去，直到子数组的大小为1，即只有一个元素，此时可以认为它已经是有序的。

下面归并排序递归版本的实现代码：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid][mid+1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	// [begin, mid][mid+1, end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	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 + 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");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

---

非递归版本

递归的思想是把数组分到一个数据认为它有序，然后才开始归并。非递归的思想就是可以一开始就是认为单个数据有序，开分组归并。

这里我们引出gap变量，gap表示每组的数据个数

我们还是通过划分区间的方法来理清逻辑，[begin1,end1] [begin2,end2]两组一归并。

end1为什么是i+gap-1？因为我们访问的是下标，所有我们要减去1

int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;

该如何控制gap？

gap的变化趋势是每次扩大2倍，gap*=2。只要gap<n，那么循环就继续。

该怎么去控制归并循环？

首先i+=2*gap，因为每次要跳过两组数据，那么i的结束条件就可以是i<n

注意：没归并完一组就将这组的数据拷贝回原数组，而不是将所有组归并完后，再将整个数组拷贝回原数组。（稍后解释原因）。

初步代码：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		
		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 = begin1;
			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++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * 2*gap);
		}

		printf("\n");

		gap *= 2;
	}


	free(tmp);
}
int main()
{
	int a[8] = { 8,7,6,5,4,3,2,1 };
	MergeSortNonR(a, 8);
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i] );
	}
}

运行结果：

但我们的数组个数不是2^n时，排序就出现错误了，这是为什么呢？

我们通过打印每组gap的分组情况发现gap为2，4，8时，都出现了越界情况，我们并没有那么多数据，因为我们都是按整数倍去算的，每次都会为我你们补齐，如何解决？

我们先看begin1，begin1是i，它不可能越界，其它的都可能越界。

如果end1越界， 那么证明后面就没有数据，就不需要越界了，接直接break。

如果begin2越界了，end2，那也可以证明后面没有数据了，直接break。

如果end2越界了，那么证明前面都是好的，end2是补齐到了整数倍所以导致越界了，那么只要将end2修正到n就好了。

这里的拷贝也是要进行修改的，因为拷贝也是按照整数倍去拷贝的，要改成（end2-i+1）左闭右闭，减完后要加1。

修改后的代码：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		//printf("gap:%2d->", gap);
		for (size_t i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// [begin1, end1][begin2, end2] 归并
			//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);

			// 边界的处理
			if (end1 >= n || begin2 >= n)
			{
				break;
			}

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

			//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);

			int j = begin1;
			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++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
		}

		printf("\n");

		gap *= 2;
	}


	free(tmp);
}

运行结果：

填前面的坑：为什么要归并一组拷贝一组，而不是等拷贝完了，拷贝整个数组？

因为会出现越界的情况，当遇到越界的情况，因为只有一组已经是有序的了，直接break就好了，就不需要进入tmp数组了，如果break了，却又整组的进行迭代数据，那么在最后一组的位置进入tmp数组就有可能出现随机值，再拷贝回原数组那么就会把最后一组正确的数据给覆盖掉了。