首页
学习
活动
专区
工具
TVP
发布

Python——关于排序算法(快速排序法)

这是奔跑的键盘侠的第100篇文章

不知不觉就写到第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行就能直接实现排序了
下一篇
举报
领券