这个 计数排序详解过程 我能吹一辈子!!!

news/2024/10/30 19:24:49/

文章目录

  • 计数排序概念
  • 计数排序算法思路
  • 计数排序算法过程
  • 计数排序代码实现
  • 计数排序缺陷

计数排序概念

计数排序是一个非基于比较的排序算法,元素从未排序状态变为已排序状态的过程,是由额外空间的辅助和元素本身的值决定的。该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法,而且当 的时候其效率反而不如基于比较的排序,因为基于比较的排序的时间复杂度在理论上的下限是 。

计数排序算法思路

顾名思义,该算法不是通过比较数据的大小来进行排序的,而是通过统计数组中相同元素出现的次数,然后通过统计的结果将序列回收到原来的序列中。

动图展示:
在这里插入图片描述

举个例子:
在这里插入图片描述

上列中的映射方法称为绝对映射,即arr数组中的元素是几就在count数组中下标为几的位置++,但这样会造成空间浪费。例如,我们要将数组:1020,1021,1018,进行排序,难道我们要开辟1022个整型空间吗?
 若是使用计数排序,我们应该使用相对映射,简单来说,数组中的最小值就相对于count数组中的0下标,数组中的最大值就相对于count数组中的最后一个下标。这样,对于数组:1020,1021,1018,我们就只需要开辟用于储存4个整型的空间大小了,此时count数组中下标为i的位置记录的实际上是1018+i这个数出现的次数。

总结
 绝对映射:count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
 相对映射:count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。

计数排序算法过程

1 根据待排序集合中最大元素和最小元素的差值范围,申请额外空间;
2.遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;
3.对额外空间内数据进行计算,得出每一个元素的正确位置;
4.将待排序集合每一个元素移动到计算得出的正确位置上。

先假设 20 个数列为:{9, 3, 5, 4, 9, 1, 2, 7, 8,1,3, 6, 5, 3, 4, 0, 10, 9, 7, 9}。

让我们先遍历这个无序的随机数组,找出最大值为 10 和最小值为 0。这样我们对应的计数范围将是 0 ~ 10。然后每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。

比如第一个整数是 9,那么数组下标为 9 的元素加 1,如下图所示。

在这里插入图片描述

第二个整数是 3,那么数组下标为 3 的元素加 1,如下图所示。

在这里插入图片描述

继续遍历数列并修改数组…。最终,数列遍历完毕时,数组的状态如下图。

在这里插入图片描述

数组中的每一个值,代表了数列中对应整数的出现次数。

有了这个统计结果,排序就很简单了,直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次。比如统计结果中的 1 为 2,就是数列中有 2 个 1 的意思。这样我们就得到最终排序好的结果。

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

计数排序代码实现

代码示例:

//计数排序
void CountSort(int* a, int n)
{int min = a[0];//记录数组中的最小值int max = a[0];//记录数组中的最大值for (int i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;//min和max之间的自然数个数(包括min和max本身)int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间,并将内存空间置0if (count == NULL){printf("malloc fail\n");exit(-1);}//统计相同元素出现次数(相对映射)for (int i = 0; i < n; i++){count[a[i] - min]++;}int i = 0;//根据统计结果将序列回收到原来的序列中for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}free(count);//释放空间
}

时间复杂度:O(N+range)  
空间复杂度:O(range)

计数排序缺陷

虽然计数排序看上去很强大,但是它存在两大局限性

1.当数列最大最小值差距过大时,并不适用于计数排序

比如给定 20 个随机整数,范围在 0 到 1 亿之间,此时如果使用计数排序的话,就需要创建长度为 1 亿的数组,不但严重浪费了空间,而且时间复杂度也随之升高。

2.当数列元素不是整数时,并不适用于计数排序

如果数列中的元素都是小数,比如 3.1415,或是 0.00000001 这样子,则无法创建对应的统计数组,这样显然无法进行计数排序。


http://www.ppmy.cn/news/104093.html

相关文章

tidyverse中filter行筛选时缺失值存在的一个坑

大家好&#xff0c;我是邓飞&#xff0c;好久没有更新博客了&#xff0c;是因为好久没有进步了。 之前我认为鲁迅说的对&#xff0c;他在《野草》中写道&#xff1a;“当我沉默着的时候&#xff0c;我觉得充实&#xff1b;我将开口&#xff0c;同时感到空虚”。现在确切的情况…

python爬虫之多线程、多进程、多协程对比

Python爬虫通常需要处理大量的数据和网络请求&#xff0c;因此在爬虫中使用多线程、多进程和多协程可以大大提高爬虫的效率和速度。在本篇文章中&#xff0c;我们将详细介绍Python爬虫中的多线程、多进程和多协程的概念&#xff0c;优缺点以及如何选择合适的方案。 一、多线程…

刷了一个月面试题,终于拿到了字节跳动的offer

前言: 最近金三银四跳槽季&#xff0c;相信很多小伙伴都在面试找工作&#xff0c; 怎样才能拿到大厂的offer&#xff0c;没有掌握绝对的技术&#xff0c;那么就要不断的学习 如何拿下阿里等大厂的offer的呢&#xff0c;今天分享一个秘密武器&#xff0c;资深测试工程师整理的…

Qt 6多媒体(Multimedia)模块变动:重塑与创新

一、Qt 6多媒体模块的转变与升级 Qt 6 是一个有意识地努力使框架更有效和易于使用的结果。尽管我们试图在每个版本中维持所有公共API的二进制和源代码兼容性&#xff0c;但为了使Qt成为一个更好的框架&#xff0c;一些改变是不可避免的。 Qt 6的Qt Multimedia模块替换了Qt 5.…

【chatGPT4结对编程】chatGPT4教我做图像分类

开始接触深度学习 大语言模型火了之后&#xff0c;我也想过是否要加入深度学习的行业当中来&#xff0c;一开始的想法就是AI大模型肯定会被各大厂垄断&#xff0c;我们作为普通应用型软件工程师直接调用api就完事&#xff0c;另外对自己的学历也自卑(刚刚够线的二本&#xff0…

移除元素的两种方法

今日复习了数组部分&#xff0c;对以下题目做了一个整理。 27. 移除元素 这里将不再详细讲述两层for循环的暴力算法。其大致思路是&#xff1a;第一层for循环遍历每一个元素&#xff0c;找到值为val的元素之后&#xff0c;从该位置将每一个元素往前移动一位进行覆盖&#xff1…

ssh无密码链接

ssh的基本语法为 ssh host 然后输入密码才可以 如果a想要免密登录b&#xff0c;则a需要将自己的公钥放在b上&#xff0c;原理如下图&#xff1a; 例如&#xff0c;以aricoder这个用户登录的情况下&#xff0c;在服务器01上生成密钥&#xff0c;命令为 ssh-keygen -t rsa然后连…

python基础知识(三):比较运算符、布尔运算符和位运算

目录 1. 比较运算符2. 布尔运算符3. 位运算 1. 比较运算符 比较运算符通常为以下6种&#xff1a; (1) 大于">“&#xff0c;比较两个数a、b的大小&#xff0c;比较的结果如果a大于b则为True&#xff0c;否则为False&#xff1b; (2) 大于等于”>“&#xff0c;比较…