python - 计数排序实现只工作了一半

Question

我尝试根据麻省理工学院的“算法简介”在 Python 中实现一个 CountingSort 程序，但它只在前几个元素之后才有效，我不知道为什么。

A = [2, 11, 3, 6, 9, 20, 11, 32, 45, 47, 52, 59]
B = []
for x in range(len(A)):
    B.append(0)

    
C = []
k = max(A)

for i in range(0,k+1):
    C.append(0)


for j in range(0, len(A)):
    C[A[j]] += 1
    

for i in range(1,k):
    C[i] = C[i] + C[i-1]

#print(C)
    
for j in range(len(A)):
    B[C[A[j]]] = A[j]
    C[A[j]] -= 1
    
print(B)

打印列表：[0, 59, 3, 6, 9, 11, 11, 20, 32, 45, 47, 52]

标签： pythonsortingcounting

Answer 1

此代码有效，您需要继续检查您正在创建和分配的索引

A = [2, 11, 3, 6, 9, 20, 11, 32, 45, 47, 52, 59, 65,2]
B = []
for x in range(len(A)):
    B.append(0)

    
C = []
k = max(A)

for i in range(0,k+1):
    C.append(0)


for j in range(0, len(A)):
    C[A[j]] += 1
    
 
for i in range(1,k+1):
    C[i] = C[i] + C[i-1]

#print(C)

for j in range(len(A)):
    B[C[A[j]]-1] = A[j]
    C[A[j]] -= 1
    
print(B)