Python实现冒泡排序外层循环为何执行n次而非n-1次

Python中冒泡排序的常见实现代码如下：

array = [5,2,7,8,1,6,3]
n = len(array)

for i in range(n):
    for j in range(n-i-1): 
        if array[j] > array[j+1]:
            array[j],array[j+1] = array[j+1], array[j]

问题描述 #

根据冒泡排序的算法原理，数组长度为n时外层循环总遍历趟数应为n-1次，但上述示例代码中range(n)在数组长度为7时会生成0、1、2、3、4、5、6的整数序列，使外层循环共执行7次，该差异的产生原因和对应的逻辑疏漏如下：

差异产生原因 #

• 第n次外层循环是完全无操作的冗余执行，不会影响最终排序结果。冒泡排序每完成一轮外层遍历，就会将当前未排序区间内的最大元素移动到区间末尾的正确排序位置。当完成n-1轮遍历后，数组末尾的n-1个元素已经全部处于正确位置，剩余的第一个元素必然是全局最小值，不需要再做任何比较交换。
• 该写法属于实现时的非严谨简化，不是逻辑错误。当外层循环变量i取到n-1时，内层循环的遍历范围是range(n - (n-1) -1)也就是range(0)，内层循环不会执行任何语句，仅会空跑一次外层循环的判断逻辑，带来极微小的不必要开销，不会改变数组内容，也不会导致排序出错。

常见的逻辑理解疏漏 #

• 混淆了「代码可运行出正确结果」和「代码符合算法最优逻辑」的边界。range(n)的写法能得到正确排序结果，本质是靠内层循环的边界条件自动兜底了冗余的外层轮次，不代表这种写法是符合算法设计本意的标准实现。
• 没有读懂内层循环边界的隐含含义：n-i-1的边界本质是在标记当前未排序区间的长度，每完成一轮外层遍历，未排序区间长度减1，当i=n-1时未排序区间长度已经为0，不存在需要比较的元素对。
• 记错了冒泡排序的终止条件：冒泡排序的终止条件是未排序区间长度为1，此时区间内仅存的单个元素自然有序，不需要再安排额外的遍历轮次。严谨的标准实现中外层循环应当写为range(n-1)，直接砍掉最后一轮无意义的空跑，逻辑更清晰也没有冗余开销。

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