【数据结构】排序算法---计数排序（动图演示）_计数排序动图

文章目录

• 1. 定义
• 2. 算法步骤
• 3. 动图演示
• 4. 性质
• 5. 算法分析
• 6. 代码实现
• • C语言
  • Python
  • Java
  • Go
• 结语

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+1 bucket = [0]*bucketLen sortedIndex =0 arrLen = len(arr) for i in range(arrLen): if not bucket[arr[i]]: bucket[arr[i]]=0 bucket[arr[i]]+=1 for j in range(bucketLen): while bucket[j]>0: arr[sortedIndex] = j sortedIndex+=1 bucket[j]-=1 return arr

Java

public class CountingSort implements IArraySort { @Override public 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 + 1 bucket := make([]int, bucketLen) // 初始为0的数组 sortedIndex := 0 length := len(arr) for i := 0; i < length; i++ { bucket[arr[i]] += 1 } for j := 0; j < bucketLen; j++ { for bucket[j] > 0 { arr[sortedIndex] = j sortedIndex += 1 bucket[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/142375338
基数排序：https://blog.csdn.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564