快速排序是一種常用的排序演算法，其時間複雜度為 O(nlogn)。在實際應用中，快速排序通常比其他排序演算法快得多。 Python 提供了許多內建的排序函數，但了解和實作快速排序仍然很重要。在本文中，我們將透過 Python 實作快速排序演算法。
快速排序的工作原理是選定一個基準值（pivot），然後將清單中所有小於基準值的元素放在一個子清單中，將所有大於基準值的元素放在另一個子列表中。然後對這兩個子列表遞歸進行快速排序。最終，所有子列表都將被遞歸排序，然後合併成一個排好序的清單。
以下是用 Python 實作快速排序的程式碼：
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)
在上面的程式碼中，我們先檢查列表的長度。如果列表長度小於 2，我們就回傳原始列表。否則，我們選擇清單的第一個元素作為基準值（pivot）。然後，我們使用清單推導式將小於等於基準值的元素放入一個清單中，並將大於基準值的元素放入另一個清單中。接下來，我們遞歸將較小和較大的清單進行排序，並將排好序的清單連接在一起，基準值置於連接的清單中間。
這個演算法需要選擇一個合適的基準數。如果選擇的基準數恰好是清單中的最大（或最小）值，那麼遞歸排序的子清單大小只減少了 1。在這種情況下，快速排序演算法的時間複雜度可能會退化為 O(n2)。為了避免這種情況，我們可以使用隨機選取基準值的方法。這個方法在基準值不是清單中的最大（或最小）值的情況下，平均地保證了遞歸排序的子清單大小。
以下是使用隨機選擇基準值的 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() 函數隨機選擇一個基準值。然後，我們將小於等於基準值的元素放入一個清單中，並將大於基準值的元素放入另一個清單中，這與前面那個實作方法是類似的。
總結一下，我們透過 Python 實作了快速排序演算法，並使用隨機選擇基準值的方法避免了遞歸排序的子清單的大小不均衡的情況。這個演算法是基於分治（Divide and Conquer）思想的，它能夠在平均情況下以 O(nlogn) 的時間複雜度快速對列表進行排序。
以上是用Python實現快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
