计数排序vs基数排序vs桶排序

栏目: 编程工具 · 发布时间: 5年前

内容简介:计数排序是一种非基于元素比较的排序算法,而是将待排序数组元素转化为计数数组的索引值,从而间接使待排序数组具有顺序性。计数排序的实现一般有两种形式:基于辅助数组和基于桶排序。整个过程包含三个数组:待排序数组A、计数数组B和输出数组C。

计数排序是一种非基于元素比较的 排序 算法,而是将待排序数组元素转化为计数数组的索引值,从而间接使待排序数组具有顺序性。

计数排序的实现一般有两种形式:基于辅助数组和基于桶排序。

基于辅助数组

整个过程包含三个数组:待排序数组A、计数数组B和输出数组C。

简单来说,就是通过统计待排序数组A中元素不同值的分布直方图,生成计数数组B,然后计算计数数组B的前缀和(此步操作可以看成计算待排序数组A中每个元素的位置信息),最后通过逆序循环将元素对应赋值到输出数组C中,输出数组C即是最终排序结果。

计数排序vs基数排序vs桶排序
计数排序vs基数排序vs桶排序

基于桶排序

其实就是用桶排序来维护稳定性,因为在每个桶中的元素是以队列结构排序的,可以维护元素的顺序。

主要步骤:

  1. 按元素的最大健值与最小健值之差来创建指定数量的桶,并在每个桶中创建一个队列。
  2. 按顺序遍历待排序数组,将它们放到对应桶的队列中。
  3. 按桶编号顺序进行遍历,将每个桶中队列按顺序输出回原数组中。
计数排序vs基数排序vs桶排序
计数排序vs基数排序vs桶排序
计数排序vs基数排序vs桶排序

计数排序的不足

可以看到辅助数组的长度和桶的数量由最大值和最小值决定,假如两者之差很大,而待排序数组又很小,那么就会导致辅助数组或桶大量浪费。

基数排序

基数排序改善了计数排序,简单来说,基数 排序算法 就是将整数或字符串切分成不同的数字或字符,然后按对应位置的数或字符分别进行比较,这样就能将辅助数组或桶的数量降低到一个较小的值,经过多轮排序后得到最终的排序结果。

比如下面对于十进制的数值比较,只需要10个桶即可,但要保证每个桶能放得进所有元素。

计数排序vs基数排序vs桶排序

第一阶段:针对个位数将元素放到对应的桶中。

计数排序vs基数排序vs桶排序

第二阶段:针对十位数将元素放到对应的桶中。

计数排序vs基数排序vs桶排序

第三阶段:针对百位数将元素放到对应的桶中。

计数排序vs基数排序vs桶排序

最终按照桶顺序输出得到排序结果。

计数排序vs基数排序vs桶排序

桶排序

桶排序是改善计数排序的方法之一,其基本思想是将待排序数组分配到若干个桶内,然后每个桶内再各自进行排序,桶内的排序可以使用不同的算法,比如插入排序或快速排序,属于分治法。每个桶执行完排序后,最后依次将每个桶内的有序序列拿出来,即得到完整的排序结果。

待排序数组的最大元素与最小元素分别为19和1,那么总的范围区间可定义为[0,19],假设用4个桶,则桶的区间分别为 [0,4][5,9][10,14][15,19] 。可以看到桶的数量可以控制在很小的范围内,而且桶的容量大小可以动态扩充。

计数排序vs基数排序vs桶排序

按照值将元素放到对应桶内。

计数排序vs基数排序vs桶排序

按照桶顺序将元素依次输出得到排序结果。

计数排序vs基数排序vs桶排序

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

高效团队开发

高效团队开发

[日] 池田尚史、[日] 藤仓和明、[日] 井上史彰 / 严圣逸 / 人民邮电出版社 / 2015-7 / 49.00

本书以团队开发中所必需的工具的导入方法和使用方法为核心,对团队开发的整体结构进行概括性的说明。内容涉及团队开发中发生的问题、版本管理系统、缺陷管理系统、持续集成、持续交付以及回归测试,并且对“为什么用那个工具”“为什么要这样使用”等开发现场常有的问题进行举例说明。 本书适合初次接手开发团队的项目经理,计划开始新项目的项目经理、Scrum Master,以及现有项目中返工、延期问题频发的开发人......一起来看看 《高效团队开发》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具