第11讲. 计数排序，计数后前缀和===位次

前提：参与排序元素应该是已知范围内的整数，此处假设数组 a 的各元素的值在整数[0,max)范围的整数。 1. 计数排序

a = [20,15,18,15,18,15]
cnt = [0]* (max(a) + 1)

for e in a:
    cnt[e] += 1

# cnt[i]的含义： 有 cnt[i]个 i

k = 0
for i in range(0,max(a) + 1):
    while cnt[i]>0:
        a[k] = i ; k += 1; cnt[i] -= 1

print(a)

1. 计数后前缀和

a = [20,15,18,15,18,15]
n = len(a)
cnt = [0]* (max(a) + 1 )

for e in a:
    cnt[e] += 1

# cnt[i]的含义： 有 cnt[i]个 i 

for i in range(1,max(a) + 1):
    cnt[i] += cnt[i-1]

# cnt[i]的含义： 有 cnt[i]个 小于等于 i 的元素

b = [-1]*n
for e in a[::-1]:
    b[cnt[e]-1 ] = e
    cnt[e] -= 1

print(b)

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com