## 快速排序 快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 步驟為： 1. 從數列中挑出一個元素，稱為"基準"（pivot）， 2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。 3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。 遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。 ## 快速排序的分析  ~~~ def quick_sort(alist, start, end): """快速排序""" # 遞歸的退出條件 if start >= end: return # 設定起始元素為要尋找位置的基準元素 mid = alist[start] # low為序列左邊的由左向右移動的游標 low = start # high為序列右邊的由右向左移動的游標 high = end while low < high: # 如果low與high未重合，high指向的元素不比基準元素小，則high向左移動 while low < high and alist[high] >= mid: high -= 1 # 將high指向的元素放到low的位置上 alist[low] = alist[high] # 如果low與high未重合，low指向的元素比基準元素小，則low向右移動 while low < high and alist[low] < mid: low += 1 # 將low指向的元素放到high的位置上 alist[high] = alist[low] # 退出循環后，low與high重合，此時所指位置為基準元素的正確位置 # 將基準元素放到該位置 alist[low] = mid # 對基準元素左邊的子序列進行快速排序 quick_sort(alist, start, low-1) # 對基準元素右邊的子序列進行快速排序 quick_sort(alist, low+1, end) alist = [54,26,93,17,77,31,44,55,20] quick_sort(alist,0,len(alist)-1) print(alist) ~~~ ## 時間復雜度 * 最優時間復雜度：O(nlogn) * 最壞時間復雜度：O(n2) * 穩定性：不穩定 從一開始快速排序平均需要花費O(n log n)時間的描述并不明顯。但是不難觀察到的是分區運算，數組的元素都會在每次循環中走訪過一次，使用O(n)的時間。在使用結合（concatenation）的版本中，這項運算也是O(n)。 在最好的情況，每次我們運行一次分區，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞歸調用處理一半大小的數列。因此，在到達大小為一的數列前，我們只要作log n次嵌套的調用。這個意思就是調用樹的深度是O(log n)。但是在同一層次結構的兩個程序調用中，不會處理到原來數列的相同部分；因此，程序調用的每一層次結構總共全部僅需要O(n)的時間（每個調用有某些共同的額外耗費，但是因為在每一層次結構僅僅只有O(n)個調用，這些被歸納在O(n)系數中）。結果是這個算法僅需使用O(n log n)時間。 ## 快速排序演示