冒泡排序

基本原理

将待排序列表中两两元素进行比较,若前面元素比后面元素大,则交换位置.

代码

# -*- coding: utf-8 -*-
'''
冒泡排序：
    列表中元素两两比较，将较大的放到右边。则比较完一轮以后，最大的放到了最后一位。
'''
def bubble_sort1(input_list):
    if len(input_list)<= 1:
        return input_list
    for i in range(0, len(input_list)-1): # 长度为6，需比较5轮。即循环0,1,2,3,4
        for j in range(0,len(input_list)-i-1):
            if input_list[j] >= input_list[j+1]:
                input_list[j],input_list[j+1] = input_list[j+1],input_list[j]
    return input_list
def bubble_sort2(input_list):
    if len(input_list) <= 1 :
        return input_list
    for i in range(1, len(input_list)):
        for j in range(0,len(input_list)-i):
            if input_list[j] >= input_list[j+1]:
                input_list[j],input_list[j+1] = input_list[j+1],input_list[j]
    return input_list
if __name__ == '__main__':
    pre_list = [7,3,5,1,9,4]
    res = bubble_sort2(pre_list)
    print(res)

易忘点和易错点

a. 不要忘记列表长度为1的情况。
b. 循环的边界 i 和 j 容易忘怎么办？ 重在理解。假设列表长度为n=6，则外层循环i需要循环n-1=5轮。因此，i 的边界可以是[0,n-1) 或者 [1, n)。而 i 代表当前循环轮数， j 表示在当前轮数情况下，需要比较的次数。而 当前轮数 i + 比较次数 = n。所以，j 的取值为 [0,n-i-1) 或者 [0,n-i)。
总之一句话： 当前轮数i + 比较次数j = 列表长度。