线性时间排序

基础算法复习:线性时间排序。

计数排序

基本思路

  计数排序核心是将输入的数据值转化为键存储在额外开辟的数组空间中,其基本思想一是:在排序之前,先统计遍历源数组,得到最大值 max 和最小值 min,然后开辟一个长度为 max-min+1 的计数数组,计数数组中 index 的元素记录的值是原数组中某元素出现的次数,遍历原数组进行计数,最后按顺序输出计数数组中不为0的元素,如果出现多次,则输出多次。

  例如要排序的数组为 [5, 3, 4, 7, 2, 4, 3, 4, 7],最大值为 7,最小值为 2,所以计数数组的长度为 6,然后按照下图的方式,记录每个数出现的次数,最后遍历计数数组进行输出。

6-1

  具体可参考 五分钟学算法 公众号的文章:【图解数据结构】 一组动画彻底理解计数排序

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def counting_sort(nums):
max_num = max(nums)
min_num = min(nums)
length = max_num - min_num + 1
src = [0 for _ in range(length)] # 计数数组
for i in nums: # 计数
tmp = i - min_num
src[tmp] += 1
res = []
for j in range(len(src)): # 输出
while src[j]:
src[j] -= 1
res.append(j + min_num)
return res

  计数排序是一种非常快捷的稳定排序方法,时间复杂度和空间复杂度均为 O(n+k),其中 n 为要排序的数的个数,k 为要排序的数组的最大值。

  计数排序的是消耗空间复杂度来优化时间复杂度的排序方法,对一定量的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

时间复杂度
  • 平均时间复杂度:O(n+k)。
  • 最优时间复杂度:O(n+k)。
  • 最坏时间复杂度:O(n+k)。
  • 空间复杂度:O(k)。
  • 稳定性:稳定。

桶排序

基本思路

  桶排序是一种基于计数的排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

  简单来说就是设置 n 个数组当作空桶子。遍历数组,并且把项目一个一个放到对应的桶子去。对每个不是空的桶子进行排序。从不是空的桶子里把项目再放回原来的数组中。

6-1

  具体可参考 五分钟学算法 公众号的文章:【图解数据结构】 一组动画彻底理解桶排序

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def bucket_sort(nums, n):
bucket = [[] for _ in range(n)]
max_num = max(nums)
min_num = min(nums)
gap = (max_num - min_num + 1) // 5 # 确定每个桶的范围
for i in nums: # 放进桶中
index = i // (gap + min_num)
bucket[index].append(i)
for i in range(n): # 桶内排序
bucket[i].sort()
index = 0
for i in range(n): # 输出
for j in range(len(bucket[i])):
nums[index] = bucket[i][j]
index += 1
return nums
时间复杂度
  • 平均时间复杂度:O(n+k)。
  • 最优时间复杂度:O(n+k)。
  • 最坏时间复杂度:O(n**2)。
  • 空间复杂度:O(n+k)。
  • 稳定性:稳定。

基数排序

基本思路

  基数排序是桶排序的扩展,它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。通过将要比较的位(个位、十位、百位…),将要排序的元素分配至 0~9 个桶中,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,得到的数组就是有序的。

6-1

  具体可参考 五分钟学算法 公众号的文章:【图解数据结构】 一组动画彻底理解基数排序

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def RadixSort(nums):
n = 1
max_num = max(nums)
while max_num > 10 ** n: # 得到最大数是几位数
n += 1
i = 0 # 从个位开始
while i < n:
bucket = [[] for _ in range(10)] # 初始化桶
for x in nums: # 对每一位进行排序
radix = int((x / (10 ** i)) % 10) # 得到每位的基数
bucket[radix].append(x) # 加入对应基数的桶中
j = 0
for k in range(10):
if len(bucket[k]) != 0: # 若桶不为空
for y in bucket[k]: # 将该桶中每个元素
nums[j] = y # 放回到数组中
j += 1
i += 1
return nums
时间复杂度
  • 平均时间复杂度:O(nxk)。
  • 最优时间复杂度:O(nxk)。
  • 最坏时间复杂度:O(nxk)。
  • 空间复杂度:O(n+k)。
  • 稳定性:稳定。
坚持原创技术分享,您的支持将鼓励我继续创作!