网站优化合同,WordPress右侧导航菜单主题,电子商务网站建设系统,毕节市住房和城乡建设局网站排序
参考#xff1a;https://www.bilibili.com/video/av38482633/?spm_id_fromtrigger_reload
目录
排序
插入排序
直接插入排序
折半排序
希尔排序
交换排序
冒泡排序
快速排序 选择排序
堆排序
流量单位计算
什么是计数排序
复杂度分析#xff1a;
什…排序
参考https://www.bilibili.com/video/av38482633/?spm_id_fromtrigger_reload
目录
排序
插入排序
直接插入排序
折半排序
希尔排序
交换排序
冒泡排序
快速排序 选择排序
堆排序
流量单位计算
什么是计数排序
复杂度分析
什么是基数排序
复杂度分析原始数列的规模是N,最大最小整数的差值是M 插入排序
有序插入在有序序列中插入一个元素保持序列有序有序长度增加 直接插入排序 ——零号位为哨兵i位要排序顺序查找j依次比较哨兵大则j往后移覆盖否则原地不动i赋值j1比较后单向移动不是交换 折半排序
循环比较midlowheight/ 2 与哨兵位置的大小如果哨兵小则到左半区查找heightmid-1否则右半区lowmid1直至low大于height确定插入位置然后将插入位置后面的所有对象都往后移动位置将哨兵插入height1 希尔排序
算法是一步一步来的两两对比相隔n个数据然后模仿直接插入排序完事儿后接着下一个数据接着同样的以上来插入排序最后一个间隔数值一定是1 交换排序 冒泡排序
基于简单的交换思想两两比较大的沉底前小后大需要一个临时空间暂存交换操作中的元素 如果发现一次排序后没有交换数据那咋说明前排的数据都是有序的了不需要再冒泡排序了 快速排序
改进的交换排序取中点放捎点low、hign指针比较捎点大小分为左右区域之后左右区域递归不稳定 选择排序
简单选择排序选择未排序里最小的并与第一个进行交换之后依次步骤一样 堆排序 无序的话就按数组顺序由根往下排并从第一个非叶子节点n/2 | 0开始堆调整直至符合堆的定义 流量单位计算
流量单位G,M,K,B,是什么意思 G, M, K, B, 都是数据或数据流量的单位符号。 其中B 是字节的符号字节 是数据或数据流量的基本单位。它们之间的换算关系是 什么是计数排序
先考一道算法题:
数组里有20个随机整数取值范圉从0到10要求用最快的速度把这20个整数从小到大进行排序。有没有比快速排序 0 nlogn更快的排序方法呢有的就是用计数排序。
让我们先来回顾一下咱们以前所学过的排序算法无论是冒泡排序还是快速排序等等都是基于元素之间的比较来进行排序。有一种特殊的排序算法叫做【计数排序】这种排序算法不是基于元素比较而是利用数组下标来确定元素的正确位置。
基于上题中整数的取值范围只是从0-10之间让我们根据这个整数取值范围建立一个长度为11的数组。数组下标从0到10元素初始值全为0。 假定20个随机整数的值如下
935491278136534010979
如何给这些无序的随机整数排序呢
非常简单让我们遍历这个无序的随机数列每一个整数按照其值对号入座对应数组下标的元素进行加1操作。
比如第一个整数是9那么数组下标为9的元素加1: 第二个整数是3那么数组下标为3的元素加1: 最终数列遍历完毕时数组的状态如下 数组每一个下标位置的值代表了数列中对应整数出现的次数
有了这个“统计结果”排序就很简单了。直接遍历数组输出数组元素的下标值
元素的值是几就输出几次
011233344556778999910
显然这个输出的数列已经是有序的了。
这就是计数排序的基本过程它适用于一定范围的整数排序。在取值范围不是很大的情况下它的性能甚至快过那些0(nlogn)的排序。
初步代码如下 这段代码在一开头补充了一 一个步骤,就是求得数列的最大整数值max。后面创建的统计数组countArray ,长度就是max1 ,以此保证数组的最后-一个下标是max。
只以数列的最大值来决定统计数组的长度其实并不严谨。而应该以最大值和最小值的差来作为数组的大小。不然会浪费空间。
我们不再以(输入数列的最大值1 )作为统计数组的长度,而是以(数列最大值和最小值的差1 )作为统计数组的长度。同时,数列的最小值作为-一个偏移量,用于统计数组的对号入座。 以这个数列为例,统计数组的长度为99-901 10 , 偏移量等于数列的最小值90。对于第一个整数95 ,对应的统计数组下标是95-90 5 ,如图所示: 此外朴素版的计数排序只是简单地按照统计数组的下标输出了元素值并没有真正给原始数列进行排序。
如果是单纯的给整数排序这样并没有问题。但如果放在现实业务里,比如给学生的考试分数排序遇到相同的分数就会分不清谁是谁。 给定一个学生的成绩表,要求按成绩从低到高排序,如果成绩相同,则遵循原表固有顺序。 那么,当我们填充统计数组以后,我们只知道有两个成绩并列95分的小伙伴,却不知道哪一个是小红哪一一个是小绿: 我们需要稍微改变之前的逻辑,在填充完统计数组以后对统计数组做一下变形。
统计数组从第二个元素开始每一个元素都加上前面所有元素之和。
这样相加的目的是让统计数组存储的元素值等于相应整数的最终排序位置。比如下标是9的元素值为5代表原始数列的整数9最终的排序是在第5位。
接下来我们创建输出数组sortedArray长度和输入数列一致。然后从后向前遍历输入数列
第一步我们遍历成绩表最后一行的小绿
小绿是95分我们找到countArray下标是5的元素值是4代表小绿的成绩排名位置在第4位。位置下标是3因为成绩最少的是第一位而他下标的位置对应就是0
同时我们给countArray下标是5的元素值减1从4变成3,代表着下次再遇到95分的成绩时最终排名是第3。 这样一来同样是95分的小红和小绿就能够清楚地排出顺序了也正因此优化版本的计数排序属于稳定排序。 复杂度分析
如果原始数列的规模是N,最大最小整数的差值是M,你说说计数排序的时间复杂度和空间复杂度是多少? 代码第1, 2, 4步都涉及到遍历原始数列运算量都是N,第3步遍历统计数列,运算量是M所以总体运算量是3NM,去掉系数时间复杂度是0 (NM)。 至于空间复杂度如果不考虑结果数组只考虑统计数组大小的话,空间复杂度是0 (M) 。 而计数排序存在它的局限性主要表现在两点:
1.当数列最大最小值差距过大时并不适用计数排序。
比如给定20个随机整数范围在0到1亿之间这时候如果使用计数排序需要创建长度1亿的数组。不但严重浪费空间而且时间复杂度也随之升高。
2.当数列元素不是整数并不适用计数排序。
如果数列中的元素都是小数比如25.213或是0.00000001这样子则无法创建对应的统计数组。这样显然无法进行计数排序。
对于这些局限性另一种线性时间排序算法做出了弥补这种排序算法叫做[桶排序]我们后续将会讲到。 参考 什么是计数排序 什么是基数排序
让我们接着来看两个特殊的需求
需求 A为一组给定的手机号排序
18914021920
13223132981
13566632981
13660891039
13361323035
........
........
按照计数排序的思路我们要根据手机号的取值范围创建一个空数组。
可是11 位手机号有多少种组合恐怕要建立一个大得不可想象的数组才能装下所有可能出现的 11 位手机号
需求 B为一组英文单词排序
banana
apple
orange
peach
cherry
........
........
计数排序适合的场景是对整数做排序如果遇到英文单词就无能为力了。
如何有效处理诸如手机号、英文单词等复杂元素的排序呢仅仅靠一次计数排序很难实现。
这时候我们不妨把排序工作拆分成多个阶段每一个阶段只根据一个字符进行计数排序一共排序 k 轮k 是元素长度。
或许这样的描述有些抽象我们来举一个例子。
数组中有若干个字符串元素每个字符串元素都是由三个英文字母组成
bdacfdqweyuiabcrrruee
如何将这些字符串按照字母顺序排序呢
由于每个字符串的长度是 3 个字符我们可以把排序工作拆分成 3 轮
第一轮按照最低位字符排序。排序过程使用计数排序把字母的 ascii 码对应到数组下标第一轮排序结果如下 第二轮在第一轮排序结果的基础上按照第二位字符排序。 需要注意的是这里使用的计数排序必须是稳定排序这样才能保证第一轮排出的先后顺序在第二轮还能继续保持。
比如在第一轮排序后元素 uue 在元素 yui 之前。那么第二轮排序时两者的第二位字符虽然同样是 u但先后顺序万万不能变否则第一轮排序就白做了。
第三轮在第二轮排序结果的基础上按照最高位字符排序。 如此一来这些字符串的顺序就排好了。
像这样把字符串元素按位拆分每一位进行一次计数排序的算法就是基数排序Radix Sort。
基数排序既可以从高位优先进行排序Most Significant Digit first简称MSD也可以从低位优先进行排序Least Significant Digit first简称LSD。
不过如果排序的字符串长度不规则呢?这个问题不难解决。我们以最长的字符串为准其他度不足的字符串在末尾补0即可。在排序时我们把字符 0 当做是比 a 更小的字符排序结果如下
ape000
apple0
banana
he0000
orange
代码如下 备注
ASCII ((American Standard Code for Information Interchange): 美国信息交换标准代码是基于拉丁字母的一套电脑编码系统主要用于显示现代英语和其他西欧语言。它是最通用的信息交换标准并等同于国际标准ISO/IEC 646。ASCII到目前为止共定义了128个字符 。
空字符的ASCII码如下 这段代码基于一个大循环来实现循环进行 k 次k 就是数组中最长字符串元素的字符数。
复杂度分析原始数列的规模是N,最大最小整数的差值是M
原本计数排序的时间复杂度是0 (nm),而基数排序总共执行了k次计数排序,所以时间复杂度是0 (k (nm))其中k是字符串的最大长度, m是字符范围。
至于空间复杂度由于基数排序的辅助数组是反复重用的所以基数排序的空间复杂度和计数排序-样,都是0(nm),其中m是字符的取值范围大小。
参考什么是基数排序
