当前位置: 首页 > news >正文

计数,桶与基数排序

 

目录

 

一. 计数排序

概念

 步骤思路如下

 实现代码如下

时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

计数排序的特点

二. 桶排序

概念 

 步骤思路如下

实现代码如下 

时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

桶排序的特点

 三. 基数排序

概念

步骤思路如下

实现代码如下

时间复杂度与空间复杂度

1. 时间复杂度

2. 空间复杂度

基数排序的特点


一. 计数排序

概念

计数排序是一种非比较排序算法,它的基本思想是利用数组下标的有序性,将元素作为计数数组的相应下标,并在该下标位置存储相应的元素数量,最后根据计数数组填充待排序数组

 步骤思路如下

1. 找出待排序数组中的最大值和最小值
遍历待排序数组,找出其中的最大值和最小值。

2. 创建计数数组
创建一个新的计数数组,其大小为(最大值 - 最小值 + 1)。
初始化计数数组的所有元素为0。

3. 统计元素出现的次数
再次遍历待排序数组,对于数组中的每个元素,将其值减去最小值(为了使得计数数组的下标从0开始),并将计数数组中对应下标的值加1。

4. 利用计数数组排序
从后向前遍历待排序数组(从大到小是为了保证稳定性,即相同元素在排序后保持原有顺序)。
对于每个元素,将其值减去最小值,然后利用计数数组找到其在排序后数组中的位置,并将该元素放到正确的位置上。
同时,将计数数组中对应位置的值减1,表示该位置已经被占用。

5. 完成排序

 实现代码如下
void CountSort(int* a,int n)
{int max=a[0], 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* tmp = (int*)calloc(max - min +1, sizeof(int));//自动将值其置为0for (int i = 0; i < n; i++){tmp[a[i] - min]++;}int count = n-1;for (int i =  max - min; i >=0; i--){while (tmp[i]--) {a[count--] = i + min;}}free(tmp);tmp = NULL;
}
时间复杂度与空间复杂度
1. 时间复杂度

统计元素出现次数的时间复杂度为 O(n)。

根据计数数组进行排序的时间复杂度为 O(n)。

综上所述计数排序的时间复杂度为一般 O(n)

2. 空间复杂度

由于计数排序需要额外的空间来存储计数数组

所以计数排序的空间复杂度主要取决于计数数组的大小,即 n。因此,计数排序的空间复杂度为 O(n)

计数排序的特点

计数排序适用于待排序数组中的元素为非负整数(负数不是不能排),并且元素的取值范围不大于计算机可以表示的最大范围。
如果待排序数组中的元素是负数,或者元素的取值范围较大,计数排序可能不适用,因为它需要额外的空间来存储计数数组。
计数排序是一种稳定的排序算法,即相同元素在排序后保持原有的顺序

计数排序的时间复杂度为O(n),其中n是待排序数组的长度

二. 桶排序

概念 

桶排序是一种分配式排序算法,它将待排序的数据分到有限数量的桶子里。每个桶子再个别排序(可能使用别的排序算法或以递归方式继续使用桶排序进行排序)。当要被排序的数组内的数值是均匀分布的时候,桶排序使用线性时间(O(n))

 步骤思路如下

1.创建n个桶

2. 将待排序元素分散到各个桶中

3. 对每个桶内的元素排序(可以使用别的排序算法)

4. 读取每个桶的元素,按顺序放回原数组中

实现代码如下 
#define BUCKET_SIZE 100
#define MAX_NUM 10
void BucketSort(int arr[], int n) {if (n <= 1) {return;}int bucket[BUCKET_SIZE][MAX_NUM / BUCKET_SIZE + 1]; // 桶数组,每个桶的大小为MAX_NUM/BUCKET_SIZE+1int bucketIndex[BUCKET_SIZE] = { 0 }; // 每个桶的当前元素数量// 将元素放入对应的桶中for (int i = 0; i < n; i++) {int index = arr[i] / BUCKET_SIZE; // 计算桶的索引bucket[index][bucketIndex[index]++] = arr[i]; // 将元素放入桶中}// 对每个桶进行排序for (int i = 0; i < BUCKET_SIZE; i++) {if (bucketIndex[i] > 0) {InsertSort(bucket[i], bucketIndex[i]); // 使用插入排序对桶内元素进行排序// 将桶内元素放回原数组for (int j = 0; j < bucketIndex[i]; j++) {arr[i * (MAX_NUM / BUCKET_SIZE + 1) + j] = bucket[i][j];}}}
}
时间复杂度与空间复杂度
1. 时间复杂度

①最坏情况

若数据的分布非常不均匀,几乎所有的元素都进入一个桶中,那么桶排序时间复杂度为O(N²)

②最好情况

如果数据分布非常均匀,每个桶中元素数量大致相同,并且使用其他排序算法也达到最佳的时间复杂度,那桶排序时间复杂度为O(N)

③平均情况

平均情况下桶排序时间复杂度大概为O(N)

2. 空间复杂度

空间复杂度大概为O(N+M),其中M为桶的数量,N为开辟数组长度

桶排序的特点

适用于大量数据的排序,是一种高效的排序算法。相比于比较排序算法,桶排序不需要进行元素之间的比较,因此在某些情况下可以更快地完成排序。


是稳定的排序算法,相同元素的相对顺序不会改变。


需要额外的空间来存储桶,如果待排序元素数量较大,可能会占用较多的内存空间

适用于待排序元素分布均匀的情况。对于分布不均匀的数据,可能导致桶的数量不均衡,影响排序效率。

适用场景
例如在对年龄、成绩等具有一定范围的数据进行排序时。当待排序元素数量较大,且数据分布较为均匀时,桶排序可以提供较高的排序效率

 三. 基数排序

概念

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较,直至完成最高位比较

步骤思路如下

1. 寻找待排序数组中最大的数,并确定其是几位数

2. 创建两个数组,一个二维数组,一个一维数组,进入循环,最高位有多少循环多少次(从1开始,因为没有第0位)

3. (使两个数组元素为0)使用一维数组记录当前位的每个数出现的次数

4. 使用前缀和记录下来<=i数字的数量

5. 从后往前遍历存入数据(从大到小是为了保证稳定性,即相同元素在排序后保持原有顺序)。

6. 通过遍历给原数组赋值

7. 重复 2,3,4,5,6 操作直至结束

实现代码如下
int GetDigit(int x,int i)
{int count = x;int n = i;while (--n>0){count /= 10;}count %= 10;return count;
}
void RadixSort(int* a, int n)
{int max=a[0];for (int i = 0; i < n; i++){if (a[i] > max)max = a[i];}int digit1 = 0;while (max){max /= 10;digit1++;}int bucket[10][20];int tmp[20] = { 0 };//桶for(int i = 1;i<=digit1;i++){memset(bucket, 0, sizeof(bucket));memset(tmp, 0, sizeof(tmp));for (int j = 0; j < n; j++){int digit2 = GetDigit(a[j], i);tmp[digit2]++;}for (int j = 1; j < 10; j++)//前缀和记录桶中tmp[i]表示小于等于i的数字数量{tmp[j] += tmp[j - 1];}for (int j = n - 1; j >= 0; j--){int digit2 = GetDigit(a[j],i);bucket[digit2][tmp[digit2]--] = a[j];}int k = 0;for (int d = 0; d < 10; d++){for (int j = 0; j < 20; j++){if(bucket[d][j]!=0)a[k++] = bucket[d][j];}}}
}
时间复杂度与空间复杂度
1. 时间复杂度

要进行 i(最高位的位数) 趟排序 , 每趟排序需要将元素分派到k个桶,所以每趟排序的时间复杂度为O(n+k) 走i趟时间复杂度就为O(i(n+k))  但桶的个数通常是固定的,执行的躺数一般又较小,所以基数排序的时间复杂度趋近于O(n)

2. 空间复杂度

由于开辟了两个数组辅助,假设两个数组长度分别为N,M,所以基数排序的空间复杂度大概为O(N+M)

基数排序的特点

基数排序是一种稳定的排序算法。在排序过程中,相同元素的相对顺序保持不变。这是因为基数排序是按照数字的每一位进行排序的,而相同元素的每一位都是相同的,所以它们的相对顺序不会发生变化。

基数排序是一种非比较型排序算法,它不通过比较元素的大小来进行排序,而是通过分配和收集的方式实现排序。这使得基数排序在某些情况下比基于比较的排序算法(如快速排序、归并排序等)更加高效

基数排序特别适用于对整数进行排序,尤其是当待排序的整数范围不大,且整数位数相差不大时。在这种情况下,基数排序的效率很高,因为只需要进行有限次的分配和收集操作。

基数排序需要额外的空间来存储桶(或子数组),以便进行元素的分配和收集。如果待排序的元素数量很大,这可能会占用较多的内存空间。因此,在使用基数排序时,需要考虑内存使用情况。

基数排序的时间复杂度可以近似认为是线性的。这使得基数排序在处理大数据集时具有较高的效率。

基数排序不仅适用于数组排序,还适用于链表排序。因为链表在分配和收集元素时不需要移动元素本身,只需要改变节点的指针指向即可。这使得基数排序在链表排序中具有更高的效率


这篇就到这里啦,感谢支持

(๑′ᴗ‵๑)I Lᵒᵛᵉᵧₒᵤ❤

http://www.lryc.cn/news/403111.html

相关文章:

  • unity渲染人物模型透明度问题
  • CH03_布局
  • 【Oracle】Oracle中的merge into
  • 【论文阅读笔记】In Search of an Understandable Consensus Algorithm (Extended Version)
  • CentOS 7 网络配置
  • 2024 React 和 Vue 的生态工具
  • AI学习指南机器学习篇-t-SNE模型应用与Python实践
  • 小试牛刀-Telebot区块链游戏机器人
  • 使用github actions构建多平台electron应用
  • java通过pdf-box插件完成对pdf文件中图片/文字的替换
  • 鸿蒙 next 5.0 版本页面跳转传参 接受参数 ,,接受的时候 要先定义接受参数的类型, 代码可以直接CV使用 [教程]
  • 【electron6】浏览器实时播放PCM数据
  • 嵌入式C/C++、FreeRTOS、STM32F407VGT6和TCP:智能家居安防系统的全流程介绍(代码示例)
  • 【Django】django自带后台管理系统样式错乱,uwsgi启动css格式消失的问题
  • 解决npm install(‘proxy‘ config is set properly. See: ‘npm help config‘)失败问题
  • 汽车及零部件研发项目管理系统:一汽东机工选择奥博思 PowerProject 提升研发项目管理效率
  • Keil开发IDE
  • 数据结构与算法05堆|建堆|Top-k问题
  • 【精简版】jQuery 中的 Ajax 详解
  • win10删除鼠标右键选项
  • 分层评估的艺术:sklearn中的策略与实践
  • 排序系列 之 快速排序
  • 【银河麒麟服务器操作系统】java进程oom现象分析及处理建议
  • Redis的AOF持久化策略(AOF的工作流程、AOF的重写流程,操作演示、注意事项等)
  • 共享模型之无锁
  • 下载安装VSCode并添加插件作为仓颉编程入门编辑器
  • 解决:Linux上SVN 1.12版本以上无法直接存储明文密码
  • Mongodb多键索引中索引边界的混合
  • 如何利用windows本机调用Linux服务器,以及如何调用jupyter界面远程操控
  • 如何定位Milvus性能瓶颈并优化