第10讲. 给序列排名次和位次

1. ★名次与位次的区别：

名次可以重复(有并列名次)，位次不能重复；名次习惯上从 1 开始。排位次注意稳定性问题。

2. 排名次或位次的方法

对序列 a 按从小到大的顺序排名次，记录在序列 cx 中。即 cx[i]是元素 a[i]的名次。

a = [20,15,19,15,18,15]
n = len(a)

方法 1：简单粗暴法。

对每一个元素假设名次为 1，扫描所有元素，扫描到一个要排在前面的则名次加 1。

# 排名次
mc = [1]*n # 所有元素的名次都初始化为 1
for i in range(n):
    for j in range(n):
        if a[j]<a[i]:
            mc[i] += 1 # 有更小的则 i 号名次加 1
注意：该方法只能用于排名次，不能用来排位次。

方法 2：方法 1 的改进——去掉重复比较。

要区分所有元素的大小，任意两个元素比较 1 次就够了，方法 1 任意两个元素比较了 2 次，且有自己和自己比较。记住模型：两个元素：i 在前，j 在后。

for i in range(n-1): # i 是所有可以放前面的元素
    for j in range(i+1, n): # j 是 i 后面的所有元素

排名次

mc = [1]*n # 所有元素的名次都初始化为 1
for i in range(n-1):
    for j in range(i+1, n):
        if a[i]>a[j]:
            mc[i] += 1 # 有更小的则 i 号名次加 1
        elif a[i]<a[j]:
            mc[j] += 1

print(mc)

排位次

wc = [0]*n # 所有元素的位次都初始化为 0
for i in range(n-1):
    for j in range(i+1, n):
        if a[i]>a[j]: wc[i] += 1 # 有更小的则 i 号名次加 1
        else: wc[j] += 1

print(wc)

方法 3：动态规划

有点像插入排序的思想。在计算 a[i]的位次时，a[1]～a[i-1]的位次是暂时正确的。现在把 a[i]加进来保证 a[1]～a[i]的位次暂时正确。不断的加入新的 a[i]直到所有的都加入为止。（类似就是排我前面少一个人，我的名次前进一位，排我名次后多一个人）

[0 …… i-1] i #对每一个元素 a[i]假设位次为其位值号 i，扫描其前面的所有元素，每找到一个需要排在其后面的元素 a[j]，则 i 的名次减 1，j 的名次加 1。

排名次

a = [20,15,19,15,18,15]
n = len(a)

mc = [i+1 for i in range(n)] # i 号元素的位次初始化为 i+1
for i in range(1, n):
    for j in range(i):
        if a[j]>a[i]: mc[j] += 1; mc[i] -= 1
        elif a[j]==a[i]: mc[i] -= 1

print(mc)

排位次

wc = [i for i in range(n)] # i 号元素的位次初始化为 i
for i in range(1,n):
    for j in range(i):
        if a[j]>a[i]: wc[j] += 1; wc[i] -= 1

print(wc)

3. 利用位次排序（抄写法）

a = [20,15,19,15,18,15]
n = len(a)
# 先求出 a 的位次 wc 代码略
b = [-1]*n
for i in range(n):
     b[wc[i]] = a[i] # a[i]的位次为 wc[i], 所以抄写到 b 的 wc[i]号。

4. 位次与索引的关系

序列 a、a 的位次序列、a 的索引序列如下表：

（1）已知列表 a，a 的位次 wc，求索引 sy。 for i in range(len(a)): sy[wc[i]] = i （2）已知列表 a，a 的索引 sy，求位次 wc。 for i in range(len(a)): wc[sy[i]] = i

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