冒泡排序

基本思想

每次比较相邻的两个数，如果它们顺序错误就把它们交换过来

对7 9 2 5 3升序排列

• 第一步：第一位的7和第二位的9比较，如果前面的值小于后面的，就交换--> 9 7 2 5 3
• 第二步：同上，比较第二位的7和第三位的2，不用交换--> 9 7 2 5 3
• 第三步：比较第三位的2和第四位的5，交换--> 9 7 5 2 3
• 第四步：比较第四位的2和第五位的3，交换--> 9 7 5 3 2
  第一次循环结束，最小的数排在了最后面，在从前往后循环4次，就可以实现降序排列

python实现冒泡排序

#!/usr/bin/python
# encoding: utf-8

# 冒牌排序（降序）

# 待排序的列表
elem = [3, 10, 7, 4, 9, 8]

for i in range(1, len(elem) - 1):
    # 第i趟冒泡排序
    for j in range(0, len(elem) - i):
        # 比较相邻的两个数
        if elem[j] < elem[j+1]:
            elem[j],elem[j+1] = elem[j+1],elem[j]

print(elem) # [10, 9, 8, 7, 4, 3]

时间复杂度

从最关键的双层for循环可以看出，冒泡排序的时间复杂度为N的平方。

*参考资料《啊哈！算法》