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