冒泡排序

冒泡排序的思想：

　　将元素两两之间进行比较，谁大就往后移动，直到将最大的元素排到最后面，一直循环，就形成了有序的序列

# 冒泡排序
def bubble(arr):
    length = len(arr)
    for i in range(length-1):
        for j in range(length-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr


arr = [2, 1, 3, 56, 32, -9, 3, 0, 34, 334, 5]
print('冒泡排序结果：', bubble(arr))
结果：
冒泡排序结果： [-9, 0, 1, 2, 3, 3, 5, 32, 34, 56, 334]

# 找出队列第2个最大的数（根据冒泡排序实现的）
def bubble_k(arr, k):
    length = len(arr)
    for i in range(k):
        for j in range(length-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr[-k]


arr = [2, 1, 3, 56, 32, -9, 3, 0, 34, 334, 5]
print('冒泡结果：', bubble_k(arr, 2))

结果：
冒泡结果：56

冒泡排序优化1：

　设定一个变量为False，如果元素之间交换了位置，将变量重新赋值为True,最后再判断，在一次循环结束后，变量如果还是为False，则brak退出循环，结束排序。

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        flag = False
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
        if not flag:
            break
    return arr


arr = [2, 1, 3, 56, 32, -9, 3, 0, 34, 334, 5]
print('冒泡排序结果：', bubble_sort(arr))

冒泡排序优化2：就是在优化方案1的基础上，反正排一次（从左到右是取大值，从右到左是取小值），这样可以减少循环次数，提高算法效率

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        flag = False
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True
        if flag:
            flag = False
            for j in range(len(arr) - 2 - i, 0, -1):
                if arr[j - 1] > arr[j]:
                    arr[j], arr[j - 1] = arr[j - 1], arr[j]
                    flag = True
        if not flag:
            break
    return arr


arr = [2, 1, 3, 56, 32, -9, 3, 0, 34, 334, 5]
print('冒泡排序结果：', bubble_sort(arr))
结果：
冒泡排序结果： [-9, 0, 1, 2, 3, 3, 5, 32, 34, 56, 334]