社区首页 >专栏 >【初探数据结构】归并排序与计数排序的序曲

【初探数据结构】归并排序与计数排序的序曲

我想吃余

发布于 2025-03-31 10:22:08

9300

代码可运行

文章被收录于专栏：数据结构初阶数据结构初阶 C语言学习

运行总次数：0

代码可运行

前言

本文主要内容是归并的递归和非递归以及计数排序的实现方法。文章会提及很多容易忽视的易错点（大多是我自己踩过的坑😂），这是我在学习这块内容时获取的教训和宝贵经验。

因为自己淋过雨，希望能为你们撑把伞！共勉！😁

一、归并排序（Merge Sort）

1. 算法原理

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

归并排序核心步骤：

分解：将数组递归分成两半，直到子数组长度为1。
合并：将两个有序子数组合并为一个有序数组。

从步骤可以看出，这似乎就是二叉树的后序遍历

不知道你们在学习C语言的时候有没有写过这样一道题合并两个有序数组我建议没写过的可以去写一下，这里可以直接抄作业了，O(∩_∩)O哈哈~

2. 递归实现

首先我们需要开辟一个临时数组，来存储合并的序列
递归结束条件：数组长度为1时结束 if (left >= right) return;
mid不要写成(right - left) / 2了，再加上left才能在正确位置（因为这是在计算下标），或者直接用（right+left）/2。——易错点
确定每次拆分的区间[left，mid] [mid + 1,right]。
递归（后序遍历），
归并：在tmp上正确的位置进行赋值，不能是cur = 0,否则会覆盖值——易错点
拷贝，将tmp拷贝到a

void Merger(int* a, int* tmp, int left, int right)
{
	//递归结束条件
	if (left >= right) {
		return;
	}
	int mid = left + (right - left) / 2;//易错：加上left才能在正确的位置
	//递归（后序遍历）
	//[left,mid] [mid+1,right]
	Merger(a, tmp, left, mid);
	Merger(a, tmp, mid+1, right);
	//归并
 	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int cur = left;//易错：在tmp上正确的位置进行赋值，不能是cur = 0,否则会覆盖值
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] > a[begin2]) {
			tmp[cur++] = a[begin2++];
		}
		else {
			tmp[cur++] = a[begin1++];
		}
	}
	while (begin1 <= end1) {
		tmp[cur++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[cur++] = a[begin2++];
	}
	//将tmp拷贝到a
	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

void MergerSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int begin = 0, end = n - 1;
	Merger(a, tmp, begin, end);
	free(tmp);
}

特点：

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定排序，适合处理大数据量。

3. 非递归实现

利用迭代（循环）模拟递归过程：

当元素个数不是gap的整数时，会发生越界问题：设归并的两部分分别为[begin1,end1]和[begin2,end2] 那么，end1、begin2、end2都可能会越界，因此我们就需要修正边界。

end1越界时，第一部分不完整且第二部分不存在，没必要归并了，直接拷贝即可
begin2越界时，第二部分不存在，没必要归并了，直接拷贝即可
end2越界时，第二部分不完整，将end2修正到数组末尾即可

可以发现，1,2是一类情况，可以一起处理了。

我们需要来抉择一个问题：

整体归并结束后拷贝
归并一部分拷贝一部分

这两个问题看似不起眼，实则不然，它会影响你控制边界的难度。可以试试两种方式都写写，会特别爽（狗头）

归并结束后再拷贝，需精密控制边界越界情况，容易出错。——不推荐该写法

void MergerSortNonR1(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) {
			//归并
			//[i,i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int cur = i;
			if (end1 >= n) {
				//修正end1
				end1 = n - 1;
				//使得begin2 > end2,终止归并
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n) {
				//使得begin2 > end2,终止归并
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n) {
				//修正end2，继续归并
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] > a[begin2]) {
					tmp[cur++] = a[begin2++];
				}
				else {
					tmp[cur++] = a[begin1++];
				}
			}
			while (begin1 <= end1) {
				tmp[cur++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[cur++] = a[begin2++];
			}
		}
		//归并结束后再打印
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;
	}
	free(tmp);
}

归并一次拷贝一次，若end1与begin2有越界情况，直接跳出循环（退出归并）即可无需控制边界情况，操作简单易理解

void MergerSortNonR(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) {
			//归并
			//[i,i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int cur = i;
			if (end1 >= n || begin2 >= n) {
				break;//直接终止归并
			}
			else if (end2 >= n) {
				//修正end2
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] > a[begin2]) {
					tmp[cur++] = a[begin2++];
				}
				else {
					tmp[cur++] = a[begin1++];
				}
			}
			while (begin1 <= end1) {
				tmp[cur++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[cur++] = a[begin2++];
			}
			//归并一次打印一次
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		//printf("\n");
		gap *= 2;
	}
	free(tmp);
}

关键点：

gap 控制合并步长，从1开始逐步扩大。
边界处理：若子数组越界，直接终止合并。

二、计数排序（Count Sort）

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

统计相同元素出现次数
根据统计的结果将序列回收到原来的序列中

1. 算法原理

确定范围：找出数组的最小值 min 和最大值 max。
统计频率：创建计数数组 countA，统计每个元素出现的次数。
重建数组：根据计数数组将元素按顺序写回原数组。

2. 代码实现

void CountSort(int* a, int n) {
    int min = a[0], max = a[0];
    for (int i = 0; i < n; i++) {   // 确定范围
        if (a[i] < min) min = a[i];
        if (a[i] > max) max = a[i];
    }
    int range = max - min + 1;
    int* countA = (int*)calloc(range, sizeof(int));  // 分配计数数组
    for (int i = 0; i < n; i++) countA[a[i] - min]++; // 统计频率
    // 重建数组
    int cur = 0;
    for (int i = 0; i < range; i++) {
        while (countA[i]--) a[cur++] = i + min;
    }
    free(countA);
}