详细讲解了归并排序和计数排序的原理、代码实现及复杂度分析。归并排序采用分治策略，时间复杂度 O(n log n)，空间复杂度 O(n)，具有稳定性。计数排序利用元素值作为索引，适用于数据范围小的场景，时间复杂度 O(n+k)。此外，文章还介绍了 memset 函数用法，区分了内排序与外排序的应用场景，并阐述了如何判断排序算法的稳定性。
归并排序（Merge Sort）是一种基于的排序算法，其核心思想是将一个未排序的数组递归地划分为多个子数组，直到每个子数组只有一个元素，然后通过合并两个有序的子数组来达到排序的目的。
12, 11, 13, 5, 6, 7[12, 11, 13] 和 [5, 6, 7][12, 11] 和 [13]、[5, 6] 和 [7][12] 和 [11]、[5] 和 [6][12] 和 [11] 为 [11, 12][5] 和 [6] 为 [5, 6][11, 12] 和 [13] 为 [11, 12, 13][5, 6] 和 [7] 为 [5, 6, 7][11, 12, 13] 和 [5, 6, 7] 为 [5, 6, 7, 11, 12, 13]#include <stdlib.h>
#include <string.h>
// _MergeSort 是递归实现的归并排序核心函数
// a: 待排序的数组
// tmp: 辅助数组，用于暂存排序结果
// begin: 当前排序范围的起始下标
// end: 当前排序范围的结束下标
void _MergeSort(int* a, int* tmp, int begin, int end) {
// 当区间内没有或仅有一个元素时，直接返回（已经有序）
if (end <= begin) return;
// 计算中间下标，将数组一分为二
int mid = (end + begin) / 2;
// 递归地对左半部分 [begin, mid] 进行归并排序
_MergeSort(a, tmp, begin, mid);
// 递归地对右半部分 [mid+1, end] 进行归并排序
_MergeSort(a, tmp, mid + 1, end);
// 现在，左右两个部分已经各自有序，需要将它们合并
int begin1 = begin, end1 = mid; // 左半部分 [begin, mid]
int begin2 = mid + 1, end2 = end; // 右半部分 [mid+1, end]
int index = begin; // 辅助数组 tmp 的索引，用于存储排序结果
// 归并左右两部分，将较小的元素逐一放入 tmp 数组
while (begin1 <= end1 && begin2 <= end2) {
if (a[begin1] < a[begin2]) {
tmp[index++] = a[begin1++];
} else {
tmp[index++] = a[begin2++];
}
}
// 如果左半部分还有剩余元素，将它们全部放入 tmp
while (begin1 <= end1) {
tmp[index++] = a[begin1++];
}
// 如果右半部分还有剩余元素，也将它们全部放入 tmp
while (begin2 <= end2) {
tmp[index++] = a[begin2++];
}
// 将排序结果从辅助数组 tmp 拷贝回原数组 a
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
// MergeSort 是归并排序的入口函数
// a: 待排序的数组
// n: 数组的元素个数
void MergeSort(int* a, int n) {
// 动态分配一个辅助数组 tmp，用于归并过程中的暂存
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc failed");
return;
}
// 调用递归归并排序函数 _MergeSort，对整个数组 [0, n-1] 进行排序
_MergeSort(a, tmp, 0, n - 1);
// 排序完成后，释放动态分配的辅助数组 tmp
free(tmp);
}
归并排序（Merge Sort）是一种稳定的排序算法，采用分治法来将数组分成两半分别排序，然后再将两个有序的子数组合并为一个有序数组。
归并排序的时间复杂度主要取决于其递归过程和合并过程。
n，则递归树的深度为 log n。O(n)。每一层递归中都会对所有元素进行一次合并操作。无论最好、最坏还是平均情况，归并排序的时间复杂度均为 O(n log n)。
O(n)。log n，因此递归调用栈的空间复杂度为 O(log n)。| 情况 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 最好情况 | O(n log n) | O(n) |
| 最坏情况 | O(n log n) | O(n) |
| 平均情况 | O(n log n) | O(n) |
O(n) 的额外空间。归并排序的非递归实现通常使用循环代替递归。每次合并的区间长度会逐步加倍，直到整个数组都被排序完成。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 合并函数：将两个有序的子数组合并成一个有序的数组
void Merge(int* arr, int* tmp, int left, int mid, int right) {
int i = left; // 左半部分的起点
int j = mid + 1; // 右半部分的起点
int k = left; // 临时数组的索引
// 将左右两个部分进行比较并存入 tmp
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
// 如果左半部分还有剩余元素，直接放入 tmp
while (i <= mid) {
tmp[k++] = arr[i++];
}
// 如果右半部分还有剩余元素，直接放入 tmp
while (j <= right) {
tmp[k++] = arr[j++];
}
// 将合并后的结果复制回原数组
for (i = left; i <= right; i++) {
arr[i] = tmp[i];
}
}
// 非递归归并排序函数
void MergeSortNonR(int* arr, int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc failed");
return;
}
// width 代表当前合并的区间大小，初始为 1，然后逐渐加倍
for (int width = 1; width < n; width *= 2) {
// 以 width 为步长，对每个区间进行合并
for (int i = 0; i < n; i += 2 * width) {
int left = i;
int mid = i + width - 1;
int right = i + 2 * width - 1;
// 防止右边界越界
if (mid >= n) break;
if (right >= n) right = n - 1;
// 合并两个区间 [left, mid] 和 [mid+1, right]
Merge(arr, tmp, left, mid, right);
}
}
free(tmp);
}
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
int n = sizeof(arr) / sizeof(arr[0]);
MergeSortNonR(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
非比较排序是一类不依赖元素间比较的排序算法，其中计数排序是典型的代表。它利用了元素的值来直接定位其在排序结果中的位置。
思想： 计数排序是基于鸽巢原理（Pigeonhole Principle），利用元素值作为索引来计数，从而确定每个元素的最终位置。适用于元素范围较小的情况。
操作步骤：
#include <stdio.h>
#include <stdlib.h>
void CountSort(int* a, int n) {
// 找到数组中的最小值和最大值
int min = a[0], max = a[0];
for (size_t 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* count = (int*)malloc(sizeof(int) * range);
if (count == NULL) {
perror("malloc fail");
return;
}
// 初始化计数数组
memset(count, 0, sizeof(int) * range);
// 统计每个元素的出现次数
for (int i = 0; i < n; i++) {
count[a[i] - min]++;
}
// 将元素按顺序拷贝回原数组
int j = 0;
for (int i = 0; i < range; i++) {
while (count[i]--) {
a[j++] = i + min;
}
}
// 释放计数数组的内存空间
free(count);
}
特点：
memset 是 C/C++ 中的一个标准库函数，用于将一块内存中的内容全部设置为指定的值。它的定义在头文件 <string.h>（C 语言）或 <cstring>（C++）中。
函数原型
void* memset(void* ptr, int value, size_t num);
应用场景
memset 将数组或结构体初始化为 0。注意事项
memset 操作的是字节，value 的范围是 0 到 255。memset 的使用需要注意，因为它直接按字节设置内存。判断一个排序算法是否稳定，主要看它在排序过程中是否保持了相等元素的相对顺序。
在计算机领域，排序分为两大类：内排序和外排序，它们根据数据存储位置和内存的使用方式进行区分。
内排序指的是所有数据都存储在内存中进行排序的情况。常见的内排序算法包括：冒泡排序、插入排序、快速排序、归并排序、堆排序。
特点：
外排序适用于数据量非常大的情况，这时数据无法一次性放入内存，需要将数据分批次存储在磁盘等外部存储设备上进行处理。
特点：
归并排序在内排序和外排序中的应用： 归并排序因其稳定性和适应性，成为既适用于内存操作、也适用于外存储操作的有效排序方法。在外排序中，常采用多路归并策略。
(此处省略具体图片展示，重点在于理解稳定性判定逻辑)
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online