快速排序是一種常用的排序算法，其時(shí)間復(fù)雜度為 o(nlogn)。在實(shí)際應(yīng)用中，快速排序通常比其他排序算法快得多。python 提供了許多內(nèi)置的排序函數(shù)，但了解和實(shí)現(xiàn)快速排序仍然很重要。在本文中，我們將通過(guò) python 實(shí)現(xiàn)快速排序算法。

快速排序的工作原理是選定一個(gè)基準(zhǔn)值（pivot），然后將列表中所有小于基準(zhǔn)值的元素放在一個(gè)子列表中，將所有大于基準(zhǔn)值的元素放在另一個(gè)子列表中。然后對(duì)這兩個(gè)子列表遞歸進(jìn)行快速排序。最終，所有子列表都將被遞歸排序，然后合并成一個(gè)排好序的列表。

以下是用 Python 實(shí)現(xiàn)快速排序的代碼：

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

在上面的代碼中，我們首先檢查列表的長(zhǎng)度。如果列表長(zhǎng)度小于 2，我們就返回原列表。否則，我們選擇列表的第一個(gè)元素作為基準(zhǔn)值（pivot）。然后，我們使用列表推導(dǎo)式將小于等于基準(zhǔn)值的元素放入一個(gè)列表中，并將大于基準(zhǔn)值的元素放入另一個(gè)列表中。接下來(lái)，我們遞歸將較小和較大的列表進(jìn)行排序，并將排好序的列表連接在一起，基準(zhǔn)值置于連接的列表中間。

這個(gè)算法需要選擇一個(gè)合適的基準(zhǔn)數(shù)。如果選擇的基準(zhǔn)數(shù)恰好是列表中的最大（或最?。┲?，那么遞歸排序的子列表大小只減少了 1。這種情況下，快速排序算法的時(shí)間復(fù)雜度可能會(huì)退化為 O(n2)。為了避免這種情況，我們可以使用隨機(jī)選取基準(zhǔn)值的方法。這個(gè)方法在基準(zhǔn)值不是列表中的最大（或最?。┲档那闆r下，平均地保證了遞歸排序的子列表大小。

立即學(xué)習(xí)“Python免費(fèi)學(xué)習(xí)筆記（深入）”；

簡(jiǎn)篇AI排版

AI排版工具，上傳圖文素材，秒出專(zhuān)業(yè)效果！

134

查看詳情

以下是使用隨機(jī)選擇基準(zhǔn)值的 Python 代碼：

import random

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot]
        greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

在上面的代碼中，我們先使用 random.randint() 函數(shù)隨機(jī)選擇一個(gè)基準(zhǔn)值。然后，我們將小于等于基準(zhǔn)值的元素放入一個(gè)列表中，并將大于基準(zhǔn)值的元素放入另一個(gè)列表中，這與前面那個(gè)實(shí)現(xiàn)方法是類(lèi)似的。

總結(jié)一下，我們通過(guò) Python 實(shí)現(xiàn)了快速排序算法，并使用隨機(jī)選擇基準(zhǔn)值的方法避免了遞歸排序的子列表的大小不均衡的情況。這個(gè)算法是基于分治（Divide and Conquer）思想的，它能夠在平均情況下以 O(nlogn) 的時(shí)間復(fù)雜度快速對(duì)列表進(jìn)行排序。

以上就是用Python實(shí)現(xiàn)快速排序的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注php中文網(wǎng)其它相關(guān)文章！