Python排序算法8：计数排序（1）

qiuyouzhi

Python排序算法8：计数排序（1）

计数排序的原理

计数排序，是一种不需要比较的算法（还有桶排序，这个后面讲)。

这种排序方法使用下标排序(和访问列表的方式差不多)。

举个例子可能会更清晰一点：

假设有20个随机整数，范围在0~10，要求用最快的速度
将他们排序。
考虑到这些整数只能在0~10这11个数内取值，范围有限，
所以可以建立一个长度为11的列表，用于存放数据。

1. [0 0 0 0 0 0 0 0 0 0 0 ]

复制代码

         

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

复制代码

假设20个随机整数是酱紫的：

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

然后下面就开始遍历这个数列：

第一个值，它的值是9，那么就给元素下标为9的元素加1

差不多是这样的：

1. [0 0 0 0 0 0 0 0 0 1 0 ]

复制代码

         

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

复制代码

然后以此类推（原谅我太懒），最后就是这个样子：

1. [1 2 1 3 2 2 1 2 1 4 1]

复制代码

         

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

复制代码

然后直接遍历数组，输出数组元素的下标值，元素的

值是几，就输出几遍。

zltzlt

又学到了新的排序方法

1. from random import randint
   
2. l1 = [0] * 11
   
3. sorted_l = []
   
4. lforsort = [randint(0, 10) for _ in range(20)]
   
5. 
   
6. for i in lforsort:
   
7.     l1[i] += 1
   
8. 
   
9. for i in range(len(l1)):
   
10.     sorted_l.extend([i] * l1[i])
    
11. 
    
12. print(sorted_l)

复制代码

qiuyouzhi

zltzlt 发表于 2020-3-8 09:30
又学到了新的排序方法

qiuyouzhi

zltzlt 发表于 2020-3-8 09:30
又学到了新的排序方法

话说回来，你这代码写的是真辣眼睛，l和1分不清楚
还是这样好：

1. def countSort(arr):
   
2.     unsortedl = [0 for i in range(len(arr))]
   
3.     result = []
   
4. 
   
5.     for i in arr:
   
6.         unsortedl[i] += 1
   
7. 
   
8.     for i in range(len(arr)):
   
9.         result.extend([i] * unsortedl[i])
   
10.         
    
11.     return result

复制代码