专栏首页编程理解排序算法(九):桶排序

排序算法(九):桶排序

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中元素进行排序,则所有桶中元素构成的集合是已排序的。

快速排序是将集合拆分为两个值域,这里称为两个桶,再分别对两个桶进行排序,最终完成排序。桶排序则是将集合拆分为多个桶,对每个桶进行排序,则完成排序过程。两者不同之处在于,快排是在集合本身上进行排序,属于原地排序方式,且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间,在额外空间上对桶进行排序,避免了构成桶过程的元素比较和交换操作,同时可以自主选择恰当的排序算法对桶进行排序。

当然桶排序更是对计数排序的改进,计数排序申请的额外空间跨度从最小元素值到最大元素值,若待排序集合中元素不是依次递增的,则必然有空间浪费情况。桶排序则是弱化了这种浪费情况,将最小值到最大值之间的每一个位置申请空间,更新为最小值到最大值之间每一个固定区域申请空间,尽量减少了元素值大小不连续情况下的空间浪费情况。

桶排序过程中存在两个关键环节:
  • 元素值域的划分,也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择,若规则设计的过于模糊、宽泛,则可能导致待排序集合中所有元素全部映射到一个桶上,则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛,则可能导致待排序集合中每一个元素值映射到一个桶上,则桶排序向计数排序方式演化。
  • 排序算法的选择,从待排序集合中元素映射到各个桶上的过程,并不存在元素的比较和交换操作,在对各个桶中元素进行排序时,可以自主选择合适的排序算法,桶排序算法的复杂度和稳定性,都根据选择的排序算法不同而不同。

算法过程

  1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数;
  2. 遍历待排序集合,将每一个元素移动到对应的桶中;
  3. 对每一个桶中元素进行排序,并移动到已排序集合中。

步骤 3 中提到的已排序集合,和步骤 1、2 中的待排序集合是同一个集合。与计数排序不同,桶排序的步骤 2 完成之后,所有元素都处于桶中,并且对桶中元素排序后,移动元素过程中不再依赖原始集合,所以可以将桶中元素移动回原始集合即可。

演示示例

待排序集合为:[-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70] 映射规则为:

,其中常量位:

,即以间隔大小 10 来区分不同值域 排序算法为:堆排序,根据堆排序特性可知,

个元素的集合,时间复杂度为:

,算法不保持稳定性

step 1:

遍历集合可得,最大值为:

,最小值为:

,待申请桶的个数为:

step 2:

遍历待排序集合,依次添加各元素到对应的桶中。

桶下标

桶中元素

0

-7, -3, -10

1

3, 4

2

16

3

21, 25, 22

4

32

5

43

6

51, 56, 56

7

68

8

77, 70

9

87

10

99

11

12

13

121

step 3:

对每一个桶中元素进行排序,并移动回原始集合中,即完成排序过程。

算法示例

def bucketSort(arr):
    maximum, minimum = max(arr), min(arr)
    bucketArr = [[] for i in range(maximum // 10 - minimum // 10 + 1)]  # set the map rule and apply for space
    for i in arr:  # map every element in array to the corresponding bucket
        index = i // 10 - minimum // 10
        bucketArr[index].append(i)
    arr.clear()
    for i in bucketArr:
        heapSort(i)   # sort the elements in every bucket
        arr.extend(i)  # move the sorted elements in bucket to array

第一个循环作用为将待排序集合中元素移动到对应的桶中,复杂度为

;第二个循环的作用为对每个桶中元素进行排序,并移动回初始集合中,若桶个数为

,平均每个桶中元素个数为

,则复杂度为

。当

时,即桶排序向计数排序方式演化,则堆排序不发挥作用,复杂度为

,只需要将元素移动回初始集合即可。当

时,即桶排序向比较性质排序算法演化,对集合进行堆排序,并将元素移动回初始集合,复杂度为

算法分析

由算法过程可知,桶排序的时间复杂度为

,其中

表示桶的个数。由于需要申请额外的空间来保存元素,并申请额外的数组来存储每个桶,所以空间复杂度为

。算法的稳定性取决于对桶中元素排序时选择的排序算法。由桶排序的过程可知,当待排序集合中存在元素值相差较大时,对映射规则的选择是一个挑战,可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象,对算法的时间复杂度或空间复杂度有较大影响,所以同计数排序一样,桶排序适用于元素值分布较为集中的序列。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法(三):插入排序

    插入排序算法维护一个已排序集合和一个待排序集合,每轮迭代,从待排序集合中选择一个元素,插入到已排序集合中的适当位置,通过多次迭代,最终完成排序。

    zhipingChen
  • 排序算法(二):选择排序

    选择排序算法维护一个待排序集合和一个已排序集合,每轮迭代,从待排序集合中选择一个最小(最大)元素,添加到已排序集合中,通过多次迭代,最终完成排序。

    zhipingChen
  • 排序算法(一):冒泡排序

    冒泡排序是一种通过交换元素位置实现的稳定排序方式,其特点是每一轮排序后,都会在首端或尾端产生一个已排序元素,就像水泡不断上浮一样,通过多次排序,最终所有元素变得...

    zhipingChen
  • 不稳定的原地排序算法:选择排序

    在之前的文章中,我们说了两个原地排序算法:插入排序和冒泡排序。分析两个算法的原理,也用代码实现了两个算法。最后,我们也从两个算法入手,引出了评价算法性能的两个重...

    飞翔的竹蜻蜓
  • 经典排序算法详细介绍

    渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    IT茂茂
  • 8大排序算法图文讲解

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    昱良
  • 多条件排序

    今天跟大家分享多条件排序的技巧! 之前分享过关于excel中的排序菜单及所有的排序函数,但是这些菜单和函数的排序功能仅限于单列排序,无法完成多列的多条件排序功...

    数据小磨坊
  • 【学习】视觉直观感受 7 种常用排序算法

    10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

    小莹莹
  • 写代码?程序猿?你不能不懂的八大排序算法的Python实现

    信息获取后通常需要进行处理,处理后的信息其目的是便于人们的应用。信息处理方法有多种,通常由数据的排序,查找,插入,删除等操作。本章介绍几种简单的数据排序算法和高...

    风骨散人Chiam
  • 两分钟真能搞懂桶排序

    在数据结构与算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,算法的排序中,我...

    bigsai

扫码关注云+社区

领取腾讯云代金券