基于条件交换列表相邻元素实现Bubble Sort冒泡排序输出异常的原因及修复

当前代码的核心问题 #

你写的元素交换逻辑本身没有问题，错误根源是只实现了单轮相邻对比交换，缺失了冒泡排序要求的多轮遍历结构。

具体执行逻辑拆解：

• 冒泡排序的核心规则是，每一轮遍历都会从头开始对比相邻元素，把当前未排序区间里最大的元素，一步步“冒泡”移动到未排序区间的最右端
• 你当前的代码只完成了1轮相邻遍历，对应输入[5,1,4,2,8]的单轮执行过程为：
  1. 对比位置0的5和位置1的1，交换后数组为[1,5,4,2,8]
  2. 对比位置1的5和位置2的4，交换后数组为[1,4,5,2,8]
  3. 对比位置2的5和位置3的2，交换后数组为[1,4,2,5,8]
  4. 对比位置3的5和位置4的8，不满足交换条件，数组不变化
     跑完这一轮后代码直接返回结果，正好就是你得到的输出[1,4,2,5,8]——这只是把数组里最大的两个数挪到了末尾位置，靠前的[1,4,2]区间里还存在4>2的相邻逆序对，根本没有完成全量排序。

修复方案 #

冒泡排序需要嵌套两层循环来覆盖所有轮次的遍历：

• 外层循环控制总的冒泡轮次：对于长度为n的数组，最多需要n-1轮遍历，每一轮至少会把1个元素移动到最终的正确位置，当数组只剩1个元素未确认顺序时，自然已经完成排序
• 内层循环控制每一轮的相邻对比范围：因为每一轮跑完后，数组末尾已经积累了i个排好序的元素，这部分元素不需要再参与后续对比，所以每一轮的遍历范围可以逐轮缩小，减少无效对比

你使用的Python解包式交换array[i+1],array[i] = array[i],array[i+1]是完全正确的，不需要改动。

基础修正版代码 #

def bubbleSort(array):
    n = len(array)
    # 外层循环：控制冒泡轮次
    for i in range(n - 1):
        # 内层循环：在当前未排序区间做相邻对比交换
        for j in range(n - 1 - i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

print(bubbleSort([5,1,4,2,8]))
# 输出结果：[1, 2, 4, 5, 8]

优化版代码（提前终止） #

可以增加一个交换标记，如果某一轮遍历全程没有发生任何交换，说明整个数组已经完全有序，不需要再跑后续的轮次，直接退出循环即可：

def bubbleSort(array):
    n = len(array)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
                swapped = True
        # 本轮无任何交换，数组已全部有序，提前终止
        if not swapped:
            break
    return array

内容的提问来源于stack exchange，提问作者Thavas Antonio