【算法】计数排序 + 各个排序算法的稳定性
2021/11/27 11:40:03
本文主要是介绍【算法】计数排序 + 各个排序算法的稳定性,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
之前介绍的排序算法:
- 【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-CSDN博客
- 【算法】选择排序——堆排序+直接选择排序_Rinne’s blog-CSDN博客
- 【算法】交换排序——快速排序+冒泡排序(更新了非递归冒泡以及优化)_Rinne’s blog-CSDN博客
- 【算法】归并排序_Rinne’s blog-CSDN博客
文章目录
- 计数排序
- 一、算法思路图解
- 1. 计数
- 2. 拷贝到原数组
- 二、代码
- 三、测试
- 四、各个排序算法的稳定性
- 1. 稳定性定义
- 2. 是否稳定
计数排序
计数排序是一个非基于比较的排序算法,该算法于1954年由
Harold H. Seward
提出它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法
当然这是一种牺牲空间换取时间的做法,而且当
O(k)>O(n*log(n))
的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n))
, 如归并排序,堆排序)
- 时间复杂度:
O(Max(N, Range))
- 空间复杂度:
O(range)
- 适合范围比较集中的整数数组
- 范围较大,或者是浮点数等等都
不适合
排序了
一、算法思路图解
1. 计数
基本思路:遍历数组a,a[i]
下标对应的count[a[i]]++
-
count数组大小
看样子范围应该是0到a数组中最大的数?
实则不是,如果数字是
1000, 1001, 1100
则从0到1100 ,浪费了很多空间
所以我们定义一个映射数组,所有的数字都是相对最小的数字的大小
1000, 1001, 1100
映射数组数字大小:a[i] - min
0, 1, 100
将它设置为count数组对应下标
2. 拷贝到原数组
这里主要是寻找数组下标与数组值之间的对应关系
-
count[i],拷贝的数字是i + min进入原数组(返回映射)
-
count[i] 的数值表示,数字i需要拷贝到原数组的次数
-
所以count数组初始值都为0
-
拷贝一次count[i]–
二、代码
//计数排序 void CountSort(int* a, int n) { int max = a[0]; int min = a[0]; int i = 0; //取出最大和最小值找范围 for (i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } //数组数字所在范围 int range = max - min + 1; //开辟内存空间,并且初始化为0 int* tmp = (int*)calloc(range, sizeof(int)); //malloc操作 //int* tmp = (int*)mallco(sizeof(int) * range); //memset(tmp, 0, sizeof(int) * range); if (!tmp) { printf("calloc fail\n"); exit(-1); } int* count = tmp; //计数 for (i = 0; i < n; i++) { count[a[i] - min]++; } int j = 0; //计数放回 for (i = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } free(tmp); tmp = NULL; }
三、测试
四、各个排序算法的稳定性
1. 稳定性定义
相同数值,在排序过后相对位置不发生改变
- 前一个和后一个相同的数,排序完成之后他们还是前一个还是在后一个数之前
2. 是否稳定
-
直接插入排序 稳定
因为是按顺序,从前往后,前1、2、3……个数依次插入排成有序
-
希尔排序 不稳定
因为是以x为长度,跨位置选数字组成一组开始插入排序
-
选择排序 不稳定
选择排序是按顺序比较前后,挑出最大和最小。将大的先放在后面,再下一次可以把相同大的放在上一次的之前,顺序改变。
但会有人说我可以通过控制代码,来选择第一次选到最大的那个是后面的那个数
还有一种情况
选择排序算法中还有一段是这样的,如果找到最大最小的两个数,最大的数在最小数需要放的位置,先交换最大和最小,改变序号
-
堆排序 不稳定
看图,向下调整之后位置改变
-
冒泡排序 稳定
前后两个数交换,可以控制代码使之相对位置不改变
-
快速排序 不稳定
假设最左为key,左边找大,右边找小
相对位置发生改变
-
归并排序 稳定
实质上细分来看是每个循环都是两个数组,相对顺序不变
按照从小到大的顺序归并到一个数组,所以稳定
-
计数排序 稳定
统计相同数值的个数,按顺序映射到原数组
这篇关于【算法】计数排序 + 各个排序算法的稳定性的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求