第8讲. 索引排序——让无序序列按索引有序

数组 a[0～n-1]无序，想实现 a 有序但又不想修改 a，可以考虑给 a 建立有序索引。 即引入一个数组 sy[0～n-1]实现 a 按索引有序，即实现：a[sy[0]]<=a[sy[1]]<=…<=a[sy[n-1]] 。构成生成 sy 数组的过程就是索引排序。

1. 索引排序的一般过程

（1）索引数组初始化：一一对应

n = len(a)
sy = [i for i in range(n)]

2. 用冒泡排序算法实现有序索引

for i in range(n-1):
    for j in range(n-1-i):
        if a[sy[j]]>a[sy[j+1]]:
            sy[j],sy[j+1] = sy[j+1],sy[j]

3. 用选择排序算法实现有序索引

for i in range(n-1):
    k = i
    for j in range(i+1,n):
        if a[sy[j]]<a[sy[k]]:
            k = j
    if k!=i:
        sy[i],sy[k] = sy[k],sy[i]

4. 用插入排序算法实现有序索引

for i in range(1,n):
    t = sy[i]
    j = i-1
    while j>=0 and a[sy[j]]>a[t]:
        sy[j+1] = sy[j]
        j -= 1
    sy[j+1] = t

第9讲. 位次与索引

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