非比较排序：计数排序，效率很高，那么代价是什么呢

目录

前言

1 · 计数排序的核心思想

2 · 算法流程详解

2 – 1 · 确定数据范围

2 – 2 · 统计元素频率

2 – 3 · 排序

3 · 代码实现(C)

4 · 算法属性分析

4 – 1 · 时间复杂度

4 – 2 · 空间复杂度

5 · 计数排序的优势与劣势

5 – 1 · 优势

5 – 2 · 劣势

6 · 总结

前言

        在众多排序算法中，计数排序以其独特的非比较性展现了线性时间复杂度的优势。与基于比较的排序算法（如快速排序）不同，计数排序通过统计元素频次而非比较元素大小来实现排序，在特定场景下能达到O(n + k)的时间效率。当数据范围k有限且数据量n较大时，k可视为常数，时间复杂度近似O(n)，这使得它在处理特定结构数据时具有显著优势。

        该算法的核心价值在于突破比较排序的时间下限，其空间换时间的策略尤其适用于整数数列的批量排序场景。然而其局限性同样明显：依赖数据的有限离散范围，若k值过大,则空间效率骤降；对负数和浮点数需特殊处理；稳定性虽佳但失去原数据的物理位置信息。这促使我们深入探究它在现代数据处理中的适用边界与应用策略。

1 · 计数排序的核心思想

        核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放置到正确的位置。

        打个比方：将计数排序比作图书馆管理员整理书籍的过程。假设图书馆的书架代表计数数组，书籍的编号代表待排序的元素值。

        管理员统计每种编号的书籍数量（计数阶段），例如3本编号为A的书、5本编号为B的书。然后按照编号顺序（A-Z）依次将对应数量的书籍放回书架（排序阶段），最终所有书籍按编号有序排列。

2 · 算法流程详解

2 – 1 · 确定数据范围

        找出待排序数组的最小值min 和 最大值max，由此可以得出计数数组的大小为：max – min + 1。同时也就确定了偏移量为min，偏移量用于处理负数或非零最小值的情况。

2 – 2 · 统计元素频率

        将计数数组初始化为0，随后遍历待排序数组，统计其中元素出现的次数，并对应在计数数组中。

2 – 3 · 排序

        根据计数数组，直接对待排序数组进行覆盖，覆盖过后，排序完成。

3 · 代码实现(C)

void CountSort(int* a, int n)
{
//找出最大和最小
int min = a[0];
int 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* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc");
exit(1);
}

//统计个数
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);
}

4 · 算法属性分析

4 – 1 · 时间复杂度

        计数排序的时间复杂度为，其中 N 表示待排序元素个数，range表示计数数组的大小

4 – 2 · 空间复杂度

        由于需要额外开一个计数数组，因此计数排序的空间复杂度为。

5 · 计数排序的优势与劣势

5 – 1 · 优势

        在特定情况下(数据范围较小，取值范围有限)，效率非常高，时间复杂度会降至，比之前介绍的比较排序都要快。

5 – 2 · 劣势

6 · 总结

        计数排序在特定场景下展现出极致高效：

恰当地运用时，它是效率惊人的排序利刃；错用则会造成巨大资源浪费

以上内容如有错误或不准确之处，欢迎指出，或者你有更好的想法，也欢迎交流。