常见的非比较类的排序算法（python详解）

常见的非比较类的排序算法

计数排序，桶排序，基数排序，典型的用空间换时间

1.计数排序

时间复杂度都为O(n+k)
稳定

主要思想：

借助额外的空间（索引与值的关系存储）记录各值出现的次数，适合元素范围（元素的取值范围K）较集中的排序

python实现：

def count_sort(arr):
	#申请额外空间数组
	min_value=min(arr)
	max_value=max(arr)
	k=max_value-min_value+1
	count=[0]*k
	#额外空间用来存放对应元素出现的次数
	#未排序序列中的元素-最小值=额外空间的数组下标
	for i in arr:
		count[i-min_value]+=1
	result=[]
	for i in range(0,len(count)):
		while count[i]>0:
			result.append(i+min_value)
			count[i]-=1
	return result
			

举例：未排序序列 [-1,3,1,2,4,2,3]
count 计数数组长度=4-（-1）+1=6，count=[1,0,1,2,2,0]
count下标 ： 0 1 2 3 4 5
count的值 ： 1 0 1 2 2 1（为原始输入序列出现的个数）
对应元素为：-1 0 1 2 3 4（-1出现1次，0没有出现，1出现一次，2出现2次，3出现2次，4出现1次）

2.桶排序

时间复杂度都为O(n+k)
稳定

主要思想：

桶排序根据映射规则将元素映射到k个桶，再将桶内元素排序，连接各桶元素(除空桶)

python实现：

def bucket_sort(arr):
	#设置桶的大小，这里默认为5
	max_value=max(arr)
	min_value=min(arr)
	buckets_size=(max_value-min_value)//5+1
	buckets=[[] for i in range(buckets_size)]
	#将序列中各元素填入各桶
	for i in arr:
		buckets[(i-min_value)//5].append(i)
	result=[]
	#将桶内元素排序，这里直接使用了sorted()
	for bucket in buckets:
		if bucket:
			result+=sorted(bucket)
	return result

3.基数排序

时间复杂度都为O(d*(n+r)),d为最大数的位数，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)
稳定

主要思想：桶排序的推广，考虑多个关键字，借助不同优先级别的关键字进行排序，适合非负整数排序，依次对个位，十位，百位…进行排序

python实现：

def radix_sort(arr):
	#最大值的位数
	max_bit=len(str(max(arr)))
	for b in range(max_bit):
		#按照0-9位数构建10个桶
		buckets=[[] for i in range(10)]
		#一趟分配
		for i in arr:
			#b=0根据个位放入对应的桶内，b=1根据十位放入对应桶内...
			buckets[i//(10**b)%10].append(i)
		#一趟收集
		#各桶按顺序取出，已经在对应位排好序的元素
		arr=[i for bucket in buckets for i in bucket]
	return arr

arr=[0,19,39,72,8,38,53,12,16,76,4,24,33]
按照个位数放入对应的桶内，按序取出就是个位数排好序的序列
[[0], [], [72, 12], [53, 33], [4, 24], [], [16, 76], [], [8, 38], [19, 39]] 
[0, 72, 12, 53, 33, 4, 24, 16, 76, 8, 38, 19, 39]
按照十位数放入对应的桶内，按序取出就是十位数排好序的序列
[[0, 4, 8], [12, 16, 19], [24], [33, 38, 39], [], [53], [], [72, 76], [], []] 
[0, 4, 8, 12, 16, 19, 24, 33, 38, 39, 53, 72, 76]