计数排序
计数排序是一个非基于比较的排序算法，优势在于在对一定范围内的整数排序时，快于基于比较的排序算法。
算法思想
计数排序的基本思想在于给定的输入序列中的每一个元素x，确定该序列中值小于等于x元素的个数，然后将x直接存放到最终的排序序列的正确位置上。
Python代码
环境
Python3.7
代码
# --*-- coding: utf-8 --*--
def CountingSort(arr):
#检查入参类型
if not isinstance(arr,(list)):
raise TypeError('error para type')
#获取arr中的最大值和最小值
maxNum=max(arr)
minNum=min(arr)
#以最大值和最小值的差作为中间数组的长度,并构建中间数组，初始化为0
length=maxNum-minNum+1
tempArr=[0 for i in range(length)]
#创建结果List，存放排序完成的结果
resArr=list(range(len(arr)))
#第一次循环遍历
for num in arr:
tempArr[num-minNum]+=1
#第二次循环遍历
for j in range(1,length):
tempArr[j]=tempArr[j]+tempArr[j-1]
#第三次循环遍历
for i in range(len(arr)-1,-1,-1):
resArr[tempArr[arr[i]-minNum]-1]=arr[i]
tempArr[arr[i]-minNum]-=1
return resArr
if __name__=='__main__':
arr=[12,25,26,13,14,25,12,17,18,14]
print(CountingSort(arr))
代码注释
- 中间数组的作用是用来统计arr中每个元素的出现次数，中间数组的下标就是arr中元素的值，中间数组的值就是arr中该下标值出现的次数
- 之所以要获取arr的最大值和最小值，是因为需要排序的一定范围的整数不一定是从0开始，此时为避免空间位置浪费，中间数组的长度是是数列最大值和最小值的差+1，此时最小值作为一个偏移量存在
- 第一次遍历：用来遍历arr的每个元素，统计每个元素的出现次数，存入中间数组（下标是arr中的元素值，值是该元素在arr中的出现次数）
- 第二次遍历：遍历中间数组，每个位置的值=当前值+前一个位置的值，用来统计出小于等于当前下标的元素个数
- 第三次遍历：反向遍历arr的每个元素，找到该元素值在中间数组的对应下标，以这个中间数组的值作为结果数组的下标，将该元素存入结果数组
空间复杂度和时间复杂度
假定原始数列的规模是N，最大值和最小值的差是M,计数排序的时间复杂度是O(N+M)，如果不考虑结果数组，只考虑中间数组大小的话，空间复杂度是O(M)
局限性
- 当数列的最大和最小值差距过大时，并不适用计数排序
- 当数列元素不是整数，并不适用计数排序
