【数据结构】排序算法---计数排序

1. 定义

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

2. 算法步骤

算法的步骤如下：

• （1）找出待排序的数组中最大和最小的元素
• （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

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

3. 动图演示

4. 性质

稳定性：

计数排序是一种稳定的排序算法。

空间复杂度：

计数排序的空间复杂度为$O(range)$

时间复杂度：

计数排序的时间复杂度为$O(n+range)$, 其中range代表待排序数据的值域大小，也就是下面算法分析中的k

5. 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是$O(n+k)$，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

6. 代码实现

C语言

void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] > max)max = a[i];if (a[i] < min)min = 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;}}
}

Python

def countingSort(arr, maxValue):bucketLen = maxValue+1bucket = [0]*bucketLensortedIndex =0arrLen = len(arr)for i in range(arrLen):if not bucket[arr[i]]:bucket[arr[i]]=0bucket[arr[i]]+=1for j in range(bucketLen):while bucket[j]>0:arr[sortedIndex] = jsortedIndex+=1bucket[j]-=1return arr

Java

public class CountingSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int maxValue = getMaxValue(arr);return countingSort(arr, maxValue);}private int[] countingSort(int[] arr, int maxValue) {int bucketLen = maxValue + 1;int[] bucket = new int[bucketLen];for (int value : arr) {bucket[value]++;}int sortedIndex = 0;for (int j = 0; j < bucketLen; j++) {while (bucket[j] > 0) {arr[sortedIndex++] = j;bucket[j]--;}}return arr;}private int getMaxValue(int[] arr) {int maxValue = arr[0];for (int value : arr) {if (maxValue < value) {maxValue = value;}}return maxValue;}}

Go

func countingSort(arr []int, maxValue int) []int {bucketLen := maxValue + 1bucket := make([]int, bucketLen) // 初始为0的数组sortedIndex := 0length := len(arr)for i := 0; i < length; i++ {bucket[arr[i]] += 1}for j := 0; j < bucketLen; j++ {for bucket[j] > 0 {arr[sortedIndex] = jsortedIndex += 1bucket[j] -= 1}}return arr
}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564