5g站长工具seo综合查询,wordpress关于我们插件,wordpress 标签手册,深圳高端响应式网站#x1f3a5; 屿小夏 #xff1a; 个人主页 #x1f525;个人专栏 #xff1a; 算法—排序篇 #x1f304; 莫道桑榆晚#xff0c;为霞尚满天#xff01; 文章目录 #x1f4d1;前言#x1f324;️计数排序的概念☁️什么是计数排序#xff1f;☁️计数排序思想⭐绝对… 屿小夏 个人主页 个人专栏 算法—排序篇 莫道桑榆晚为霞尚满天 文章目录 前言️计数排序的概念☁️什么是计数排序☁️计数排序思想⭐绝对映射⭐相对映射 ️计数排序的实现☁️实现思路☁️代码实现☁️代码解析 ️计数排序特性总结☁️时间复杂度☁️空间复杂度☁️稳定性☁️适用性限制☁️不适用于大规模数据☁️总结 ️全篇总结 前言 什么是计数排序计数排序的思想是什么它是如何实现的 本文会对计数排序进行由浅入深的探究让你彻底掌握计数排序 ️计数排序的概念
☁️什么是计数排序
计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。
统计每个元素出现的次数然后根据元素的大小顺序将它们放入正确的位置。
☁️计数排序思想
计数排序是一种小众的排序,它适合于数据密集的场景,按最大数的数值来开空间。
⭐绝对映射
假设现有一组数据,最大的数据是1000,那么便会开一千个大小的空间,这种属于绝对映射,在极端的场景下,极易造成空间上的浪费比如现在有5,99,88,1000,8888,452,635,82,777,555,只有10个数但是最大的数是8888因此要开8888大小的空间,剩余的空间全部都浪费了。
⭐相对映射
因此绝大多数情况下,都会使用相对映射。
具体的步骤如下
找出待排序数组中的最大值和最小值并创建一个计数数组长度为最大值和最小值之差加1。遍历待排序数组统计每个元素出现的次数并将次数存储在计数数组的相应位置上。对计数数组进行累加操作得到每个元素在排序后数组中的最终位置。创建一个与待排序数组长度相同的临时数组用于存储排序后的结果。从后向前遍历待排序数组根据计数数组中每个元素的值将元素放入临时数组的相应位置上。将临时数组中的元素复制回待排序数组完成排序。 ️计数排序的实现
☁️实现思路
找到数组中的最小值和最大值以确定计数数组的大小。然后根据最小值和最大值计算计数数组的大小并分配内存空间。接下来将计数数组的所有元素初始化为0。然后遍历原数组统计每个元素出现的次数将统计结果保存在计数数组中。接着使用两个循环将计数数组中的元素按照次数依次放回原数组中。最后释放计数数组的内存空间。
☁️代码实现
//计数排序
void CountSort(int* a, int n)
{int min a[0];int max a[0];for (int i 0; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* count (int*)malloc(sizeof(int) * range);if (count NULL){perror(malloc fail);exit(-1);}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;}}
}☁️代码解析
寻找最小值和最大值 首先通过循环遍历输入数组 a找到数组中的最小值 min 和最大值 max。这是为了确定排序范围。确定排序范围 计算排序范围 range即 (max - min 1)这表示需要排序的整数范围。创建计数数组 使用 malloc 函数为计数数组 count 分配内存该数组的大小是排序范围 range。计数数组用于存储每个整数在输入数组中出现的次数。初始化计数数组 使用 memset 函数将计数数组 count 中的所有元素初始化为0。计数 遍历输入数组 a对于每个整数 a[i]将其减去 min 的值作为索引然后在计数数组中对应索引位置的值加1。这一步会统计每个整数在输入数组中出现的次数。重构排序数组 使用两个循环首先遍历计数数组 count然后在内部循环中根据计数数组中的值将相应数量的整数值还原到原始输入数组 a。这将完成排序过程。
️计数排序特性总结
☁️时间复杂度
计数排序的时间复杂度为 O(nk)其中 n 是输入数组的大小k 是整数的范围。它具有线性时间复杂度的优点适用于整数排序特别是当整数范围相对较小且分布均匀时。
☁️空间复杂度
计数排序的空间复杂度取决于整数范围为 O(k)。因此它需要额外的空间来存储计数数组当整数范围较大时可能会占用较多内存。
☁️稳定性
计数排序是一种稳定的排序算法。稳定性意味着具有相同值的元素在排序后仍保持相对顺序不变。在计数排序中具有相同值的元素会按照它们在输入数组中的顺序被放置在输出数组中。
☁️适用性限制
计数排序仅适用于整数排序特别是当整数范围相对较小且分布均匀时。它不适用于排序包含负数或浮点数的数组。此外如果整数范围过大可能会导致内存占用过多。
☁️不适用于大规模数据
尽管计数排序具有线性时间复杂度的优点但它对于大规模数据集的排序可能并不理想。当整数范围非常大且分布不均匀时计数排序的性能可能会受到限制。
☁️总结
计数排序适用于特定范围内的整数排序并且在这种情况下具有稳定的性能表现。然而在应用计数排序时需要仔细考虑整数范围和数据集的分布情况以确保不会出现内存占用过大或性能下降的情况。
️全篇总结
本章专门对计数排序从概念到实现进行了细致入微的讲解期望对你理解掌握计数有所帮助
看到这里希望给博主留个:点赞收藏⭐️关注 你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
