第9讲. 位次与索引

下面这首古诗为杜甫的《春晓》 ，但顺序被打乱。 （1）请在诗句前的位次括号内标出正确的次序；（2）诗句正确的顺序依次为：③ ① ④ ② 名(位)次 春晓 （ 2 ） ①处处闻啼鸟 （ 4 ） ②花落知多少 （ 1 ） ③春眠不觉晓 （ 3 ） ④夜来风雨声 以前做这样的题是否有过这样的困惑，都是要来描述顺序，但上面两种方法描述的形式是完全不一样的。第一种方法标的是当前诗句的位次，如上，标号为③的诗句应该是第 1 句，所以其位次为 1。而第二种方法是索引描述，第一句是③，所以③放在第 1 个位置。

1. 位次表达的是去哪儿；索引表达的是在哪儿。

2. 对数组排好位次 ≠ 排好顺序 。

如数组 a[0～n-1]各元素的升序位次依次为 wc[0～n-1] ，即 a[0]的位次为 wc[0] 、a[i]的位次为 wc[i] , 但并不能直接按序输出各元素，都不知道最小元素是谁。但通过位次抄写到数组 b[0～n-1]可以完成排序。

for i in range(n):
    b[wc[i]] = a[i]

3. 对数组建好有序索引 ＝ 排好顺序 。

如数组 a[0～n-1]的升序索引为 sy[0～n-1]，即a[sy[0]] ≤a[sy[1]]≤……≤a[sy[i]]≤……≤a[sy[n-1]] 。有了该升序索引就等于数组 a 已经排好序了，你可以直接按序输出各元素。

for i in range(n)
    print(a[sy[i]] )

4. 位次与索引可以相互转换，一重循环即可实现

（1）位次索引 wc[0～n-1] -> sy[0～n-1] #a[i]的位次为 wc[i]，即第 wc[i]个索引指向 i

for i range(n):
    sy[wc[i] ] = i

（2）索引位次 sy[0～n-1] -> wc[0～n-1] #sy(i)指向的元素的位次为 i

for i range(n):
    wc[sy[i] ] = i 

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