Python——关于排序算法（冒泡法）
前一阵发的一篇《关于多线程的应用》，本来要去某站爬取几个T的资源，爬了几百G以后重感冒，就休息了一周。未料再次开动时，网站已然设置了反爬机制
可能是我的多线程开的太猛了吧
（峰值时大概50个线程，一分钟能下载1G）
这个周末本想安心写一下关于编程常见的一个排序算法，发现无法爬取自然不甘心，于是折腾了两天还是没搞定
收拾一下心情，讲一下关于排序算法吧，排序问题是编程入门里老生常谈的问题，虽说python也有内置的排序语法而且很好用（sort、sorted），但是讲到数据结构这块，排序的几个常见算法还是有必要学习一下。
冒泡排序法（Bubble Sort）
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 百度百科
冒泡排序算法的原理：
比如要排序n个数字，进行n轮循环比较并操作。每一轮，都是将未排序过的数字，进行两两比较，将较大的数不断往后置换；每一轮都会将本轮中的最大数置于未排序数字中的末位。
举个例子：
有列表[6，3，1，5，4，2]
用冒泡法操作：
第一轮：
6，3比较，6大则6，3互换：
3，6，1，5，4，2
6，1比较，6大则6，1互换：
3，1，6，5，4，2
…………
3，1，5，6，4，2
3，1，5，4，6，2
3，1，5，4，2，6
第一轮结束，最大数6置于末位了。
第二轮：
只需将前5位进行排序即可，
3，1，5，4，2
3，1比较，3大则3，1互换：
1，3，5，4，2
3，5比较，3小则不动，用下一位5进行比较，
5，4比较，5大则5，4互换：
1，3，4，5，2
1，3，4，2，5
第二轮结束，本组最大数5置于末位了。
第三轮：
只需将前4位进行排序即可，
1，3，4，2
1，3比较，1小则不动，下一位，
3，4比较，3小则不动，下一位，
4，2比较，4大则4，2互换：
1，3，2，4
第三轮结束，本组最大数4置于末位了。
第四轮：
只需将前3位进行排序即可，
1，3，2
1，3比较，1小则不动，下一位，
3，2比较，3大则3，2互换：
1，2，3
第四轮结束，本组最大数3置于末位了。
第五轮：
只需将前2位进行排序即可，
1，2
1，2比较，1小则不动
1，2
第五轮结束，本组最大数2置于末位了。
排序结束。
冒泡排序总的平均时间复杂度为
。假设列表中的元素是刚好逆序的：比如[6，5，4，3，2，1]那第一轮就要交换5次，第二轮4次……1次0次，总共次数就是1/2*6*（5+0）也就是1/2*N*（N-1），时间复杂度是n的平方。
coding
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-24 18:39
# @Author : Ed Frey
# @File : bubble_sort.py
# @Software: PyCharm
from time import clock
def timer(f):
def _f(*args):
t0 = clock()
f(*args)
return clock() - t0
return _f
def bubble_sort(num:list):
lenth = len(num)
while lenth:
for i in range(lenth-1):
if num[i]>num[i+1]:
num[i],num[i+1] = num[i+1],num[i]
lenth -= 1
print(num)
return num
if __name__ == '__main__':
num = [6,3,1,5,4,2]
time = timer(bubble_sort)(num)
print(time)timer是计算函数运行计时的函数，详见《Python——关于算法与数据结构》有不记得的小伙伴可以再瞅一眼哈。
运行结果如下：
[3, 1, 5, 4, 2, 6]
[1, 3, 4, 2, 5, 6]
[1, 3, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
6.100000000003325e-05
改进后的coding
上面的代码测试了一下，你会发现的确是时间复杂度中分析的，运行了6个循环（输出结果我直接打印了出来），可是有个问题，不知道你是否有发现。就是，最后3行是一模一样，都是排好序的，换句话说，就是有2行是无用功。
那是否有办法改进一下呢？of course
思路就是:
如果运行到某一轮，所有数字都不需要互换位置，也就是if num[i]>num[i+1]: 该轮中的每一次if条件都没发生，那么，排序就完成了，就可以提前结束while循环，输出结果了。so，只需要加一个flag即可，改进后的代码如下：
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-24 18:39
# @Author : Ed Frey
# @File : bubble_sort.py
# @Software: PyCharm
from time import clock
def timer(f):
def _f(*args):
t0 = clock()
f(*args)
return clock() - t0
return _f
def func(date):
for i in range(10):
print(i**3,date)
def bubble_sort(num:list):
lenth = len(num)
while lenth:
flag = False
for i in range(lenth-1):
if num[i]>num[i+1]:
num[i],num[i+1] = num[i+1],num[i]
flag = True if flag == False:
break lenth -= 1
print(num)
return num
if __name__ == '__main__':
num = [6,3,1,5,4,2]
time = timer(bubble_sort)(num)
print(time)运行结果如下：[3, 1, 5, 4, 2, 6]
[1, 3, 4, 2, 5, 6]
[1, 3, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
5.099999999996774e-05
运行时间上，改进后的代码，是少了一点点。数组元素只有6个，可能不是很明显，如果换成一个很大的数组，就显而易见了。