排序算法详解：归并排序与计数排序

排序算法详解：归并排序与计数排序

引用

CSDN

1.

https://m.blog.csdn.net/qq_66330780/article/details/144154012

本文将介绍两种重要的排序算法：归并排序和计数排序。通过对比分析它们的原理、实现方式及复杂度，帮助读者更好地理解这些排序算法的特点和适用场景。

一、归并排序

1.1 基本思想

归并排序（MERGE-SORT）是一种基于归并操作的高效排序算法，采用分治法（Divide and Conquer）策略。其基本思想是将数组分解成更小的子数组，对这些子数组进行排序，然后将已排序的子数组合并成一个完全有序的数组。

根据上面两个图我们可以大致了解到：归并排序是先把整个数组分解成像二叉树一样的形式，然后两两排序后进行合并，从而完成排序。代码实现上我们依然可以用递归思想完成。

1.2 代码实现

void _MergeSort(int* a, int* tmp, int begin, int end)
{
    if (end <= begin)
        return;
    int mid = (end + begin) / 2;
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else 
        { 
            tmp[index++] = a[begin2++]; 
        }
    }
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }
    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
}  

这段代码可以实现偶数元素的四四归并、两两归并，奇数元素也可实现归并。

1.3 特性

1. 空间复杂度：O(N)，需要额外的存储空间来存放临时数组
2. 时间复杂度：O(N*logN)，在所有输入情况下都能保持稳定的时间复杂度
3. 稳定性：稳定，相同元素的相对顺序在排序后保持不变
4. 适用场景：适用于大数据量的排序，尤其是外排序场景

二、计数排序

2.1 基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。其基本步骤如下：

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

2.2 代码实现

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);
    printf("range:%d\n", 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;
        }
    }
}  

2.3 特性

1. 时间复杂度：O(N+range)，其中range是数组中最大值和最小值的差
2. 空间复杂度：O(range)，需要额外的空间来存储计数数组
3. 适用性：只适合整形数据，且数据范围不宜过大
4. 稳定性：稳定，相同元素的相对顺序在排序后保持不变
5. 适用场景：适用于数据范围集中的场景

三、排序算法总结

稳定性是排序算法的一个重要特性，它指的是在排序过程中，相同元素的相对位置是否发生变化。例如，在比赛排名中，如果多个选手的成绩相同但完成时间不同，就需要使用稳定的排序算法来保持它们的原始顺序。

下表总结了常见排序算法的时间复杂度、空间复杂度和稳定性：

通过对比分析，我们可以根据具体的应用场景选择合适的排序算法。例如，当数据量较大时，归并排序是一个很好的选择；当数据范围集中时，计数排序则更为高效。