[Python知识库]计算机十大经典算法（python版）之快速排序法

计算机十大经典算法（python版）之快速排序法

个人理解：快速排序法是通过在整个数据源中选择基准数据，并通过递归方式以基准数据为块内数据大小分界点，将整块数据不断分割为一个个小数据块。再将小数据块作同样处理，最终达到排序目的的一种算法。

用到的知识：递归

递归算法百度网址：https://baike.baidu.com/item/%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95/4323575?fr=aladdin

上代码

# 目标数据生成
import random
l=[]
i=0
while i<30:
    l.append(random.randint(1,100))
    i+=1
print('排序目标：',l)

# 快速排序，每次递归以范围内最左边的为基准
def run(l,i=0,j=29):
    left=i
    right=j
    while True:
        if left==right:
            left-=1
            right+=1
            break
        # 范围内从右向左挑小于基准的
        for item in range(left,right):
            if l[left] < l[right]:
                l[right], l[left] = l[left], l[right]
            left+=1
        # 每变动一次都要检验，否则有一半的可能出现无限递归
        if left == right:
            left -= 1
            right += 1
            break
        # 范围内从左往右挑大于基准的
        for item in range(left,right):
            if l[left] > l[right]:
                l[right], l[left] = l[left], l[right]
            right -= 1
    # 向左递归
    if i < left:
        run(l,i,left)
    # 向右递归
    if j > right:
        run(l,j,right)
    return l

# 显示结果
print("排序结果：",ll)

我的运行结果

排序目标： [76, 71, 6, 100, 46, 55, 69, 18, 11, 3, 61, 44, 64, 67, 51, 25, 17, 92, 90, 60, 18, 40, 38, 86, 14, 85, 97, 27, 60, 44]
排序结果： [100, 97, 92, 90, 86, 85, 76, 71, 69, 67, 64, 61, 60, 60, 55, 51, 46, 44, 44, 40, 38, 27, 25, 18, 18, 17, 14, 11, 6, 3]