排序算法

冒泡排序

1. 基础版：重复遍历数组，每次比较相邻元素，将较大的元素 “冒泡” 到数组末尾；每轮遍历后，未排序区间的最大值会被放到正确位置，逐步缩小未排序区间。

def bubble_sort_basic(arr):
    """
    基础版冒泡排序
    :param arr: 待排序的列表（会直接修改原列表）
    :return: 排序后的列表
    """
    # 复制原列表，避免修改输入的原始数据
    arr_copy = arr.copy()
    n = len(arr_copy)
    
    # 外层循环：控制排序轮数，共n-1轮（最后一个元素无需比较）
    for i in range(n - 1):
        # 内层循环：遍历未排序区间，每轮减少i次比较（已排序i个元素在末尾）
        for j in range(n - 1 - i):
            # 比较相邻元素，若前>后则交换
            if arr_copy[j] > arr_copy[j + 1]:
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
    
    return arr_copy

# 测试基础版本
if __name__ == "__main__":
    test_arr = [64, 34, 25, 12, 22, 11, 90]
    sorted_arr = bubble_sort_basic(test_arr)
    print("原始数组：", test_arr)
    print("排序后数组：", sorted_arr)

2. 优化版本（提前终止 + 缩小遍历范围） 基础版本存在冗余：若某一轮遍历中没有发生任何交换，说明数组已完全有序，可直接终止；此外，记录最后一次交换的位置，后续遍历只需到该位置即可（该位置后的元素已有序）。

def bubble_sort_optimized(arr):
    """
    优化版冒泡排序（提前终止+缩小遍历范围）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    arr_copy = arr.copy()
    n = len(arr_copy)
    # 记录最后一次交换的位置，初始为n-1（未排序区间的末尾）
    last_swap_idx = n - 1
    
    while last_swap_idx > 0:
        # 标记本轮是否发生交换
        swapped = False
        # 本轮遍历的终点：last_swap_idx（之后的元素已有序）
        current_end = last_swap_idx
        # 重置最后交换位置，若本轮无交换则保持0，循环终止
        last_swap_idx = 0
        
        for j in range(current_end):
            if arr_copy[j] > arr_copy[j + 1]:
                # 交换相邻元素
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
                swapped = True
                # 更新最后一次交换的位置
                last_swap_idx = j
        
        # 若本轮无交换，说明数组已有序，直接退出
        if not swapped:
            break
    
    return arr_copy

# 测试优化版本
if __name__ == "__main__":
    # 测试用例1：普通无序数组
    test_arr1 = [64, 34, 25, 12, 22, 11, 90]
    # 测试用例2：近乎有序数组（优化版优势明显）
    test_arr2 = [1, 2, 3, 5, 4, 6, 7]
    # 测试用例3：空数组
    test_arr3 = []
    # 测试用例4：单元素数组
    test_arr4 = [5]
    
    print("优化版测试结果：")
    print(f"原始数组1：{test_arr1} → 排序后：{bubble_sort_optimized(test_arr1)}")
    print(f"原始数组2：{test_arr2} → 排序后：{bubble_sort_optimized(test_arr2)}")
    print(f"原始数组3：{test_arr3} → 排序后：{bubble_sort_optimized(test_arr3)}")
    print(f"原始数组4：{test_arr4} → 排序后：{bubble_sort_optimized(test_arr4)}")