python算法(四)快速排序

快速排序

目標(biāo): 將一組亂序的數(shù)列,按從小到大(從大到小)的順序排列.
方法:
快速排序的邏輯是:
先從這一組數(shù)中,隨便找一個(gè)數(shù)作為基準(zhǔn)
然后對(duì)其他的數(shù)進(jìn)行分類(lèi),大于基準(zhǔn)的分成一組,小于基準(zhǔn)的分成一組.
然后對(duì)分好的兩組重新按上面的方法進(jìn)行分組,直到每一個(gè)組只有一個(gè)元素,則排序完成

示意圖:
例題數(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
然后加回來(lái):
1 2 5 6 7 8 9

python實(shí)現(xiàn)

# coding: utf-8
# 作者:愛(ài)編程的章老師
# 創(chuàng)建:2021/1/30 10:04 下午 
# 郵箱:slxxf000@163.com
# 微信:slxxfl
# 微信公眾號(hào):A衛(wèi)隆少兒編程
# 格言:給自己的生活增加一份向上的力，每都進(jìn)步一點(diǎn)點(diǎn)

from random import shuffle

"""快速排序算法"""
def quick_sort(num_list: list):
    """num_list:要排序的原始數(shù)列"""
    # 如果要排序的列表只有一個(gè)元素或者沒(méi)有元素,直接返回
    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é)果


# 生成一個(gè)一百個(gè)數(shù)的數(shù)列
num_list_demo = [x for x in range(100)]
# 打亂這個(gè)數(shù)列,形成一個(gè)測(cè)試用例
shuffle(num_list_demo)
print("排序前的數(shù)列:", num_list_demo)
print("排序后的數(shù)列:", quick_sort(num_list_demo))