用Python如何理解快速排序算法

這篇文章將為大家詳細講解有關用Python如何理解快速排序算法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

快速排序作為我們經常在數據結構面試中見到的算法，我們對它的理解和掌握是非常重要的，下面我用一段簡單的步驟描述圖解以及代碼描述來帶大家快速的理解它。

快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort）。

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

步驟為：

1，從數列中挑出一個元素，稱為"基準"（pivot），

2，重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

3，遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

import random
def quick_sort(alist,start,end):
    if start>end:
        return
    # 如果前值大于后值則排序停止   此時low指針和high指針重合
    low = start
    high = end
 
    middle = alist[start]
    # middle 是我們開始時定的基準的值而low和high表示指針的位置
 
    while low < high:
        while low < high and alist[high] >= middle:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] <= middle:
            low += 1
        alist[high] = alist[low]
        # 當退出循環的時候，證明low指針指向的數據有大于基準middle的，所以講這個大于middle的數和high的位置進行交換
    alist[low] = middle
    # 推出循環之后，low和high的位置重合，此時這個重合的位置就是middle元素應該在的位置，此時將middle放置此處，一次大循環結束
    quick_sort(alist, start, low-1)
    quick_sort(alist, low+1,end)
list1=[]
# 用生成隨機數的方法去驗證我們的排序算法
for i in range(30):
    list1.append(random.randint(1, 300))
quick_sort(list1, 0, len(list1)-1)
print(list1)

時間復雜度

最優時間復雜度：O(nlogn)

最壞時間復雜度：O(n2)

穩定性：不穩定

從一開始快速排序平均需要花費O(n log n)時間的描述并不明顯。但是不難觀察到的是分區運算，數組的元素都會在每次循環中走過一次，使用O(n)的時間。在使用結合的版本中，這項運算也是O(n)。

在最好的情況，每次我們運行一次分區，我們會把一個數列分為兩個幾近相等的片段。

這個意思就是每次遞歸調用處理一半大小的數列。

因此，在到達大小為一的數列前，我們只要作log n次嵌套的調用。

這個意思就是調用樹的深度是O(log n)。

但是在同一層次結構的兩個程序調用中，不會處理到原來數列的相同部分；因此，程序調用的每一層次結構總共全部僅需要O(n)的時間（每個調用有某些共同的額外耗費，但是因為在每一層次結構僅僅只有O(n)個調用，這些被歸納在O(n)系數中）。

結果是這個算法僅需使用O(n log n)時間。

關于用Python如何理解快速排序算法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。