不知不觉就写到第100篇了~~
最近一直在写排序的算法,可能讲到合并排序法,很多人就会有点晕乎了,还是要多多研究练习,才能得法。包括我也是,看教程的时候感觉懂了,开始写的时候感觉都忘记了,再复习总结,再过一遍,总算深入一点。
趁热打铁,前面几期的排序,不知道大家是否有发现一个关于空间复杂度的问题,冒泡、插入、选择这三种,我代码都是直接在原列表内部之间交换位置,就实现了排序,不需要新的空间。而上一节的合并排序法,有初始化一个空的列表c,然后按大小往里丢数字,也就是生成了一个新的list,就是说,开辟了新的空间。
合并排序法的空间复杂度是O(N),当然,一个小小的list占不了很多空间,但是空间复杂度如果变成了N的平方级别,那随着数据量的增长,对空间的占用就是指数级的增长,要研究数据结构和算法,空间复杂度可是必须要考虑的。
打个比方,编写了一个游戏,游戏本身就占用很多内存,这个时候代码中又非常多O(N2)复杂度的代码,游戏在电脑上运行起来,就会很吃内存。简单点讲,就是牛逼的电脑跑起来很顺畅,配置低一点的电脑可能就玩的很卡顿,为了玩个游戏还要升级电脑?这个游戏是有多魔幻呀?开发一个产品,自然要考虑到用户的设备配置高低,是否适配大部分人的电脑硬件。
今天,我们更新最后一个排序算法——快速排序法。
快速排序法(quick sort)
先来看一下百度百科的定义:
快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 百度百科
合并排序法如果理解了,那么这节的快速排序法也就不难理解了,可能还是比合并排序法稍微难那么一点点,所以是放在最后来讲。
直接举例子吧:
先讲2个单词:
pivot 英 [ˈpɪvət] 枢轴; 中心点,中枢; [物] 支点,支枢;
partition 英 [pɑ:ˈtɪʃn] 分割; 隔墙; 划分,分开; 隔离物;
以第一个元素作为pivot,然后将后续所有元素与pivot比较,小的丢左边,大的丢右边,最后pivot置于中间,这一轮下去,就变成了一个以pivot为中心,左边小、右边大的list。然后递归一下,将左边、右边的list继续轮下去。
有列表a = [4,5,3,8,2,9,7,1,6]
用快速排序法操作:
取首个元素4作为pivot,
第一轮:
看剩下的元素,依次往后找第一个比pivot大的数字,是5,同时从末尾向前找第一个比pivot小的数字,是1,将这一大一小互换位置,
[4,1,3,8,2,9,7,5,6]
第二轮:
接着刚才的2个位置,继续往后找比pivot大的数字,是8,继续向前找比pivot小的数字,是2,将这一大一小互换位置,
[4,1,3,2,8,9,7,5,6]
第三轮:
接着刚才的2个位置,继续往后找比pivot大的数字,是8,继续向前找比pivot小的数字,是2,这个时候出现了交叉,假设比pivot大的数字序号是i,比pivot大的数字序号是j,前面两轮都是i<j,而这一轮i>j了。这个时候,a[j] = 2,我们将pivot与a[j]进行交换:
[2,1,3,4,8,9,7,5,6]
这一个循环就完成了。不知道你是否发现一个规律:pivot左边都是比pivot小的数字,右边都是大于pivot的数字。没错,就是这个样子
第一个循环完成了,就进行后续的n个循环,原列表返回的结果等同于:拆分成了left+pivot+right三部分,left是小的,right是大的。递归调用此方法,直到left和right只有一个元素,返回的结果就是小+pivot+大。再原路回拼成多个元素的left,right,返回最终排好序的list。
怎么样?晕了吧,hohoho~~~
coding
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-30 10:56
# @Author : Ed Frey
# @File : quick_sort.py
# @Software: PyCharm
from time import clock
def timer(f):
def _f(*args):
t0 = clock()
f(*args)
return clock() - t0
return _f
def partition(num:list,first,last):
pivotvalue = num[first]
mark_left = first+1
mark_right = last
done = False
while not done:
while mark_left <= mark_right and num[mark_left] <= pivotvalue:
mark_left += 1
while mark_left <= mark_right and num[mark_right] >= pivotvalue:
mark_right -= 1
if mark_left >= mark_right:
done = True
else:
num[mark_left], num[mark_right] = num[mark_right], num[mark_left]
num[first],num[mark_right] = num[mark_right],num[first]
print(num)
return mark_right
if __name__ == '__main__':
num = [4,5,3,8,2,9,7,1,6]
time = timer(partition)(num,0,8)
print(time)
上方是单个partition的操作coding,运行结果num变成了左边小的数值+pivotvalue+右边大的数值,返回值我们取的mark_right,这个是为了后续的递归调用做铺垫。
运行结果:
[2, 1, 3, 4, 8, 9, 7, 5, 6]
2.6999999999999247e-05
Process finished with exit code 0
然后我们再加入递归,将left的[2, 1, 3]和right的[8, 9, 7, 5, 6]分别进行快速排序、拼接。也就是num切片一下,变成了num[:markright]和num[markright+1:],再次调用partition,直到left和right都只有一个元素或空为止。
完整的coding
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-30 10:56
# @Author : Ed Frey
# @File : quick_sort.py
# @Software: PyCharm
from time import clock
def timer(f):
def _f(*args):
t0 = clock()
f(*args)
return clock() - t0
return _f
def partition(num:list,first,last):
pivotvalue = num[first]
mark_left = first+1
mark_right = last
done = False
while not done:
while mark_left <= mark_right and num[mark_left] <= pivotvalue:
mark_left += 1
while mark_left <= mark_right and num[mark_right] >= pivotvalue:
mark_right -= 1
if mark_left >= mark_right:
done = True
else:
num[mark_left], num[mark_right] = num[mark_right], num[mark_left]
num[first],num[mark_right] = num[mark_right],num[first]
print(num)
return mark_right
def quick_sort(num:list,first,last):
if first < last :
splitpoint = partition(num,first,len(num)-1)
quick_sort(num,first,splitpoint-1)
quick_sort(num,splitpoint+1,last)
if __name__ == '__main__':
num = [4,5,3,8,2,9,7,1,6]
first = 0
last = len(num)-1
time = timer(quick_sort)(num,first,last)
print(time)
运行结果:
[2, 1, 3, 4, 8, 9, 7, 5, 6]
[1, 2, 3, 4, 8, 9, 7, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
0.000128000000000017
Process finished with exit code 0
小结
合并排序法总的平均时间复杂度稍微有点尴尬,如果是平均情况的话也是O(N*logN)。但如果碰到黑天鹅:比如刚好是逆序排列的,也就pivot右侧的值都比pivot小,right循环完挪回pivot左边,如此下去,循环N轮。
上面的2个代码可能看着稍微有点晕,,其实有更简便的coding,只是上面的方法,没有开辟新的list,也就是说没有产生新的空间复杂度。
如果不考虑空间复杂度。那么可以参考以下简便的coding:
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-30 16:40
# @Author : Ed Frey
# @File : quick_sort_usingnewspace.py
# @Software: PyCharm
from time import clock
def timer(func):
def _f(*args):
t0 = clock()
func(*args)
return clock() - t0
return _f
def _quick_sort(num:list):
if len(num) <= 1:
return num
pivotvalue = num[0]
num_left = _quick_sort([x for x in num[1:] if x < pivotvalue])
num_right = _quick_sort([x for x in num[1:] if x > pivotvalue])
print(num_left+[pivotvalue]+num_right)
return num_left+[pivotvalue]+num_right
if __name__ == "__main__":
num = [4,5,3,8,2,9,7,1,6]
time = timer(_quick_sort)(num)
print(time)
怎么样,这个用到新空间的代码就很简烈了吧~~
最后的最后,我们只讲了正序,如果要做反序,要再单独做一个函数吗??NO NO NO其实,python自带的函数sort如果你用的溜的话,就明白,其实是通过一个默认参数来实现的,中间就是用了切片的[::-1]来实现了逆序,其实python自带的语法蛮强大的。coding也分享给大家:
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-30 16:40
# @Author : Ed Frey
# @File : quick_sort_usingnewspace.py
# @Software: PyCharm
def _quick_sort(num:list):
if len(num) <= 1:
return num
pivotvalue = num[0]
num_left = _quick_sort([x for x in num[1:] if x < pivotvalue])
num_right = _quick_sort([x for x in num[1:] if x > pivotvalue])
return num_left+[pivotvalue]+num_right
def quick_sort(num,reverse = False):
nums = _quick_sort(num)
if reverse:
return nums[::-1]
return nums
if __name__ == "__main__":
num = [4,5,3,8,2,9,7,1,6]
print(quick_sort(num))
print(quick_sort(num,reverse = True))
在排序算法的最后的最后,我再讲一点,其实我们仅仅是为了学习排序的算法,增强对算法和数据结构的理解,实战中,万万没必要自己写一个排序的算法去使用。因为python有自带排序的语法,2行就能实现排序,不信,你看:
num = [4,5,3,8,2,9,7,1,6]
print(sorted(num))
这2行就能直接实现排序了