排序算法-计数排序

一、计数排序

       这种排序算法 是利用数组下标来确定元素的正确位置的。

      如果数组中有20个随机整数，取值范围为0~10，要求用最快的速度把这20个整数从小到大进行排序。 很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn）的排序。

    9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9，7，9

   考虑到这些整数只能够在0、1、2、3、4、5、6、7、8、9、10这11个数中取值，取值范围有限。可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0

    下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时对应数组下标的元素进行加1操作。

    根据这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标 值，元素的值是几，就输出几次: 0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10

    计数排序的基本过程，它适用于一定范围内的整数排序。在取值范围不是 很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn）的排序。

def countSort(ll):
    # 1.得到数列的最大值
    max=ll[0]
    for i in range(1,len(ll)):
        if ll[i]>max:
            max=ll[i]
    # print(max)
    # 2.根据数列最大值确定统计数组大小,并赋值0；
    arrs=[0]*(max+1)
    print(arrs)
    # 3.遍历数列,填充统计数组
    for i in range(len(arrs)):
        arrs[ll[i]]+=1
    print(arrs)
    # 4.遍历数列
    sorted_arrs=[]
    for i in range(len(arrs)):
        for j in range(0,arrs[i]):
            # print(i)
           sorted_arrs.append(i)
    #返回排序数组
    return sorted_arrs
 
if __name__ == '__main__':
    ll=[9,3,5,4,9,1,2,7,8,1,10]
    print(ll)
    print(countSort(ll))

 

以上是找数列的最大值来决定统计数组的长度，其实并不严谨 。

如： 96，93，91，94，95，90，99, 93，91，90

这个数列的最大值是99，但最小的整数是90。如果创建长度为100的数组，那么前面从0到89的空间位置就都浪费了!

    很简单，只要不再以输入数列的最大值+1作为统计数组的长度，而是以数列最大值-最小值+1作为统计数组的长度即可。 同时数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。 

统计出数组的长度：99-90+1=10，偏移量等于数列的最小值90对于第1个整数96，对应的统计数组下标是96-90=6

如下图所示: 同时数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。 

 如果学生成绩表，要求按成绩从低到高进行排序，如果成绩相同，则遵循原表固有顺序。

 如图所示：

这是变形，其实就是从统计数组的第2个元素开始，每一个元素都加上前面所有元素之和。 

步骤1：遍历成绩表最后一行的小绿同学的成绩。

小绿的成绩是95分，找到count_array下标是5的元素，值是4，代表小绿的成绩排名位置在第4位。 同时，给count_array下标是5的元素值减1，从4变成3，代表下次再遇到95分的成绩时，最终排名是第3。 

 

步骤2：遍历成绩表倒数第二行的小白同学的成绩。 

 

步骤3：遍历成绩表倒数第三行的小红同学的成绩。  

 

重复上面的步骤继续完成！ 

'''优化'''
def countSort2(ll):
    # 1.得到数列的最大值,最小值
    max=ll[0]
    min=ll[0]
    for i in range(1,len(ll)):
        if ll[i]>max:
            max=ll[i]
        if ll[i]<min:
            min=ll[i]
    #差值
    diff=max-min
    # print(diff)
    # 2.确定统计数组大小,并赋值0；
    arrs=[0]*(diff+1)
    # print(arrs)
    # 3.遍历数列,填充统计数组
    for i in range(len(ll)):
        arrs[ll[i]-min]+=1   #如：95-90=5,94-90=4
    print(arrs)
    # 4.统计数组变形，从第二个元素开始，后面的元素等于前面的元素之和
    for i in range(1,len(ll)):
        arrs[i]+=arrs[i-1]  #1+2,3+1,4+1...
    print(arrs)
    # 5.排序数列
    sorted_arrs=[0]*len(ll)
    # 倒序遍历原始数列，从统计数组找到正确位置
    for i in range(len(ll)-1,-1,-1):
        sorted_arrs[arrs[ll[i]-min]-1]=ll[i]  #92-90-1=1；1是排序数列下标，再将对应原始数据最后一个赋值到这个下标。
        arrs[ll[i] - min] -= 1    #arrs[92-90]-1=arrs[2]-1=1
        # #返回排序数组
    return sorted_arrs
 
if __name__ == '__main__':
    ll = [95,94,91,98,99,90,99,93,91,92]
    print(ll)
    print(countSort2(ll))

计数排序有它的局限性，主要表现两点：

1、当数列最大和最小值差距过大时，并不适合用计数排序。

    如：给出20个随机整数，范围在0到1亿之间，这时如果使用计数排序，需要创建长度为1亿的数组。不但严重浪费空间，而且时间复杂度也会随之升高。

2、当数列元素不是整数时，也不适合用计数排序。

  如果数列中的元素都是小数，如25.213或0.000001这样的数字，则无法创建对应的统计数组。