1 Introduction

分配排序基本思想: 排序过程无须比较关键字, 通过用额外的空间来分配和收集来实现排序, 这是一种以空间换时间的排序算法, 一般时间复杂度都是 O(n).

所以, 一般分配排序都是用于小规模或者分类数量极少, 重合度非常之高的数据排序中, 在对
时间性能要求非常之高, 对空间要求低的应用场景中.

分配排序就是类似分布式的思维, 对数据的分配, 分布, 进行一种归纳整合, 最终在进行下一步
的操作, 具体见.

分类:

  • 桶排序: 将数组分到有限数量的桶子里,然后对每个桶子再分别排序
  • 基数排序: 将整数按位数切割成不同的数字, 然后按每个位数分别比较
  • 索引排序: 根据索引来表示数据的交换, 并非一定在分配排序中使用.

2 桶排序

2.1 Analysis

本质上,这是一种非比较类-线性时间-分配类-排序, 桶本身就已经是具备顺序的一个个集合, 物以类聚、人以群分,社会分层始终存在,左与右的选择.

缺点:浪费空间,桶的数量

关键字:分配到各个桶、收集各个桶的信息

过程:

  • 设置一个定量的数组当作空桶子, 当然必须有一套提前预定的规则, 这样才能知道桶数量
  • 遍历数组, 将元素按照规则放入桶中, 数据的分配和整合
  • 对每一个非空的桶进行其他排序
  • 合并非空桶

动画演示

2.3 性能分析

时间复杂度: O(n + k)

空间复杂度: 最坏-O(n^2), O(n*k)

2.3 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bucketSort(list1, bucket_num):
"""bucketSort:按照十位数进行桶排序,仅仅打印,不进行真正的结果返回

:param list1:source list1
:param bucket_num:bucket numbers
"""
print '原始桶:'
for value in list1:
print value,
print

print '排序后的桶:'
for i in xrange(10):
for value in list1:
if (value / 10) % 10 == i:
print value,
print

3 基数排序

3.1 Analysis

本质上,一种非比较类-线性时间-分配类-排序. 将整数按位数切割成不同的数字,然后按每个位数分别比较.

术语:

  • 分量-d:所需进行桶排序的数量,每一次的基数都不一样的
  • 单关键字:例如十进制整数,d的值为最长位数,每次的基数都是10
  • 多关键字:例如扑克牌花色,d的值为花色取值、点数,每次的基数不一样

算法过程:

  • NB公司求职?好几个备胎人选?还有好几关面试?
  • 保证每一次的桶排序,大哥我都在优先队列
  • 此轮排序的基数都是在前一轮排序的基础上的,技术第一嘛,OK

排序方式:

  • LSD:低位优先排序
  • MSD:高位优先排序

动画演示

3.2 性能分析

时间复杂度: O(n), O(kn)

空间复杂度: O(n + k)

但是使用范围小

3.3 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def radixSort(list1, radix):
"""radixSort

:param list1: 带排序数组
:param radix: 基数, 需要提前设置
"""
# 用K位数可表示任意整数
# 1 首先根据radix基数(10进制, 15进制)来获取lnN的值: math.log(Max, radix)
# 2 之后获取向上取整值: math.ceil(value)
# 3 最后才得到桶的数量
k = int(math.ceil(math.log(max(list1) + 1, radix)))
for i in range(1, k + 1):
# 设置某一位基数位时的桶
bucket = [[] for j in range(radix)]
for val in list1:
bucket[val % (radix**i) // (radix**(i - 1))].append(val)
del list1[:]

# 桶合并
for each in bucket:
list1.extend(each)
return list1

4 索引指针排序

4.1 Analysis

元素的数量或者数据量巨大等原因, 不希望频繁的移动要排序的元素, 故而维持一个索引指针
数组来表示数据的迁移, 排序的过程就是下标移动的过程.该排序思维并非一种排序思想,
仅仅是一种排序的解决手段, 它可以再所有排序算法中使用.

好处:

  • 避免扰乱要排序的数据
  • 避免移动整个记录