概念
快速排序（Quick sort）是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。我們可以從名字就可以看出快速排序存在的意義就在於：快，而且效率高，它是處理大數據最快的排序算法之一。快速排序同樣也是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
算法步驟：
快速排序使用分治法（Divide and conquer）策略來把一個序列（sequence）分為兩個子序列（Sub-sequence）。
首先從未排序序列中挑出一個元素（通常為了方便，都是用第一個元素），稱為 「基準」（pivot）。
然後以這個基準值將序列重新排序，比基準值小的擺放在基準的前面，比基準大的擺放在基準的後面（相同的數可以到任意一邊，這也就是說快速排序是不穩定排序），一輪結束之後該基準數也就歸位了。
通過上面步驟我們已經將序列分為兩個子序列，然後對左邊和右邊的子序列重複上述步驟，直到所有基準值全部歸位排序完成。
算法圖解：
Array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]如何將基準值歸位步驟圖解：（這裡用以3為基準的情況）
首先快速排序是冒泡排序的一種升級版，在前面我們介紹了冒泡排序是相鄰兩個元素進行比較，較大的元素向後移；很明顯這種方式是較為浪費時間的。
而快速排序是設置兩個指針（i，j）以及一個基準值，分別指向要排序序列的頭部（i）和尾部（j），從兩端開始進行對比，每次先通過 j 從右向左尋找小於基準值的元素，再通過 i 從左向右尋找大於基準值的元素，找到之後兩個值進行交換，然後繼續尋找，繼續交換；直到兩個指針相遇，將基準值和當前位置的值進行交換，結束本輪交換。算法實現：
def quick_Sort(arr, left=None, right=None):
left = 0 if not isinstance(left, (int, float)) else left
right = len(arr) - 1 if not isinstance(right, (int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quick_Sort(arr, left, partitionIndex - 1)
quick_Sort(arr, partitionIndex + 1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot + 1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index += 1
i += 1
swap(arr, pivot, index-1)
return index - 1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
Array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print("排序完成，最終返回結果為：", quick_Sort(Array))友情提示：可在 https://pythontutor.com/visualize.html#mode=edit 中可視化執行代碼。
關注公眾號，後續更精彩。