python算法(四)快速排序
快速排序
目标: 将一组乱序的数列,按从小到大(从大到小)的顺序排列.
方法:
快速排序的逻辑是:
先从这一组数中,随便找一个数作为基准
然后对其他的数进行分类,大于基准的分成一组,小于基准的分成一组.
然后对分好的两组重新按上面的方法进行分组,直到每一个组只有一个元素,则排序完成
示意图:
例题数组: 1 5 7 3 2 8 6 9
比如,我用7作为基准
1<7 加入左侧, 5<7加入左侧, 3<7加入左侧,2<7加入左侧,8<7加入右侧, 6<7加入左侧, 9>7加入右侧
第一轮:的结果
左侧:1 5 3 2 6 右侧 8 9 基本7
第二轮: 左侧如果用3作基准, 右侧用 8 作基准
1<3 加入左侧, 5>3 加入右侧, 2<3加入左侧, 6>3 加入右内里
9>8 加入右侧,左侧为空
第二轮结果
左侧: 左边:1 2 右边: 5 6 基准:3 右侧: 左边[] 右边: 9 基准:8
第三轮:
1 [] 基准 2 5 [] 基准 6
然后加回来:
1 2 5 6 7 8 9
python实现
# coding: utf-8
# 作者:爱编程的章老师
# 创建:2021/1/30 10:04 下午
# 邮箱:slxxf000@163.com
# 微信:slxxfl
# 微信公众号:A卫隆少儿编程
# 格言:给自己的生活增加一份向上的力，每都进步一点点
from random import shuffle
"""快速排序算法"""
def quick_sort(num_list: list):
"""num_list:要排序的原始数列"""
# 如果要排序的列表只有一个元素或者没有元素,直接返回
if len(num_list) == 1 or len(num_list) == 0:
return num_list
temp = num_list[-1] # 基准数
left = [] # 左侧列表
right = [] # 右侧列表
for i in range(len(num_list) - 1):
if num_list[i] < temp:
left.append(num_list[i])
else:
right.append(num_list[i])
left = quick_sort(left)
right = quick_sort(right)
return left + [temp] + right # 将左侧与基准与右侧重新拼接成最终结果
# 生成一个一百个数的数列
num_list_demo = [x for x in range(100)]
# 打乱这个数列,形成一个测试用例
shuffle(num_list_demo)
print("排序前的数列:", num_list_demo)
print("排序后的数列:", quick_sort(num_list_demo))
