资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

8行代码实现快速排序,简单易懂图解!

快速排序是一种常用的排序算法,比选择排序快的多。在之前的我随笔中也写过关于快速排序的算法,也可以看一下和现在的区别python实现快速排序 - Mr-Yang` - 博客园 (cnblogs.com)。

成都创新互联专注为客户提供全方位的互联网综合服务,包含不限于做网站、成都网站制作、将乐网络推广、微信小程序开发、将乐网络营销、将乐企业策划、将乐品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;成都创新互联为所有大学生创业者提供将乐建站搭建服务,24小时服务热线:028-86922220,官方网址:www.cdcxhl.com

在看快速排序之前,要先了解一下递归,对于递归我之前的文章中也有提到python递归函数 - Mr-Yang` - 博客园 (cnblogs.com),在这里我补充一个关于递归的一个点:基线条件和递归条件

一、基线条件和递归条件

由于递归函数是自己调用自己,因此编写这样的函数时容易出错,从而导致无限循环。示例如下:

def countdown(i):
    print(i)
    countdown(i-1)

如果运行上述代码,就会发现一个问题:这个函数运行起来是不会停止,直到到达递归的最大深度。

正是因为这样,编写递归函数的时候,必须告诉它何时停止递归,所以每个递归函数都有两个部分:基线条件(base case)和递归条件(recursive case)。递归条件指定的是函数调用自己,而基线条件则指的是不再调用自己,从而避免循环。例如给 countdown 添加基线条件。

def countdown(i):
    print(i)
   	if i <= 1:	#<----------基线条件
        return
    else:	#<--------------递归条件
        countdown(i-1)

这样就按照预期那样执行,不会无限循环下去如图所示

二、快速排序

因为对于排序来说,最简单的就是一个空列表,或者只包含一个元素的列表,所以可以将基线条件设置为空或只包含一个元素,在这种情况下,只需要返回原列表。

def quicksort(alist):
    if len(alist) < 2:
        return alist

思路如下图所示:

代码如下:

def quicksort(alist):
    if len(alist) < 2:
        return alist	# 基线条件为空或只包含一个元素的列表是有序的。
    else:
        pivot = alist[0]	# 选择基准值
        less = [i for i in alist[1:] if i <= pivot]	# 由小于基准值的元素组成
        biggish = [i for i in alist[1:] if i > pivot]	# 由大于基准值的元素组成
        return quicksort(less) + [pivot] + quicksort(biggish)

作者:Mr-Yang

出处:https://www.cnblogs.com/XiaoYang-sir/p/.html

版权:本作品采用「署名-非商业性使用-相同方式共享 4.0 国际」许可协议进行许可。


当前题目:8行代码实现快速排序,简单易懂图解!
文章出自:http://cdkjz.cn/article/dsoggpg.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220