【算法】十大经典排序算法(三)

相关推荐:

写在前面:

非比较排序:计数排序、桶排序、基数排序

8、计数排序(Counting Sort)

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

8.1、算法描述

  1. 找出待排序的数组中最大和最小的元素;
  2. 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第 i 项;
  3. 对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加);
  4. 反向填充目标数组:将每个元素 i 放在新数组的第 C (i) 项,每放一个元素就将 C (i) 减去 1。

8.2、动图演示

【算法】十大经典排序算法(三)

8.3、代码实现

8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 k 之间的整数时,时间复杂度是 O (n+k),空间复杂度也是 O (n+k),其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。

9、桶排序(Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

9.1、算法描述

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。 

9.2、图片演示

【算法】十大经典排序算法(三)

9.3、代码实现

9.4、算法分析

桶排序最好情况下使用线性时间 O (n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为 O (n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

10、基数排序(Radix Sort)

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

10.1、算法描述

  1. 取得数组中的最大数,并取得位数;
  2. arr 为原始数组,从最低位开始取每个位组成 radix 数组;
  3. 对 radix 进行计数排序(利用计数排序适用于小范围数的特点);

10.2、动图演示

【算法】十大经典排序算法(三)

10.3、代码实现

10.4 算法分析

基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要 O (n) 的时间复杂度,而且分配之后得到新的关键字序列又需要 O (n) 的时间复杂度。假如待排数据可以分为 d 个关键字,则基数排序的时间复杂度将是 O (d*2n) ,当然 d 要远远小于 n,因此基本上还是线性级别的。基数排序的空间复杂度为 O (n+k),其中 k 为桶的数量。一般来说 n>>k,因此额外空间需要大概 n 个左右。

相关推荐:

参考:

喜欢(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

博主在线

博主在线

  • 扫描二维码,微信联系 扫描二维码,微信联系