冒泡排序（Python实现）

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

原理

比较相邻的元素，如果第一个比第二个大，就交换。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

冒泡算法每次都需要对元素进行比较，是一种稳定的排序算法，时间复杂度为：O（n²）

Python实现

# -*- coding:utf-8 -*-
# 冒泡排序

'''
重点：每一轮比较都把最大的数放到最后，第二层循环的循环次数是递减的，
所以j终止的条件是 j = end - i - 1
'''

# while 写法
def bubble_sort(list):
    # if len(list) < 1:
    #     return list

    i = 0
    end = len(list) - 1
    while i < end:
        j = 0
        while j < end - i:
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
            j = j + 1

        i = i + 1

    return list

# for 写法
def bubble_sort_for(list):
    # if len(list) < 1:
    #     return list

    end = len(list)

    # 外循环次数等于需排序个数减 1，比如3个数字，只需要循环两轮，i初始为0
    for i in range(end - 1):
        for j in range(end - i - 1): # 单趟排序比较的次数要减去已排序好的个数（即 i）
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
    return list