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

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友！

文章目录

- 前言
- 一、归并排序（Merge Sort）
- - 1. 算法原理
  - 2. 递归实现
  - 3. 非递归实现
- 二、计数排序（Count Sort）
- - 1. 算法原理
  - 2. 代码实现
- 三、对比与总结

前言

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

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

一、归并排序（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拷贝到amemcpy(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) {//修正end1end1 = 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) {//修正end2end2 = 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);
}