最近在学习Python，下面是我的一些笔记

冒泡排序

实现思路 ：
使用双重for循环，内层变量为i， 外层为j，在内层循环中不断的比较相邻的两个值（i, i+1）的大小，如果i+1的值大于i的值，交换两者位置，每循环一次，外层的j增加1，等到j等于n-1的时候，结束循环

第一次看不懂很正常，不要灰心，下面是使用代码的实现

arr = [7, 4, 3, 67, 34, 1, 8]
n = len(arr)
for j in range(0, n - 1):
    for i in range(0, n - 1 - j):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]

print(arr)  # [1, 3, 4, 7, 8, 34, 67]

关键点其实在双重for循环变量的配置，我们来分析一下

• 第一次循环： j = 0, i~n-2 range(0, n-1)
  第二次循环： j = 1, i~n-3 range(0, n-1-1)
  第三次循环： j = 2, i~n-4 range(0, n-1-1-1) —> range(0, n-1-j)

理解这一点后，我们就可以换一种写法来实现了

arr = [7, 4, 3, 67, 34, 1, 8]

for j in range(len(arr) - 1, 0, -1):  # [n-1, n-2, ....2, 1]
    for i in range(0, j):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]


print(arr)  # [1, 3, 4, 7, 8, 34, 67]

优化
       写到这里我们发现，无论是第一种写法还是第二种写法，他的时间复杂度都是O(n ^ 2), 第二种写法也仅仅停留在优化样式的层面，并没有带来性能的提升，想象一下，如果我们输入的本来就是一个有序序列，其实只需要一次循环就够了，所以我们需要针对特殊情况进行优化

arr = [7, 4, 3, 67, 34, 1, 8]

for j in range(len(arr)-1, 0, -1):
    count = 0
    for i in range(0, j):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
            count += 1
    if count == 0:
        return

print(arr)  # [1, 3, 4, 7, 8, 34, 67]

       我们在循环中定义了一个变量count，如果第一次循环后count没有变化，就说明输入的是有序序列，这时我们直接return退出循环，这时候的时间复杂度为O(n)

       扩展知识：冒泡排序还是一种稳定性的算法，如果序列中出现两个相同的值的时候，无论选取最大值，还是最小值进行排序，最后两个相同值的前后位置都是不变的。