三种基础排序：冒泡、选择、插入

题目

练习 11：实现冒泡、选择、插入排序，并统计元素比较次数。

输入：第一行 n，第二行 n 个整数。

比较次数只统计两个元素之间的大小比较，不统计下标边界判断。

参考程序：ex11.py；空白练习：lx11.py。

完整代码

以下内容与 ex11.py 一致，可对照右侧讲解阅读。

"""练习 11：实现冒泡、选择、插入排序，并统计元素比较次数。
输入：第一行 n，第二行 n 个整数。
比较次数只统计两个元素之间的大小比较，不统计下标边界判断。

学习说明：
- 三个函数都先复制 data，避免排序时改动原列表；返回“排序结果, 比较次数”。
- 冒泡排序：相邻元素逆序就交换；每一轮把尚未排好的一端最大值放到末尾。
- 选择排序：在未排序部分找到最小值，放到本轮开头。
- 插入排序：取出一个 key，在前面已排序部分中向左寻找插入位置。
- comparisons 只在实际比较两个数字时加 1；主程序对三种算法使用同一份输入并分别打印。
"""
def bubble_sort(data):
    # 复制输入列表；比较次数从 0 开始。
    values = data[:]
    comparisons = 0
    # end 是本轮尚未排好部分的右边界，每轮都向左缩小。
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        # 从左到右检查相邻元素，把较大的值逐步交换到右侧。
        for index in range(end):
            comparisons += 1
            if values[index] > values[index + 1]:
                values[index], values[index + 1] = values[index + 1], values[index]
                swapped = True
        if not swapped:
            break
    return values, comparisons


def selection_sort(data):
    # 每轮选出剩余元素中的最小值，放到 start 位置。
    values = data[:]
    comparisons = 0
    for start in range(len(values) - 1):
        minimum = start
        for index in range(start + 1, len(values)):
            comparisons += 1
            if values[index] < values[minimum]:
                minimum = index
        values[start], values[minimum] = values[minimum], values[start]
    return values, comparisons


def insertion_sort(data):
    # 左侧部分在每轮开始时已经有序；把下一个 key 插入正确位置。
    values = data[:]
    comparisons = 0
    for index in range(1, len(values)):
        key = values[index]
        position = index - 1
        while position >= 0:
            comparisons += 1
            if values[position] > key:
                values[position + 1] = values[position]
                position -= 1
            else:
                break
        values[position + 1] = key
    return values, comparisons


n = int(input())
values = list(map(int, input().split()))[:n]
# 将函数与显示名称配对，逐个运行三种排序。
for name, sort_function in (
    ("bubble", bubble_sort),
    ("selection", selection_sort),
    ("insertion", insertion_sort),
):
    result, comparisons = sort_function(values)
    print(name + ":", *result)
    print("comparisons:", comparisons)

运行结果

示例输入：

5
4 2 5 1 3

程序输出：

bubble: 1 2 3 4 5
comparisons: 10
selection: 1 2 3 4 5
comparisons: 10
insertion: 1 2 3 4 5
comparisons: 8