这是《python算法教程》第9篇读书笔记，笔记的主要内容为快速排序法。

快速排序法简介

快速排序法运用分治法的方式，将需要排序的序列细分成小序列进行排序。
思路如下：将序列划分为大于序列第一个值、小于序列第一元素的两个序列，以及用于作为比较基准的序列的第一个元素。之后递归调用上述思路，将拆分出来的两个序列分别按照上述思路进行拆分，直到需要排序的序列剩下一个元素。之后将拆分的序列组合起来。

代码展示

以下展示快速排序的两种代码方案。
第一种是每次划分序列，均生成两个新的序列。
第二种则是通过调换元素间的顺序，以使得用于对比的基准元素的左边的元素均小于基准元素，基准元素右边的元素大于基准元素。

方案1

#快速排序
import numpy as np

def partition(seq):
    lo=[x for x in seq if x<seq[0]]
    hi=[x for x in seq if x>seq[0]]
    return lo ,seq[0],hi
    
def quickSort(seq):
    if len(seq)<=1:
        return seq
    lo,pi,hi=partition(seq)
    return quickSort(lo) + [pi] + quickSort(hi)

#生成随机整数序列，用于测试排序算法
seq=np.random.randint(0,100,100)
print(seq)
res=quickSort(seq)
print(res)

方案2

#快速排序
import numpy as np

def quickSort(seq):
    if len(seq)<=1:
        return seq
    i=0
    j=len(seq)-1
    k=seq[0]
    while i<j:
        while i<j and k<=seq[j]:
            j-=1
        seq[i],seq[j]=seq[j],seq[i]
        while i<j and k>=seq[i]:
            i+=1
        seq[i],seq[j]=seq[j],seq[i]
    #print(seq[0:i],seq[i+1:len(seq)])
    return quickSort(seq[0:i]) +[k]+quickSort(seq[i+1:len(seq)])

#生成随机整数序列，用于测试排序算法
seq=[x for x in np.random.randint(0,100,50)]
print(seq)
res=quickSort(seq)
print(res)

我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=11flspuoq5iwm