Python线性时间排序——桶排序、基数排序与计数排序

1. 桶排序

1.1 范围为1-M的桶排序

如果有一个数组A，包含N个整数，值从1到M，我们可以得到一种非常快速的排序，桶排序（bucket sort）。留置一个数组S，里面含有M个桶，初始化为0。然后遍历数组A，读入A_i时，S[A_i]增一。所有输入被读进后，扫描数组S得出排好序的表。该算法时间花费O(M+N)，空间上不能原地排序。

初始化序列S

遍历A修改序列S的项

举个例子，排序一个数组[5,3,6,1,2,7,5,10]

值都在1-10之间，建立10个桶：

[0 0 0 0 0 0 0 0 0 0]    桶

[1 2 3 4 5 6 7 8 9 10]   桶代表的值

遍历数组，第一个数字5，第五个桶加1

[0 0 0 0 1 0 0 0 0 0]

第二个数字3，第三个桶加1

[0 0 1 0 1 0 0 0 0 0]

遍历后

[1 1 1 0 2 1 1 0 0 1]

输出

[1 2 3 5 5 6 7 10]

代码

1.2 区间[0,1)均匀分布的桶排序

当输入符合均匀分布时，例如，元素均匀的分布在区间[0,1)上，可以将桶排序与其它排序方法结合使用。

如果序列的大小为n，就将[0,1)划分成n个相同大小的子区间(桶),然后将n个输入数分布到各个桶中。先对各个桶中的数进行排序，然后按照次序把各桶中的元素列出来即可。

《算法导论》的描述图：

代码：

2. 基数排序

基数排序一般用于长度相同的元素组成的数组。首先按照最低有效数字进行排序，然后由低位向高位进行。

329                720                720                329

457                355                329                355

657                436                436                436

839＝＝＝＝≯ 457＝＝＝＝≯ 839＝＝＝＝≯ 457

436                657                355                657

720                329                457                720

355                839                657                839

基数排序可以看做是进行多趟桶排序。每个有效数字都在0-9之间，很适合桶排序，建10个桶很方便。

排序数组 64,8,216，512,27,729,0,1,343,125

第一趟排序：

0     1    512   343   64   125   216   27    8   729

0     1      2      3      4      5      6      7     8     9

第二趟排序：

8            729

1    216   27

0    512   125         343           64

0     1      2      3      4      5      6      7     8     9

第三趟排序：

64

27

8

1

0    125   216  343         512          729

0     1      2      3      4      5      6      7     8     9

输出：1  8  27  64  125  216  343  512  729

代码：

　1.3 计数排序

假设n个输入元素中每一个都是介于0到k之间的整数，此处k为某个整数。当k=O(n)时，计数排序的运行时间为Θ(n)。

对每一个数的元素x，确定出小于x的元素个数。有了这一信息就可以把x直接放到最终输出数组中的位置上。