网站改版影响排名,宝塔一键部署wordpress最新版,临沂的各类网站建设,做网站跟客人怎么沟通目录
计数排序算法的思想
计数排序算法的实现 计数排序算法的思想
遍历数组#xff0c;找出数组中的最大值 max 和 最小值 min
最大值 max 减去最小值 min 再加 1 得出数组元素的范围 range
利用 range 的大小 malloc 一个 count 数组用来计数
再对 count 数组进行初始化…目录
计数排序算法的思想
计数排序算法的实现 计数排序算法的思想
遍历数组找出数组中的最大值 max 和 最小值 min
最大值 max 减去最小值 min 再加 1 得出数组元素的范围 range
利用 range 的大小 malloc 一个 count 数组用来计数
再对 count 数组进行初始化全初始化为 0
在计数时要把原数组的每个元素各自减去最小值 min这样做才能和 count 数组的下标一一对应只要有相同的元素就在对应的位置自增 1 而且以上的做法称之为相对映射
如果原数组的元素是多少就直接映射到 count 数组的对应位置的话这样的映射叫做绝对映射但是这样的映射可能会导致 count 数组多开很多不必要的空间会造成空间浪费
当 count 数组计数完成后再对 count 数组进行遍历遍历 count 数组上的每个元素的个数只要是非 0 的个数那么就在原数组上面覆盖注意覆盖是需要先加 min
最后走完 count 数组时原数组也就完成了排序 计数排序算法的实现
代码演示
void CountSort(int* a, int size)
{/*找到数组中的最小值和最大值*/int min a[0];int max a[0];for (int i 0; i size; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}// 得出元素范围int range max - min 1;// 开辟 range 个空间用来计数int* countArr (int*)malloc(sizeof(int) * range);// 判断是否开辟成功if (countArr NULL){perror(malloc fail);return;}// 初始化为 0memset(countArr, 0, sizeof(int) * range);// 计数for (int i 0; i size; i){countArr[a[i] - min];}// 排序int k 0;for (int i 0; i range; i){while (countArr[i]--){a[k] i min;}}
}
代码解析
解析countArr[a[i] - min]
用 i 遍历原数组 a 中的每个值再减去最小值 min 得到的就是 [0,range] 区间的值
那么 [0,range] 区间也就是 countArr 数组下标对应的值因为初始是 0 所以通过 countArr[a[i] - min] 找到后直接即可
最后再排序排 countArr 数组中非 0 元素的值再一一覆盖到 a 数组注意覆盖时要加上最小值 min才是原数组中的值
代码验证
