排序算法详解：归并排序、计数排序与稳定性分析

时间复杂度、空间复杂度分析

归并排序（Merge Sort）是一种稳定的排序算法，采用分治法来将数组分成两半分别排序，然后再将两个有序的子数组合并为一个有序数组。

1. 时间复杂度分析

归并排序的时间复杂度主要取决于其递归过程和合并过程。

• 拆分过程：归并排序首先将数组不断二分，直到每个子数组的长度为 1。假设数组长度为 n，则递归树的深度为 log n。
• 合并过程：每次合并两个有序的子数组。合并两个子数组的时间复杂度是线性的，即 O(n)。每一层递归中都会对所有元素进行一次合并操作。
• 总的时间复杂度： [ T(n) = O(n) \times O(\log n) = O(n \log n) ]

无论最好、最坏还是平均情况，归并排序的时间复杂度均为 O(n log n)。

2. 空间复杂度分析

• 额外空间消耗：归并排序需要额外的数组来存储两个子数组的合并结果，空间复杂度为 O(n)。
• 递归栈空间消耗：递归的深度为 log n，因此递归调用栈的空间复杂度为 O(log n)。
• 总的空间复杂度： [ S(n) = O(n) + O(\log n) = O(n) ]

3. 归并排序的特点

• 稳定性：归并排序是稳定的排序算法。在合并过程中，如果遇到两个相等的元素，原先在左边的元素会优先被合并到结果数组中。
• 适用场景：适合大规模数据的排序，尤其是外部排序。
• 空间开销：主要缺点是其空间复杂度较高，需要 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），利用元素值作为索引来计数，从而确定每个元素的最终位置。适用于元素范围较小的情况。

操作步骤：

1. 统计相同元素出现的次数：找出最大值和最小值，创建计数数组。
2. 累加计数，确定元素的位置：将计数数组转换为累加数组。
3. 根据计数结果将序列回收到原来的序列中：从原数组末尾开始遍历放置元素。

计数排序的代码实现

#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);
}

特点：

• 时间复杂度: O(n + k)，其中 n 是元素个数，k 是元素范围。
• 空间复杂度: O(k)
• 稳定性: 稳定排序算法
• 适用范围: 元素范围 k 相对较小时，计数排序非常高效。

回顾：memset

memset 是 C/C++ 中的一个标准库函数，用于将一块内存中的内容全部设置为指定的值。它的定义在头文件 <string.h>（C 语言）或 <cstring>（C++）中。

函数原型

void* memset(void* ptr, int value, size_t num);

应用场景

1. 初始化数组或结构体：可以使用 memset 将数组或结构体初始化为 0。
2. 内存清零：例如，将某个缓冲区清零以防止信息泄露。

注意事项

1. memset 操作的是字节，value 的范围是 0 到 255。
2. 对于结构体或非字符类型的数组，memset 的使用需要注意，因为它直接按字节设置内存。

如何判断排序算法是否稳定

判断一个排序算法是否稳定，主要看它在排序过程中是否保持了相等元素的相对顺序。

• 稳定的排序算法：如果在排序前，两个相等的元素在数组中的相对顺序是先后排列的，经过排序后，它们的相对顺序依然保持不变。
• 不稳定的排序算法：在排序后，相等元素的相对顺序可能发生改变。

常见排序算法的稳定性

• 稳定的排序算法：冒泡排序、插入排序、归并排序、基数排序。
• 不稳定的排序算法：选择排序、快速排序、堆排序。

内排序和外排序

在计算机领域，排序分为两大类：内排序和外排序，它们根据数据存储位置和内存的使用方式进行区分。

1. 内排序（In-Memory Sorting）

内排序指的是所有数据都存储在内存中进行排序的情况。常见的内排序算法包括：冒泡排序、插入排序、快速排序、归并排序、堆排序。

特点：

• 数据可以通过随机访问进行操作。
• 访问速度快。

2. 外排序（External Sorting）

外排序适用于数据量非常大的情况，这时数据无法一次性放入内存，需要将数据分批次存储在磁盘等外部存储设备上进行处理。

特点：

• 必须考虑磁盘的访问方式，依赖顺序读写。
• 性能受磁盘 I/O 影响较大。

归并排序在内排序和外排序中的应用： 归并排序因其稳定性和适应性，成为既适用于内存操作、也适用于外存储操作的有效排序方法。在外排序中，常采用多路归并策略。

八大算法稳定性分析

(此处省略具体图片展示，重点在于理解稳定性判定逻辑)

1. 实验验证：编写测试程序，构造包含多个相等元素的数组，观察排序后的相等元素顺序是否保持不变。
2. 理论分析：检查算法在处理相等元素时是否会打乱它们的相对顺序。