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

快速排序是一种常用的排序算法,比选择排序快的多。在之前的我随笔中也写过关于快速排序的算法,也可以看一下和现在的区别python实现快速排序 – Mr-Yang - 博客园 (cnblogs.com)</a>。</p> <p>在看快速排序之前,要先了解一下递归,对于递归我之前的文章中也有提到<a href="https://www.cnblogs.com/XiaoYang-sir/p/14714877.html">python递归函数 - Mr-Yang – 博客园 (cnblogs.com),在这里我补充一个关于递归的一个点:基线条件和递归条件

一、基线条件和递归条件

因为递归函数调用自身,所以在编写这样的函数时很容易出错,导致无限循环。以下是一些例子:

[En]

Because recursive functions call themselves, it is easy to make mistakes when writing such a function, resulting in an infinite loop. Examples are as follows:

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

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

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

def countdown(i):
    print(i)
    if i

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

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

二、快速排序

因为最简单的排序方法是空列表或只包含一个元素的列表,所以可以将基线条件设置为空或只包含一个元素,在这种情况下,您只需要返回到原始列表。

[En]

Because the simplest thing for sorting is an empty list, or a list containing only one element, you can set the baseline condition to empty or contain only one element, in which case you only need to return to the original list.

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

思路如下图所示:

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

代码如下:

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

作者:Mr-Yang

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

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

Original: https://www.cnblogs.com/XiaoYang-sir/p/16425804.html
Author: Mr-Yang`
Title: 8行代码实现快速排序,简单易懂图解!

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/499183/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球