计数排序-C语言实现

本文主要是介绍计数排序-C语言实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

计数排序是速度特别快的一种排序方式，甚至说可以达到o（n），什么概念，一趟就可以实现，这是很快的，虽然具备一定的局限性，但是这个速度也是叹为观止的

计数排序gif

实现图解

这里的核心逻辑就在于，我们需要入数组和出数组这两点

代码实现
//计数排序
void Countsort(int* a, int n)
{//求出最小值和最大值int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}//计算差值,需要最小值和最大值//0 1 2三个数值，但是2-1=2，也就是两个数值，所以我们需要+1 ,这个差值也就是我们开辟多大的空间int delta = max - min + 1;//创建数组空间int* tmp = (int*)calloc(delta, sizeof(int));if (tmp == NULL){perror("Countsort:tmp:err:");exit(1);//正常退出}//把原数组里面的数值计算之后->存放到tmp数组里面,但是需要控制差值存放在数组里面for (int i = 0; i < n; i++){tmp[a[i] - min]++;}//从数组读取出，放到原数组里面int j = 0;for (int i = 0; i < delta; i++){while (tmp[i]--){a[j++] = i + min;}}
}
解释：

求最小值和最大值：

首先初始化 max 和 min 为数组的第一个元素的值。
遍历整个数组 a，更新 max 和 min 为数组中的最大值和最小值。

计算差值：

计算最大值和最小值的差值 delta，这个差值加1后将用于确定计数数组 tmp 的大小。

创建计数数组：

使用 calloc 分配一个大小为 delta 的数组 tmp，并将所有元素初始化为0。calloc 会初始化分配的内存为0，这对于计数排序是必要的。

计数：

遍历原数组 a，对于数组中的每个元素 a[i]，计算其与最小值 min 的差值，并在 tmp 数组的相应位置增加计数。例如，如果 a[i] 是3，且 min 是0，则 tmp[3] 会增加1。

输出排序结果：

使用两个指针 i 和 j，i 用于遍历 tmp 数组，j 用于指向原数组 a 的当前位置。
对于 tmp 数组中的每个非零元素，将其对应的值加回到原数组 a 中，直到 tmp[i] 减至0。这意味着将 min + i 赋值给 a[j]，然后 j 增加，重复这个过程直到 tmp[i] 为0。

结束排序：

当所有计数都减至0时，原数组 a 已经是部分有序的，排序完成。

错误处理：

如果 calloc 分配内存失败，使用 perror 打印错误信息，并调用 exit 退出程序。

计数排序的时间复杂度是 O(n + k)，其中 n 是数组 a 的长度，k 是整数的范围（在这个例子中是 delta）。由于 k 通常远小于 n，计数排序对于大量数据的排序非常高效。然而，计数排序的空间复杂度也是 O(k)，如果整数的范围非常大，它可能需要大量的内存。

计数排序是一种稳定的排序算法，它不会改变相等元素的相对顺序。它特别适用于当数据范围不大且数据量很大时的场景。

时间复杂度

寻找最大值和最小值：遍历整个数组以找到最大值和最小值，这个过程的时间复杂度是 O(n)，其中 n 是数组中元素的数量。

创建计数数组：使用 calloc 为计数数组分配内存并初始化，这个操作的时间复杂度是 O(k)，其中 k 是最大值和最小值的差值加 1（即整数的范围）。

计数：再次遍历数组，将每个元素的计数在计数数组中增加。这个过程的时间复杂度也是 O(n)。

输出排序结果：最后，根据计数数组重建排序后的数组。这个过程涉及遍历计数数组，并且对于每个非零计数，将对应的元素值放入原数组中。如果计数数组中的非零元素数量接近 n，则这个操作的时间复杂度接近 O(n)。

综合上述步骤，计数排序的总时间复杂度主要由以下两个 O(n) 操作决定：

寻找最大和最小值
计数和输出排序结果

因此，计数排序的总时间复杂度是 O(n + k)。然而，实际上，当 k（整数的范围）远小于 n 时，k 可以被视为一个常数，所以时间复杂度可以简化为 O(n)。但是，如果 k 很大，接近或大于 n，时间复杂度就接近 O(n + k)。

计数排序的空间复杂度是 O(k)，因为需要额外的计数数组来存储每个可能整数的出现次数。如果 k 非常大，这可能会成为一个问题。