[数据结构]——非比较排序—计数排序

简介: [数据结构]——非比较排序—计数排序

1.非比较排序——计数排序



思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。


6f8b67933e744c5793680a9f8cdf2230.gif


2.最终实现


1.解析

操作步骤:

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中


找出最大和最小值: 首先遍历数组 a 一次,找到其中的最大值 max 和最小值 min。这一步是为了确定数组中的数值范围,从而决定后续计数数组 count 的大小。

创建计数数组: 根据最大值和最小值计算出数值范围 range = max - min + 1,并用 calloc 动态分配一个大小为 range 的整型数组 count。计数数组的每个元素初始化为0,用于记录原数组中每个数值出现的次数。

统计每个元素的出现次数: 再次遍历原数组 a,对于数组中的每个元素 a[i],计算它与最小值的差值 a[i] - min,并将计数数组中对应索引的位置加1。这样做是因为我们希望 count[0] 存储的是原数组中小于等于 min 的元素数量,count[1] 存储的是原数组中等于 min+1 的元素数量,依此类推,从而避免了因为负数或零而导致的索引错误。

重排元素: 遍历计数数组 count,对于 count[j] 非零的每个元素,将其对应的数值(即 j + min)放回原数组 a 中,同时减少 count[j] 的计数。这里的循环保证了数值会按照原来的顺序被放置回数组,从而维持了稳定性排序。

2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例,手撕分析

image.png


3.代码实现

void CountSort(int* a, int n)
{//找出最大和最小元素
  int min = a[0], max = a[0];
  for (int i = 1; i < n; i++)
  {
  if (a[i] < min)
    min = a[i];
  if (a[i] > max)
    max = a[i];
  }
  int range = max - min + 1;//确定新创建数组的数据个数和原数组大小相同,便于下面计数
  int* count = (int*)calloc(range, sizeof(int));
  if (count == NULL)
  {
  printf("calloc fail\n");
  return;
  }
  // 统计次数
  for (int i = 0; i < n; i++)
  {
  count[a[i] - min]++;//min作为偏移量,然后再在对应数组位置++,统计该数字出现的次数
  }
  // 排序
  int i = 0;
  for (int j = 0; j < range; j++)
  {
  while (count[j]--)
  {
    a[i++] = j + min;
  }
  }
}

4.计数排序具有以下主要特性:

非比较排序算法:计数排序不通过元素间的直接比较来进行排序,而是通过计算元素的分布情况来确定它们的位置,这使得它在最好、最坏和平均情况下都有较好的性能表现。


时间复杂度:计数排序的时间复杂度为O(n+k),其中n是数组长度,k是数组中数据范围(最大值与最小值之差加一)。当k不是很大且远小于n时,计数排序非常高效。


空间复杂度:计数排序需要额外的计数数组,其空间复杂度为O(k),这使得它在处理大数据范围时可能比较消耗内存。


稳定性:计数排序是一种稳定的排序算法。因为它在重新排列元素时能够保持相同值的元素原有的相对顺序不变。


适用范围:最适合于整数或有限范围内的非负整数排序。对于浮点数或负数,虽然理论上可以通过调整使其适用,但实际上并不常见,因为这会增加算法的复杂性。


局限性:计数排序的局限性主要体现在它对数据类型的限制上,不适合非整数类型的数据排序。此外,当数据范围非常大时,所需的额外空间也会非常大,这在资源受限的环境下可能是个问题。


预处理要求:在执行排序前需要先遍历一遍数组以确定数据范围,这一步骤虽然简单,但也构成了算法的一部分开销。


综上,计数排序在特定场景下(如数据范围不大、整数类型)是一种快速且高效的排序选择,但其适用场景相对有限,且空间效率较低。

相关文章
|
2天前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
23 10
|
2天前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
25 10
|
2天前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
22 7
|
3月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
48 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
3月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
36 1
|
3月前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
3月前
|
搜索推荐 C++
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(一)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
3月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
3月前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(三)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理