Python 四大排序实现（插入排序用索引数组实现） 要求说明： 原数组 a 存储真实数据 索引数组 sy：存下标，只对 sy 排序，不改动原数组 a 实现：冒泡排序、选择排序、索引版插入排序、计数排序

# 1. 冒泡排序（直接排原数组）
def bubble_sort(a):
    arr = a.copy()
    n = len(arr)
    for i in range(n):
        flag = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
        if not flag:
            break
    return arr

# 2. 选择排序（直接排原数组，min_idx改为k）
def select_sort(a):
    arr = a.copy()
    n = len(arr)
    for i in range(n):
        k = i
        for j in range(i + 1, n):
            if arr[j] < arr[k]:
                k = j
        arr[i], arr[k] = arr[k], arr[i]
    return arr

# 3. 插入排序（索引数组sy实现，key_idx改为k，不修改原数组a）
def insert_sort_index(a):
    n = len(a)
    sy = list(range(n))  # 索引数组sy，初始0,1,2...n-1
    for i in range(1, n):
        # 当前待插入的索引
        k = sy[i]
        j = i - 1
        # 比较原数组a的值，移动索引
        while j >= 0 and a[sy[j]] > a[k]:
            sy[j + 1] = sy[j]
            j -= 1
        sy[j + 1] = k
    # 根据排序后的索引数组生成有序结果
    res = [a[idx] for idx in sy]
    return sy, res

# 4. 计数排序（仅适用于非负整数）
def count_sort(a):
    if not a:
        return []
    max_val = max(a)
    count = [0] * (max_val + 1)
    # 统计频次
    for num in a:
        count[num] += 1
    # 回填结果
    res = []
    for i in range(max_val + 1):
        res.extend([i] * count[i])
    return res


# 测试示例
if __name__ == "__main__":
    a = [5, 2, 9, 1, 5, 6]
    print("原始数组 a =", a)

    # 冒泡排序
    bubble_res = bubble_sort(a)
    print("冒泡排序结果:", bubble_res)

    # 选择排序
    select_res = select_sort(a)
    print("选择排序结果:", select_res)

    # 索引版插入排序
    sy, insert_res = insert_sort_index(a)
    print("插入排序-索引数组 sy =", sy)
    print("插入排序-有序数组 =", insert_res)

    # 计数排序
    count_res = count_sort(a)
    print("计数排序结果:", count_res)

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