排序--非比较排序之计数排序

loreal8

于 2020-05-11 17:22:40 发布

阅读量178

点赞数

分类专栏：排序

本文链接：https://blog.csdn.net/loreal8/article/details/106058573

版权

排序专栏收录该内容

11 篇文章

订阅专栏

本文深入讲解计数排序算法，分析其时间复杂度O(max(n,范围))和空间复杂度O(范围)，并探讨其稳定性及数据敏感性。通过具体代码实现，展示如何统计数据范围，开辟辅助空间进行计数，以及如何恢复原始数据。适用于小范围数据排序，但当数据范围增大时，空间复杂度将显著提升。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

计数排序

时间复杂度：O(max(n,范围))
空间复杂度：O(范围)
稳定：一般教材认为是稳定的
数据敏感：不敏感
计数排序：只适合小范围数据，如果范围大，空间复杂度较高

void countSort(int* array, int n)
{
 // 1, 2, 3,   1000000
 //统计范围
 int min = array[0], max = array[0];
 for (int i = 1; i < n; ++i)
 {
  if (array[i] > max)
   max = array[i];
  if (array[i] < min)
   min = array[i];
 }
 int range = max - min + 1;
 //开辅助空间，进行计数
 int* countArr = (int*)malloc(sizeof(int)* range);
 //初始化为0
 memset(countArr, 0, sizeof(int)* range);
 //统计次数
 for (int i = 0; i < n; ++i)
 {
  countArr[array[i] - min]++;
 }
 //恢复数据， 遍历计数数组
 int idx = 0;
 for (int i = 0; i < range; ++i)
 {
  while (countArr[i]--)
  {
   array[idx++] = i + min;
  }
 }
 free(countArr);
}