其他
程序员必备排序算法（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）
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)
往期推荐阅读：
▲长按关注此公众号