计数排序

计数排序是一个非基于比较的排序算法，优势在于在对一定范围内的整数排序时，快于基于比较的排序算法。

算法思想

计数排序的基本思想在于给定的输入序列中的每一个元素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)

局限性

• 当数列的最大和最小值差距过大时，并不适用计数排序
• 当数列元素不是整数，并不适用计数排序