通过相邻元素交换排序：为何len(f)*(len(f)-2)是有效终止条件？

先看你写的代码：

n=input()
f=n.split(' ')
count = 0

while count <  ( len(f) * (len(f)-2) ):
    
    for z in range(1, len(f)):
       
        if int(f[z]) > int(f[z-1]):
            f[z], f[z-1] = f[z-1], f[z]
       
        if int(f[z]) < int(f[z-1]):
            count +=1
            
print (f)

一、先拆解你的代码逻辑 #

你的代码本质是变种冒泡排序，核心逻辑是：

1. 把输入字符串拆成字符串数字列表f
2. 外层用count计数器控制循环次数，只要count没达到设定的上限就继续
3. 内层循环从第二个元素开始，逐个和前一个元素比较：
   • 如果当前元素更大，就交换位置（把大元素往左挪，最终会得到降序排列的数组）
   • 不管是交换后还是本来就满足「当前元素比前一个小」，都会让count加1

二、为什么小上限（比如len(f)）不行？ #

冒泡排序要完成排序，需要足够的遍历次数。假设数组长度是n：

• 最坏情况（比如原本是升序，要改成降序），最大的元素要从最后一位挪到第一位，得走n-1步；第二大的元素要从倒数第二位挪到第二位，得走n-2步……
• 总共需要的交换次数是 (n-1)+(n-2)+...+1 = n*(n-1)/2

如果上限只设成n，count到n就停止循环了，但此时很多元素还没挪到正确位置，自然排序失败。

三、为什么len(f)*(len(f)-2)或更大值能生效？ #

因为n*(n-2)（n是数组长度）比最坏情况需要的交换次数n*(n-1)/2大（当n>2时）：

• 比如n=3，3*(3-2)=3，刚好等于最坏情况的交换次数
• 比如n=4，4*(4-2)=8，大于最坏情况的6次交换

当你把上限设得比最坏情况的交换次数大，就能保证：在count达到上限之前，数组已经完全排好序了。之后的循环里，虽然count还会继续涨（因为数组已经是降序，每个相邻元素都是后小前大，第二个if每次都会触发），但只要达到上限，循环就会停止，最终输出正确的排序结果。

四、可以优化的点 #

你的代码有两处可以简化的地方：

1. 计数逻辑冗余：现在count不是只记录交换次数，而是只要后元素比前元素小就加1，完全没必要。可以改成只有发生交换时才计数。
2. 避免无效循环：当某一轮内层循环完全没交换，说明数组已经排好序，直接跳出循环就行，不用等count到上限。

优化后的代码示例：

n = input()
# 直接转成整数列表，避免每次比较都转类型
f = [int(num) for num in n.split(' ')]

while True:
    swapped = False
    for z in range(1, len(f)):
        if f[z] > f[z-1]:
            f[z], f[z-1] = f[z-1], f[z]
            swapped = True
    # 这一轮没交换，说明已经排好序了
    if not swapped:
        break

print(f)

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