算法导论程序15-计数排序（Python）算法导论

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。

文章图片

计数排序的基本思想是：对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了，例如，如果有17个元素小于x，则x就应该
在第18个输出位置上，当有几个元素相同时，这一方案要略做修改。因为不能把它们放在同一个输出位置上。
假设输入是一个数组A[0...n-1]，A.length=n,我们还需要两个数组，B[0...n-1]存放排序的输出，C[0...k]提供临时存储空间。

def counting_sort(A,B,k): n=len(A) C=[] for i in range(0,k+1): C.append(0) for j in range(0,n): C[A[j]]=C[A[j]]+1 for i in range(1,k+1): C[i]=C[i]+C[i-1] for j in range(n-1,-1,-1): B[C[A[j]]-1]=A[j] C[A[j]]=C[A[j]]-1

运行结果： 【算法导论程序15-计数排序（Python）】

>>> A=[2,5,3,0,2,3,0,3] >>> B=[0,0,0,0,0,0,0,0] >>> k=5 >>> counting_sort(A,B,k) >>> A [2, 5, 3, 0, 2, 3, 0, 3] >>> B [0, 0, 2, 2, 3, 3, 3, 5]

第二个for循环后，C中存放的是等于i的元素的个数。第三个for循环后，C中存放的是小于或者等于i元素的总数。
第四个for循环，可以把每个元素A[j]放到它在输出数组B中的正确位置上。如果所有n个元素都是互异的，那么当第一次执行第四个for循环时，对每一个A[j]值来说，C[A[j]]-1就是A[j]在输出数组中的最终正确的位置。我们每将一个A[j]放入数组B中以后，都要将C[A[j]]的值减一。这样，当遇到下一个值等于A[j]的输入元素（如果存在）时，该元素可以直接被放到输出数组中A[j]的前一个位置上。