桶排序

2020-07-26 约 627 字预计阅读 2 分钟次阅读

介绍

桶排序（Bucket sort），是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序并不是比较排序，他不受到 $O(n\log n)$ 下限的影响。

步骤

桶排序以下列程序进行：

1
2
3
4


1.设置一个定量的数组当作空桶子。
2.寻访序列，并且把项目一个一个放到对应的桶子去。
3.对每个不是空的桶子进行排序。
4.从不是空的桶子里把项目再放回原来的序列中。

说明

假设有些整数，范围在1-100之间。现在有n=10的序列要进行排序

1
2
3
4
5
6


Original array

+-------------------------------------------------+
|  6 | 28 | 96 | 14 | 74 | 37 |  9 | 71 | 91 | 36 |
+-------------------------------------------------+

Create：创建一定数量的空桶，这里我们建立与原始数组长度相等的空桶（10个）。每个空桶对应区间为0~9、10~19、20~29、30~39、40~49、50~59、60~69、70~79、80~89、90-99的区间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Bucket array
   
+-------------------------------------------------+
|    |    |    |    |    |    |    |    |    |    |
+-------------------------------------------------+
  ^    ^
  |    |
  |    |
  |    holds values in range 11 to 20
  holds values in range 1 to 10
   

Scout：将原始序列中的元素，放入到对应的桶里

1
2
3
4
5
6
7
8


Bucket array
   
  6,9  14   28   37,36               74,71     96,91
  |    |    |    |                   |         |
+-v----v----v----v-------------------v---------v--+
|    |    |    |    |    |    |    |    |    |    |
+-------------------------------------------------+
   

Sort：排序所有非空桶中的元素，桶内排序可以采用任意排序算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Bucket array
   
  sort sort sort sort                sort      sort
  ---  --   --   -----               -----     -----
  6,9  14   28   36,37               71,74     91,96
  |    |    |    |                   |         |
+-v----v----v----v-------------------v---------v--+
|    |    |    |    |    |    |    |    |    |    |
+-------------------------------------------------+
   

Gather：排序完成后，再把所有桶中元素依序放回原始序列

1
2
3
4
5


Original array
+-------------------------------------------------+
|  6 |  9 | 14 | 28 | 36 | 37 | 71 | 74 | 91 | 96 |
+-------------------------------------------------+
   

目录

桶排序