程序员必备排序算法（2）
一、写在前面
排序算法算是比较简单面试过程中遇到最多的算法，一般我们所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是非线性时间比较类排序，通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。主要有：计数排序，基数排序，桶排序等。
上次介绍的是比较类型排序程序员必备排序算法（1）今天给大家介绍非比较类型排序。
二、算法详解
1、桶排序（Bucket Sort）
桶排序也叫箱排序。工作的原理是将数组元素映射到有限数量个桶里，利用计数排序可以定位桶的边界，每个桶再各自进行桶内排序（使用其它排序算法或以递归方式继续使用桶排序）
1.1 算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
1.2 图片演示 下图给出了对{ 29, 25, 3, 49, 9, 37, 21, 43 }进行桶排序的简单演示过程
1.3 代码实现
1def bucketSort(nums):
2 # 选择一个最大的数
3 max_num = max(nums)
4 # 创建一个元素全是0的列表, 当做桶
5 bucket = [0]*(max_num+1)
6 # 把所有元素放入桶中, 即把对应元素个数加一
7 for i in nums:
8 bucket[i] += 1
9
10 # 存储排序好的元素
11 sort_nums = []
12 # 取出桶中的元素
13 for j in range(len(bucket)):
14 if bucket[j] != 0:
15 for y in range(bucket[j]):
16 sort_nums.append(j)
17
18 return sort_nums
19
20nums = [29, 25, 3, 49, 9, 37, 21, 43 ]
21print bucketSort(nums)2、计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。通俗地理解，例如有10个年龄不同的人，假如统计出有8个人的年龄不比小明大（即小于等于小明的年龄，这里也包括了小明），那么小明的年龄就排在第8位，通过这种思想可以确定每个人的位置，也就排好了序。当然，年龄一样时需要特殊处理（保证稳定性）：通过反向填充目标数组，填充完毕后将对应的数字统计递减，可以确保计数排序的稳定性。 2.1 算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
2.2 动图演示
2.3 代码实现
1def sort(l):
2 n = len(l)
3 res = [None] * n
4 # 首次循环遍历, 每个列表的数都统计
5 for i in range(n):
6 # p 表示 a[i] 大于列表其他数 的次数
7 p = 0
8 # q 表示 等于 a[i] 的次数
9 q = 0
10 # 二次循环遍历, 列表中的每个数都和首次循环的数比较
11 for j in range(n):
12 if l[i] > l[j]:
13 p += 1
14 elif l[i] == l[j]:
15 q += 1
16 for k in range(p, p+q): # q表示相等的次数,就表示, 从 P开始索引后, 连续 q次,都是同样的数
17
18 res[k] = l[i]
19 return res
20
21
22 print(sort([5, 2, 3，4，1])) 3、基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
3.1 算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
3.2 动图演示
3.3 代码实现
1def radix_sort(array):
2
3 bucket, digit = [[]],0
4
5 while len(bucket[0]) != len(array):
6
7 bucket = [[], [], [], [], [], [], [], [], [], []]
8
9 for i in range(len(array)):
10
11 num = (array[i] // 10 ** digit) % 10
12
13 bucket[num].append(array[i])
14
15 array.clear()
16
17 for i in range(len(bucket)):
18
19 array += bucket[i]
20
21 digit += 1
22
23 return array
24
25hlist = radix_sort([4,5,6,7,3,2,6,9,8])
26
27print(hlist)