数据结构 ——— 计数排序算法的实现

目录

计数排序算法的思想

计数排序算法的实现

---

计数排序算法的思想

遍历数组，找出数组中的最大值 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，才是原数组中的值

代码验证：