【C语言】排序算法 -------- 计数排序

个人主页

创作不易，感谢大家的关注！

文章目录

• 1. 计数排序的概念
• 2. 计数排序使用场景
• 3. 计数排序思想
• 4. 计数排序实现过程
• 5. 计数排序的效率
• 6. 总结（附源代码）

  1. 计数排序的概念

  计数排序是一种非比较的排序算法，其基本思想是统计待排序元素中小于等于每个元素的个数，从而确定每个元素的位置。

  2. 计数排序使用场景

  计数排序适用于以下几种情况：

  1. 数据的取值范围比较小，序列中最大值和最小值之间的差值不能过大，防止建立数组时造成内存浪费。
  2. 数据是整数类型，不能为浮点数类型。

  3. 计数排序思想

  计数排序的核心是：利用数组的索引是有序的前提下，通过将序列中的元素作为索引，其个数作为值放入数组，遍历数组来排序。

  4. 计数排序实现过程

  方法步骤如下：

  1. 先选出待排序序列中的最小数和最大数。
  2. 给出一个范围range，为 max-min+1。
  3. 创建一个count数组，大小为每个元素的大小。
  4. 遍历待排序数组，统计每个元素出现的次数，并将其存储在count数组中。
  5. 本质是利用count数组的自然序号排序。根据count数组中的元素，遍历依次更新待排序数组中的元素，实现排序。
  6. 统计count数组里的每个元素出现的次数，然后映射给tmp数组。（使用相对映射）
  7. 将tmp数组里不为0的元素的下标+min反赋给数组count,遍历结束,排序完成。

  5. 计数排序的效率

  时间复杂度：O（N+range），N为待排序序列的长度，range为max-min+1的大小。

  空间复杂度：O（range）。

  稳定性：稳定。

  6. 总结（附源代码）

  #define _CRT_SECURE_NO_WARNINGS 1
  void PrintArray(int* a, int n);
  void CountSort(int* a, int n);
  void PrintArray(int* a, int n)
  {
  	for (int i = 0; i  max)
  		{
  			max = a[i];
  		}
  	}
  	int range = max - min + 1;
  	int* count = (int*)calloc(range,sizeof(int));
  	if (count == NULL)
  	{
  		perror("calloc fail");
  		return;
  	}
  	// 统计次数
  	for (int i = 0; i  
  今天的分享就到这里啦，感谢大家的支持，我们下次再见！