能否将GeeksforGeeks冒泡排序外层循环改为range(n-1)？

原代码 #

# Python program for implementation of Bubble Sort

def bubbleSort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):

        # Last i elements are already in place
        for j in range(0, n-i-1):

            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]


# Driver code to test above
if __name__ == "__main__":
    arr = [5, 1, 4, 2, 8]

    bubbleSort(arr)

    print("Sorted array is:")
    for i in range(len(arr)):
        print("%d" % arr[i], end=" ")

技术问询 #

原代码的外层循环为for i in range(n)，能否将其修改为for i in range(n-1)以减少一次循环？个人认为即使在最坏情况下，排序最多只需要len(array)-1轮即可完成，想确认是否存在考虑疏漏的地方。

解答 #

完全可以把外层循环改成for i in range(n-1)，你的判断完全正确——最坏情况下，冒泡排序只需要n-1轮外层循环就能完成排序。

道理很直白：冒泡排序每一轮外层循环都会把当前未排序区间里的最大元素“推”到它的最终位置。对于长度为n的数组，我们只需要把n-1个较大的元素逐个归位，剩下的最后一个元素自然就在正确的位置上了。

原代码里的range(n)会让循环跑n次，但第n次外层循环时，内层循环的range(0, n-n-1)等价于range(0, -1)，这时候内层循环根本不会执行，相当于多做了一次无意义的外层循环判断，对排序结果没影响，但纯粹浪费了一点性能。

修改后的代码完全能正常运行，不会有任何问题。比如把外层循环改成range(n-1)后，测试原数组[5,1,4,2,8]，排序结果和原代码完全一致，还少了一次不必要的循环。

另外，冒泡排序还有个常用优化：如果某一轮外层循环里没有发生任何交换，说明数组已经完全有序，可以直接终止循环，进一步提升效率。优化后的代码示例如下：

def bubbleSort(arr):
    n = len(arr)
    for i in range(n-1):
        swapped = False
        # Last i elements are already in place
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 本轮无交换，数组已完全有序，提前退出
        if not swapped:
            break

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