冒泡排序

基本思想

依次比较两个相邻元素nums[i]和nums[i-1]，将较大/小的元素交换到前面去，就像泡泡上浮的过程一样；比较完后进行下一轮比较。

具体实现

from typing import List
def bubble_sort(nums: List):
    length = len(nums)
    for i in range(length):
        for j in range(1, length-i):
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]

性能分析

平均时间复杂度：

• 求数组长度length：
• 两个循环：
• 总和：

空间复杂度：

优化

设置一个符号位flag，表明是否发生交换，若未发生交换说明数组已经有序。

def bubble_sort(nums: List):
    flag = 0
    length = len(nums)
    for i in range(length):
        for j in range(1, length-i):
            if nums[j] < nums[j-1]:
                nums[j], nums[j-1] = nums[j-1], nums[j]
                flag = 1
        if flag == 0:
            break