深圳手机建站模板,网站建设后运维合同,网站备案查询流程,WordPress多人聊天插件文章目录 1. 定义2. 算法步骤3. 动图演示4. 性质5. 算法分析6. 代码实现C语言PythonJavaGo 结语 1. 定义
计数排序又称为鸽巢原理#xff0c;是对哈希直接定址法的变形应用。计数排序不是基于比较的排序算法#xff0c;其核心在于将输入的数据值转化为键存储在额外开辟的数组… 文章目录 1. 定义2. 算法步骤3. 动图演示4. 性质5. 算法分析6. 代码实现C语言PythonJavaGo 结语 1. 定义
计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。计数排序不是基于比较的排序算法其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。 2. 算法步骤
算法的步骤如下
1找出待排序的数组中最大和最小的元素2统计数组中每个值为i的元素出现的次数存入数组C的第i项3对所有的计数累加从C中的第一个元素开始每一项和前一项相加4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 3. 动图演示 4. 性质
稳定性
计数排序是一种稳定的排序算法。
空间复杂度
计数排序的空间复杂度为 O ( r a n g e ) O(range) O(range)
时间复杂度
计数排序的时间复杂度为 O ( n r a n g e ) O(n range) O(nrange), 其中range代表待排序数据的值域大小也就是下面算法分析中的k
5. 算法分析
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时时间复杂度是 O ( n k ) O(nk) O(nk)其排序速度快于任何比较排序算法。当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 maxValue1bucket [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] jsortedIndex1bucket[j]-1return arrJava
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
