「@Author：Runsen」
❝程式設計的本質來源于算法，而算法的本質來源于數學，程式設計隻不過将數學題進行代碼化。「---- Runsen」
❞
快速排序
不久前，我在牛客中看到這樣一個笑話，面試官讓他寫一個快速排序，結果他寫了一個冒泡排序，雖說不是計算機專業的，還一直說沒有寫錯，都不知道面試官為什麼這麼PASS。其實，一共有十大排序算法，最快最穩定的就是快速排序，簡稱快排。
quicksort 可以說是應用最廣泛的排序算法之一，它的基本思想是分治法。基礎的快速排序算法思想很簡單，核心就是一句話：找到基準值的位置。
具體的過程其實和把大象裝進冰箱這個問題一樣，都可以分成三步：
「第一步，選擇一個值作為基準值。」
「第二步，找到基準值的位置，并将小于基準值的元素放在基準值的前面，大于基準值的元素放在基準值的後面。」
「第三步，對基準值的左右兩側遞歸地進行這個過程。」
以
arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ]
為例，選擇一個支點,
index= (L+R)/2 = (0+7)/2=3
, 支點的值
pivot = arr[index] = arr[3] = 6
，接下來需要把
arr
中小于
6
的移到左邊，大于
6
的移到右邊，最後然後對基準值的左右兩側遞歸地進行這個過程。
快速排序最好用遞歸的代碼實作，代碼簡單可讀性前。
def quick_sort(b):
"""快速排序"""
if len(b) < 2:
return arr
# 選取基準，随便選哪個都可以，選中間的便于了解
mid = arr[len(b) // 2]
# 定義基準值左右兩個數列
left, right = [], []
# 從原始數組中移除基準值
b.remove(mid)
for item in b:
# 大于基準值放右邊
if item >= mid:
right.append(item)
else:
# 小于基準值放左邊
left.append(item)
return quick_sort(left) + [mid] + quick_sort(right)
def quicksort(array):
if len(array) < 2:
# 基本情況下，具有0或1個元素的數組是已經“排序”的
return array
else:
# 基準選取不同
pivot = array[0]
# 小于基準值的所有元素的子數組
less = [i for i in array[1:] if i <= pivot]
# 大于基準值的所有元素的子數組
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
複制
快排優化
快排優化的方法就是：「合理選擇pivot。」。我們知道，如果基準值選取不合理的話，快速排序的時間複雜度有可能達到
O(n^2)
這個量級，也就是退化成和選擇排序、插入排序等算法一樣的時間複雜度。隻有當基準值每次都能将排序區間中的資料平分時，時間複雜度才是最好情況下的
O(nlogn)
。
關于基準值選取的一個優化政策，「三點取中法。」
謂三點取中法，就是每一輪取排序區間的
頭、尾和中間
元素這三個值，然後把它們排序以後的中間值作為本輪的基準值。調整要選取的這三個值的位置。
我們就以上圖為例，假設本輪的三個值分别為 2、9、7，中間值是 7，是以，本輪的基準值就是 7。
快排優化：「更快地分區」。快速排序的做法是從左向右依次與 pivot 比較，做交換，這樣做其實效率并不高。
舉個簡單的例子，一個數組
[2, 1, 3, 1, 3, 1, 3]
，選第一個元素作為 pivot 是2，每次發現比2小的數會引起一次交換，一共三次。
然而，直覺來說，其實隻要将第一個3和最後一個1交換就可以達到這三次交換的效果。是以更理想的分區方式是從「兩邊向中間周遊」的雙向分區方式，而不是從左到右，當然前提是基準值選擇數組的中位數。
具體快速排序優化的代碼如下所示。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公衆号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/12/21
'''
def quick_sort(nums, start, end):
if start >= end:
return
pivot = nums[start] # 基準值
low = start # 左指針
high = end # 右指針
while low < high:
while low < high and nums[high] >= pivot:
high -= 1
nums[low] = nums[high]
while low < high and nums[low] < pivot:
low += 1
nums[high] = nums[low]
nums[low] = pivot
quick_sort(nums, start, low - 1)
quick_sort(nums, low + 1, end)
if __name__ == '__main__':
nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(nums, 0, len(nums) - 1)
print(nums)
複制
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大資料最快的排序算法之一了，而且Python内置的
sorted
就是快速排序。
雖然 Worst Case 的時間複雜度達到了
O(n²)
，比如說順序數列的快排。但是就是優秀，在大多數情況下都比平均時間複雜度為
O(n logn)
的排序算法表現要更好，，比複雜度穩定等于
O(nlogn)
的歸并排序要小很多。是以，對絕大多數順序性較弱的随機數列而言，快速排序總是優于歸并排序。
❝本文已收錄 GitHub，傳送門~[1] ，裡面更有大廠面試完整考點，歡迎 Star。
❞
Reference
[1]傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -