【数据结构与算法】详解计数排序：小范围整数排序的最佳选择

一、引言

传统的比较型排序算法（如快速排序、归并排序等）虽然应用广泛，但在面对特定类型的数据时，其性能往往受到一定限制。这时，非比较型排序算法，如计数排序，便展现出了其独特的优势。 本文旨在深入剖析计数排序的奥秘与魅力，从基本原理到实现步骤，从优缺点分析到实际应用场景，全面展现这一排序算法的独特之处。通过本文的阅读，读者将能够深刻理解计数排序的工作原理，掌握其实现方法，并学会在合适的场景下灵活运用这一算法，以提升数据处理的效率和质量。

二、计数排序的基本原理

计数排序（Counting Sort）是一种非比较型排序算法，它的基本原理是通过统计每个元素的出现次数，然后利用这些信息来重建排序后的数组。 其核心思想在于：通过统计每个元素在数组中出现的次数，来确定该元素在排序后数组中的位置。这种方法在处理具有明显范围限制且分布相对均匀的整数数据时，尤为高效。 作为一种线性时间复杂度的排序，它要求输入的数据必须是有确定范围的整数。

请看下图动图演示

三、实现步骤

1. 确定数据范围

首先，代码通过遍历待排序数组 a，找出其中的最大值 max 和最小值 min。这两个值用于确定计数数组 count 的大小，因为计数数组需要覆盖待排序数组中所有可能出现的值（在最小值和最大值之间）。

int min = INT_MAX;
int max = INT_MIN;
for (int i = 0; i < n; i++)//求得最大值和最小值
{
	if (a[i] > max)
		max = a[i];
	if (a[i] < min)
		min = a[i];
}

2. 初始化计数数组

根据最大值和最小值计算出的范围（max - min + 1），代码使用 calloc 分配了一个足够大的整数数组 count，并将所有元素初始化为 0。这个数组用于统计待排序数组中每个值出现的次数。使用 calloc 而不是 malloc 加初始化是为了确保所有元素都初始化为 0，因为计数排序需要这些初始值来正确统计。

int size = max - min + 1;
int* count = (int*)calloc(size, sizeof(int));//根据数据范围申请空间
if (count == NULL)
{
	perror("calloc fail\n");
	return;
}

3. 统计元素频率

接下来，代码再次遍历待排序数组 a，这次是为了统计每个元素出现的次数。对于数组 a 中的每个元素 a[i]，代码通过 count[a[i] - min]++ 将 a[i] 的出现次数记录在 count 数组的相应位置上。这里减去 min 是为了将 a 中的值映射到 count 数组的有效索引范围内。

for (int i = 0; i < n; i++)//遍历原数组，将数据出现的次数写入count数组对应的位置
{
	count[a[i] - min]++;//核心代码1
}

4. 排序

代码遍历 count 数组，并根据每个值出现的次数，将对应的值依次放回原数组 a 中。这里使用了一个双层循环，外层循环遍历 count 数组的每个索引（即待排序数组中的每个可能值），内层循环（通过 while 循环实现）则根据 count[j] 的值（即该值出现的次数）将 j + min（即原始值）放回原数组 a 中。每次放回一个值后，count[j] 递减，直到该值的所有出现都被放回原数组。

int i = 0;
for (int j = 0; j < size; j++)//遍历count数组，根据数据出现次数，将数据写入原数组对应的位置
{
	while (count[j]--)//每写入一次，次数--
	{
		a[i++] = j + min;//核心代码2
	}
}

5. 清理资源

最后，代码释放了 count 数组占用的内存，并将其指针设置为 NULL，以避免野指针问题。

free(count);
count = NULL;

四、C语言实现代码

🍃计数排序升序代码

void CountSort1(int* a, int n)//计数排序升序
{
	int min = INT_MAX;
	int max = INT_MIN;
	for (int i = 0; i < n; i++)//求得最大值和最小值
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int size = max - min + 1;
	int* count = (int*)calloc(size, sizeof(int));//根据数据范围申请空间
	if (count == NULL)
	{
		perror("calloc fail\n");
		return;
	}

	for (int i = 0; i < n; i++)//遍历原数组，将数据出现的次数写入count数组对应的位置
	{
		count[a[i] - min]++;//核心代码1
	}

	int i = 0;
	for (int j = 0; j < size; j++)//遍历count数组，根据数据出现次数，将数据写入原数组对应的位置
	{
		while (count[j]--)//每写入一次，次数--
		{
			a[i++] = j + min;//核心代码2
		}
	}

	free(count);
	count = NULL;
}

🍃计数排序降序代码

void CountSort2(int* a, int n)//计数排序降序
{
	int min = INT_MAX;
	int max = INT_MIN;
	for (int i = 0; i < n; i++)//求得最大值和最小值
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int size = max - min + 1;
	int* count = (int*)calloc(size, sizeof(int));//根据数据范围申请空间
	if (count == NULL)
	{
		perror("calloc fail\n");
		return;
	}

	for (int i = 0; i < n; i++)//遍历原数组，将数据出现的次数写入count数组对应的位置
	{
		count[a[i] - min]++;//核心代码1
	}

	int i = 0;
	for (int j = size-1; j >=0; j--)//遍历count数组，根据数据出现次数，将数据写入原数组对应的位置
	{
		while (count[j]--)//每写入一次，次数--
		{
			a[i++] = j + min;//核心代码2
		}
	}

	free(count);
	count = NULL;
}

五、性能分析

🍃时间复杂度：O(n + k)，近似于O(n) 计数排序的时间复杂度主要由以下几个部分组成：

1. 确定数据范围：遍历一次待排序数组，找出最大值和最小值，这个过程的时间复杂度是O(n)，其中n是数组的长度。
2. 初始化计数数组：根据最大值和最小值确定计数数组的大小，并初始化所有元素为0。这一步的时间复杂度主要取决于计数数组的大小，但因为是常数时间操作（尽管这个“常数”可能很大，但它不随n的变化而变化），所以通常认为它是O(1)的，但更准确地说，它是O(k)，其中k是数据范围的大小（即最大值和最小值之间的差值加1）。然而，在分析计数排序的时间复杂度时，我们更关注n，因此这一步通常被忽略或视为O(1)。
3. 统计元素频率：再次遍历待排序数组，统计每个元素的出现次数，并将结果存储在计数数组中。这一步的时间复杂度是O(n)。
4. 累加计数（隐含步骤）：在计数排序的某些实现中，这一步是显式的，但在你的代码中，它是隐含的，因为你在填充原数组时直接使用了计数数组的信息。无论是否显式进行，这一步的时间复杂度都是O(k)。然而，由于我们更关注n，且k通常远小于n（对于实际应用中的许多情况），这一步的时间复杂度通常被忽略。
5. 排序：遍历计数数组，根据元素的出现次数将元素放回原数组。这一步的时间复杂度是O(n + k)，因为你需要遍历计数数组（O(k)）并将元素放回原数组（O(n)）。但是，由于k通常远小于n，且这一步是计数排序中唯一与n直接相关的步骤（除了确定数据范围），所以这一步的时间复杂度通常简化为O(n)。

综上所述，计数排序的总时间复杂度是O(n + k)。然而，在实际应用中，由于k通常远小于n（例如，当排序的是一定范围内的整数时），计数排序的性能可以近似地看作是线性的，即O(n)。

🍃空间复杂度：O(k) 计数排序的空间复杂度主要取决于计数数组的大小，即O(k)，其中k是数据范围的大小。如果k与n相比很大，那么计数排序可能会消耗大量的内存。因此，计数排序只适用于数据范围不是很大的情况。

🍃稳定性：稳定 计数排序能够保持相等元素的相对顺序不变，即它是稳定的排序算法。 计数排序通过统计每个元素的出现次数，并根据这些统计信息来重建排序后的数组。在这个过程中，如果两个元素的值相等，它们会被放入计数数组的同一个位置（或者更准确地说，是相邻的位置，因为计数数组会记录每个值出现的次数），并且在重建排序后的数组时，这些相等的元素会按照它们在原数组中的顺序被依次放回。

六、计数排序优缺点分析

优点

1. 稳定性：计数排序是稳定的排序算法。如果两个元素相等，它们在排序后的数组中的相对位置与排序前相同。
2. 高效性：在数据范围不是很大的情况下，计数排序的时间复杂度可以认为是线性的，即O(n+k)，其中n是数组的长度，k是数据范围的大小。这使得计数排序在处理具有明确范围且分布相对均匀的整数数据时非常高效。
3. 易于实现：计数排序的实现相对简单直观，不需要复杂的比较和交换操作。
4. 适用场景广泛：计数排序不仅适用于整数排序，还可以扩展到其他类型的数据排序，只要能够确定数据的范围并且数据分布相对均匀即可。

缺点

1. 空间复杂度高：计数排序需要额外的空间来存储计数数组，这个数组的大小取决于数据的范围。如果数据的范围很大，那么计数数组将占用大量的内存空间，可能导致内存溢出。
2. 数据范围限制：计数排序要求能够确定数据的范围，这限制了它的应用场景。如果数据的范围很大或者无法确定，那么计数排序可能不是一个好的选择。
3. 对重复数据敏感：当数据中存在大量重复元素时，计数排序的效率会受到影响，因为计数数组中的某些位置会被多次更新。然而，这通常不会显著影响总体性能，因为排序过程仍然是线性的。
4. 非原地排序：计数排序不是原地排序算法，因为它需要额外的空间来存储计数数组。这可能会在某些内存受限的环境下成为问题。

总结

计数排序是一种高效的排序算法，特别适用于一定范围内的整数排序。它的稳定性和高效性使得它在处理特定类型的数据时非常有用。然而，计数排序的空间复杂度较高，且对数据范围有一定的限制，这限制了它的应用范围。在选择排序算法时，需要根据具体的应用场景和数据特性来决定是否使用计数排序。如果数据范围明确且分布相对均匀，且内存空间足够，那么计数排序是一个很好的选择。