非比较排序之计数排序

目录

一、什么是计数排序

二、思路

三、代码实现

---

一、什么是计数排序

计数排序是一种非比较型的排序算法，它通过统计待排序数据中每个元素出现的次数，然后根据这个次数来进行排序。计数排序的具体步骤如下：

1. 首先找出待排序数据中的最大值和最小值。
2. 创建一个新的数组，长度为最大值和最小值之间的范围，并初始化为0。
3. 遍历待排序数组，统计每个元素出现的次数，存储到新数组对应位置。
4. 根据新数组中统计的次数，将数据重新排列得到排序后的数组。

计数排序适用于数据范围相对较小且数据比较集中的情况，它的时间复杂度为O(n+k)，其中n为数据数量，k为数据范围。计数排序是稳定的排序算法，它不是基于比较的排序方法，因此在某些情况下可以比快速排序和归并排序等比较排序算法更快。但是计数排序需要额外的空间用于存储计数，所以在数据范围非常大的情况下可能会占用大量内存。

二、思路

将一组数据相对映射到一个数组中，通过数组建立索引来排序。不需要像基数排序一样存储原数据，只需要得到相对映射值加上最小值即为当前值。

具体步骤：

1. 找到最大最小值，计算需要开辟的索引数组空间的大小
2. 建立索引：每一个值减去基准值得到了索引数组的下标
3. 排序：遍历索引数组，其中不为0的元素即为排好的数据。复原只需要加上基准值即可

三、代码实现

void CountSort(int* a,int n)
{//遍历找最大最小值int max = a[0];int min = a[0];for (int i = 0; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}//开辟基准数组int size = max - min + 1;int* tmp = (int*)malloc(sizeof(int) * size);if (tmp == NULL){perror(malloc);exit(1);}memset(tmp, 0, sizeof(int) * size);//建立索引for (int j = 0; j < n; j++){tmp[a[j] - min]++;}//排序int q = 0;for (int m = 0; m < size; m++){while (tmp[m]--){a[q++] = m + min;}}
}