十大排序演算法（四）——- 快速排序
快速排序演算法採用的是分治法的思想（Divide and Conquer）， 它把一個待排序的陣列，以某個元素或者稱為基準（這裡記為PIVOT）為界，分為兩個子陣列，比PIVOT小的全部移到到PIVOT左邊，比PIVOT大的全部移動到PIVOT右邊。再分別對以PIVOT分開的兩個子陣列重複該過程，直到無法再分。
快速排序正常情況下時間複雜度為O（nlogn）。最壞情況下為O（n^2）。最壞情況發生在每次排序都需要移動所有剩下待排序的元素，這種情況雖然很少發生，但是為了避免這樣的情況可以採用隨機選擇PIVOT元素的方法來預防。下面描述演算法的實現步驟：
隨機的從待排序陣列中選擇一個元素作為PIVOT
將所有比PIVOT小的數放到PIVOT的左邊，比PIVOT大的數放到PIVOT的右邊。跟PIVOT一樣大的數，放到左右都可以。這個步驟稱為Partition。這樣以PVIOT為界分成了左右兩個子陣列。
對#2分成兩個子陣列遞迴進行#1~#3操作，直到排序完成。
假設我們要對A［5， 3， 6， 1， 2， 8］留個數進行排序，下圖展示了排序的過程。
快速排序過程展示
絕大多數情況下，快速排序是高效的，但是快速排序不是穩定的。下面是python的程式碼實現。有興趣的同學，也可以用其它程式語言嘗試實現一下。
import random
A = ［5， 3， 6， 1， 2， 8］
def quick_sorting（data， left， right）：
if left >= right ： return
mark = random。randint（left， right）
data［left］， data［mark］ = data［mark］， data［left］
mark = left
tmp = data［left］
for i in range（left+1， right+1）：
if data［i］ < tmp：
mark += 1
data［i］， data［mark］ = data［mark］， data［i］
data［left］， data［mark］ = data［mark］， data［left］
quick_sorting（data， left， mark-1）
quick_sorting（data， mark+1， right）
def main（）：
right=len（A）-1
left = 0
#Ascending
quick_sorting（A， left， right）
print（A）
if __name__==‘__main__’：
main（）
將上面的程式碼儲存到一個文字檔案，字尾名修改為。py。可以用python直譯器執行一下，會輸出如下結果：
可以看到，排序正確。
