buble sort 冒泡排序

思路

每次比较相邻两个元素大小，如果不是有序的就交换，遍历完当前的范围[start,end]，end-1，继续比较[start, end-1]这个范围内的相邻的元素，如果不是有序那就交换，重复这个过程，直到范围内只有一个元素。优化，如果当前范围遍历完也没有需要交换的元素，说明这个列表是有序的，就不用在继续遍历了。

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

代码

arr = [64, 34, 25, 12, 22, 11, 90]

# Iterating adjacent two elements, swap if not sorted.
# Each time an iteration finished, the end index of the arr to be sorted minus one as the last element of the current arr is sorted.
# Repeate the above process, until no elements need to be swapped.
n = len(arr)

for i in range(n):
    flag = False
    for j in range(n-1-i):
        # j j+1
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
            flag = True
    if not flag:
        break
print(arr) # [11, 12, 22, 25, 34, 64, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17