排序算法-计数排序

柔光的暖阳◎ 2024-05-02 20:26 81阅读 0赞

## 一、计数排序 ##

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

如果数组中有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

![5fd6dcb4e89a4ee88a299c10dfceb2a1.png][]

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

![8da64ecb01324f8e82143d679bf5c7f6.png][]

![644910fe29dd40a19b6a5a6f7f143080.png][]

根据这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标 值，元素的值是几，就输出几次: 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))

![81f96505325b4a6f9265d9b4099f36a2.png][]

> 以上是找数列的最大值来决定统计数组的长度，其实并不严谨 。
> 
> 如： 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

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

![051c1bac5cb54de1a92ee900dc53f3d5.png][]

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

![f6787631251e4e2fb885265aee61121e.png][]

**如图所示：**

![39b2607f2d444306b6587e89fa625d9d.png][]

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

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

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

![cdd1956bbf4f4e7daccf5ac4ec116ea4.png][]

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

![61e378c2fdc6450b807146d75cbce470.png][]

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

![a40c9a5369dd46ffbb827a50cb6e336b.png][]

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

'''优化'''
    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))

![446e99dd892a4ae1818487d62fbcabd4.png][]

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

> **1、当数列最大和最小值差距过大时，并不适合用计数排序。**
> 
> 如：给出20个随机整数，范围在0到1亿之间，这时如果使用计数排序，需要创建长度为1亿的数组。不但严重浪费空间，而且时间复杂度也会随之升高。
> 
> **2、当数列元素不是整数时，也不适合用计数排序。**
> 
> 如果数列中的元素都是小数，如25.213或0.000001这样的数字，则无法创建对应的统计数组。

[5fd6dcb4e89a4ee88a299c10dfceb2a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/b6ef4564fe974c6fad0128c7101f506f.png
[8da64ecb01324f8e82143d679bf5c7f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/47d9b563712a4e5da9a23220f034a1ff.png
[644910fe29dd40a19b6a5a6f7f143080.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/71273f3a1a4c4cc2a4b35ead3a9c3f6d.png
[81f96505325b4a6f9265d9b4099f36a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/4f44f52460434e4ab3eef15525a0e981.png
[051c1bac5cb54de1a92ee900dc53f3d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/7d1817d99b894f68ba382aa1cf9666a0.png
[f6787631251e4e2fb885265aee61121e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/f9331ac56d6f4025a64ac91b726e46c0.png
[39b2607f2d444306b6587e89fa625d9d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/4409e3e135174f7a92527b10f09c3bbb.png
[cdd1956bbf4f4e7daccf5ac4ec116ea4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/ca21ac50e90f4609bfbf0f33ead2bc7f.png
[61e378c2fdc6450b807146d75cbce470.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/4ac61c42121e45bd95e8a1ffa47cb4ec.png
[a40c9a5369dd46ffbb827a50cb6e336b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/fcdf373cc5654d3c8cf300437b11c757.png
[446e99dd892a4ae1818487d62fbcabd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/c845683611934db6aa77891f75bc153e.png