冒泡排序Bubble Sort

Niklaus Wirth: “程序=数据结构+算法”

排序：将⼀组“⽆序”的记录序列调整为“有序”的记录序列。

列表排序：将⽆序列表变为有序列表

• 输⼊：列表

• 输出：有序列表 升序与降序

• 内置排序函数：sort()

冒泡排序 (Bubble Sort)

• 列表每两个相邻的数，如果前⾯⽐后⾯⼤，则交换这两个数。

• ⼀趟排序完成后，则⽆序区减少⼀个数，有序区增加⼀个数。

• 代码关键点：趟、⽆序区范围

• 时间复杂度 O( n^2 )

过 程：

python实现

def bubble_sort(li):    # 入参li是一个无序的列表    for i in range(len(li)-1):        # 第二层减i去掉有序区长度        for j in range(len(li)-1-i):            if li[j] > li[j+1]: # 前面的数比后面的数大               # 前后数据交换，大数往后排               li[j], li[j+1] = li[j+1], li[j]     return li # 返回升序列表

上面的python实现还是可以再优化的，比如以下情况：

其实在第三次的时候已经排序完成，但是由于实现了双层循环必须走完才能结束，所以之后的流程都是无意义的，考虑时间开销，可以做如下优化：

def