python算法(四)快速排序
快速排序
目標(biāo): 將一組亂序的數(shù)列,按從小到大(從大到小)的順序排列.
方法:
快速排序的邏輯是:
先從這一組數(shù)中,隨便找一個數(shù)作為基準(zhǔn)
然后對其他的數(shù)進(jìn)行分類,大于基準(zhǔn)的分成一組,小于基準(zhǔn)的分成一組.
然后對分好的兩組重新按上面的方法進(jìn)行分組,直到每一個組只有一個元素,則排序完成
示意圖:
例題數(shù)組: 1 5 7 3 2 8 6 9
比如,我用7作為基準(zhǔn)
1<7 加入左側(cè), 5<7加入左側(cè), 3<7加入左側(cè),2<7加入左側(cè),8<7加入右側(cè), 6<7加入左側(cè), 9>7加入右側(cè)
第一輪:的結(jié)果
左側(cè):1 5 3 2 6 右側(cè) 8 9 基本7
第二輪: 左側(cè)如果用3作基準(zhǔn), 右側(cè)用 8 作基準(zhǔn)
1<3 加入左側(cè), 5>3 加入右側(cè), 2<3加入左側(cè), 6>3 加入右內(nèi)里
9>8 加入右側(cè),左側(cè)為空
第二輪結(jié)果
左側(cè): 左邊:1 2 右邊: 5 6 基準(zhǔn):3 右側(cè): 左邊[] 右邊: 9 基準(zhǔn):8
第三輪:
1 [] 基準(zhǔn) 2 5 [] 基準(zhǔn) 6
然后加回來:
1 2 5 6 7 8 9
python實現(xiàn)
# coding: utf-8
# 作者:愛編程的章老師
# 創(chuàng)建:2021/1/30 10:04 下午
# 郵箱:slxxf000@163.com
# 微信:slxxfl
# 微信公眾號:A衛(wèi)隆少兒編程
# 格言:給自己的生活增加一份向上的力狞谱，每都進(jìn)步一點(diǎn)點(diǎn)
from random import shuffle
"""快速排序算法"""
def quick_sort(num_list: list):
"""num_list:要排序的原始數(shù)列"""
# 如果要排序的列表只有一個元素或者沒有元素,直接返回
if len(num_list) == 1 or len(num_list) == 0:
return num_list
temp = num_list[-1] # 基準(zhǔn)數(shù)
left = [] # 左側(cè)列表
right = [] # 右側(cè)列表
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 # 將左側(cè)與基準(zhǔn)與右側(cè)重新拼接成最終結(jié)果
# 生成一個一百個數(shù)的數(shù)列
num_list_demo = [x for x in range(100)]
# 打亂這個數(shù)列,形成一個測試用例
shuffle(num_list_demo)
print("排序前的數(shù)列:", num_list_demo)
print("排序后的數(shù)列:", quick_sort(num_list_demo))
