网站建设项目经验,找人做网站需要先了解哪些要点,温州企业网站,wordpress 样式 code从计数排序说起 计数排序是一种非基于元素比较的排序算法#xff0c;而是将待排序数组元素转化为计数数组的索引值#xff0c;从而间接使待排序数组具有顺序性。 计数排序的实现一般有两种形式#xff1a;基于辅助数组和基于桶排序。 基于辅助数组 整个过程包含三个数组而是将待排序数组元素转化为计数数组的索引值从而间接使待排序数组具有顺序性。 计数排序的实现一般有两种形式基于辅助数组和基于桶排序。 基于辅助数组 整个过程包含三个数组待排序数组A、计数数组B和输出数组C。 简单来说就是通过统计待排序数组A中元素不同值的分布直方图生成计数数组B然后计算计数数组B的前缀和(此步操作可以看成计算待排序数组A中每个元素的位置信息)最后通过逆序循环将元素对应赋值到输出数组C中输出数组C即是最终排序结果。 基于桶排序 其实就是用桶排序来维护稳定性因为在每个桶中的元素是以队列结构排序的可以维护元素的顺序。 主要步骤 按元素的最大健值与最小健值之差来创建指定数量的桶并在每个桶中创建一个队列。按顺序遍历待排序数组将它们放到对应桶的队列中。按桶编号顺序进行遍历将每个桶中队列按顺序输出回原数组中。 计数排序的不足 可以看到辅助数组的长度和桶的数量由最大值和最小值决定假如两者之差很大而待排序数组又很小那么就会导致辅助数组或桶大量浪费。 基数排序 基数排序改善了计数排序简单来说基数排序算法就是将整数或字符串切分成不同的数字或字符然后按对应位置的数或字符分别进行比较这样就能将辅助数组或桶的数量降低到一个较小的值经过多轮排序后得到最终的排序结果。 比如下面对于十进制的数值比较只需要10个桶即可但要保证每个桶能放得进所有元素。 第一阶段针对个位数将元素放到对应的桶中。 第二阶段针对十位数将元素放到对应的桶中。 第三阶段针对百位数将元素放到对应的桶中。 最终按照桶顺序输出得到排序结果。 桶排序 桶排序是改善计数排序的方法之一其基本思想是将待排序数组分配到若干个桶内然后每个桶内再各自进行排序桶内的排序可以使用不同的算法比如插入排序或快速排序属于分治法。每个桶执行完排序后最后依次将每个桶内的有序序列拿出来即得到完整的排序结果。 待排序数组的最大元素与最小元素分别为19和1那么总的范围区间可定义为[0,19]假设用4个桶则桶的区间分别为[0,4][5,9][10,14][15,19]。可以看到桶的数量可以控制在很小的范围内而且桶的容量大小可以动态扩充。 按照值将元素放到对应桶内。 按照桶顺序将元素依次输出得到排序结果。 总结 基数排序和桶排序可以看成是计数排序的泛化版本使用了某些措施优化排序过程。在桶排序中当桶的个数取最大值(max-min1)的时候就变成了计数排序所以计数排序时桶排序的一种特例。基数排序可以看做是多轮桶排序基数排序以有效位的角度每个有效位都进行一轮桶排序。当用最大值作为基数时基数排序就退化成了计数排序。-------------推荐阅读------------ 我的开源项目汇总(机器深度学习、NLP、网络IO、AIML、mysql协议、chatbot) 为什么写《Tomcat内核设计剖析》 2018汇总数据结构算法篇 2018汇总机器学习篇 2018汇总Java深度篇 2018汇总自然语言处理篇 2018汇总深度学习篇 2018汇总JDK源码篇 2018汇总Java并发核心篇 2018汇总读书篇 跟我交流向我提问 欢迎关注
