插入排序#

def insertion_sort(arr):
    """
    插入排序函数
    参数:
        arr: 待排序的列表
    返回:
        排序后的列表
    """
    # 从第二个元素开始（索引1），因为第一个元素可以看作已排序
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的元素
        j = i - 1     # 已排序部分的最后一个元素的索引
        
        # 在已排序部分中从后向前寻找插入位置
        # 同时将大于key的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 将元素向后移动
            j -= 1
        
        # 将key插入到正确位置
        arr[j + 1] = key
        
        # 可选：打印每轮排序后的结果
        print(f"第{i}轮插入后: {arr}")
    
    return arr

def insertion_sort_demo():
    """插入排序演示"""
    data = [5, 2, 4, 6, 1, 3]
    print(f"原始数组: {data}")
    print("排序过程:")
    
    sorted_data = insertion_sort(data.copy())
    print(f"最终结果: {sorted_data}")

# 优化版本：二分查找插入位置
def binary_insertion_sort(arr):
    """
    使用二分查找优化的插入排序
    减少比较次数，但移动次数不变
    """
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用二分查找找到插入位置
        left, right = 0, i
        while left < right:
            mid = (left + right) // 2
            if arr[mid] > key:
                right = mid
            else:
                left = mid + 1
        
        # 移动元素为key腾出空间
        for j in range(i, left, -1):
            arr[j] = arr[j - 1]
        
        # 插入key
        arr[left] = key
    
    return arr

# 运行演示
insertion_sort_demo()

# 示例：对学生成绩进行排序
def sort_student_scores():
    students = [
        ("Alice", 85),
        ("Bob", 92),
        ("Charlie", 78),
        ("Diana", 96),
        ("Eve", 88)
    ]
    
    # 按成绩排序（使用插入排序思想）
    for i in range(1, len(students)):
        key_student = students[i]
        j = i - 1
        
        while j >= 0 and students[j][1] > key_student[1]:
            students[j + 1] = students[j]
            j -= 1
        
        students[j + 1] = key_student
    
    return students

# 运行示例
sorted_students = sort_student_scores()
for name, score in sorted_students:
    print(f"{name}: {score}")