#!/usr/bin/python
# -*- coding: utf-8 -*-
def counting_sort(A, k):
B, C = [0] * len(A), [0] * (k + 1) # 包括0和k，长度k+1
for a in A:
C[a] += 1
for i in range(1, k + 1): # 1 to k
C[i] += C[i-1]
for j in reversed(range(len(A)-1)):
# 这里要注意索引从0开始的，所以要-1
B[C[A[j]]-1] = A[j]
C[A[j]] -= 1
return B
from collections import defaultdict
def counting_sort2(A, key=lambda x: x):
B, C = [], defaultdict(list)
for x in A:
C[key(x)].append(x)
for k in range(min(C), max(C)+1):
B.extend(C[k])
return B
from random import randrange
seq = [randrange(10000) for i in range(1000000)]
seq2 = seq[:]
import cProfile
cProfile.run('counting_sort(seq, 10000)')
cProfile.run('counting_sort2(seq2)')
