前一阵发的一篇《关于多线程的应用》,本来要去某站爬取几个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个,可能不是很明显,如果换成一个很大的数组,就显而易见了。