文章目錄
- 一、快速排序簡介
- 二、快速排序可視化
- 三、快速排序實作
- 1. 鍊式隊列實作快速排序
- 2. 快速排序時間複雜度分析
- 2.1 最壞時間複雜度
- 2.2 最好時間複雜度
- 2.3 平均時間複雜度
- 四、快速排序其他實作
- 1. 雙端隊列實作快速排序
同【常見算法Python描述】基于分治思想的歸并排序簡介與實作中的歸并排序一樣，快速排序是分治思想的另一個典型應用。
一、快速排序簡介
假設給定具有 n n n個元素的序列 s s s，則對其應用快速排序算法的步驟可以大緻分為以下幾步：
- 分：如果序列 s s s僅有0個或1個元素，因為序列已有序，則直接傳回 s s s即可；否則（序列至少有2個元素），首先從序列 s s s中選擇出一個特定的元素 x x x，且稱其為基準值，通常會将序列 s s s的第一個或最後一個元素選為基準值；然後将序列 s s s中所有元素移動至三個子序列中：
- l t lt lt：儲存序列 s s s中所有小于 x x x的元素；
- e q eq eq：儲存序列 s s s中所有等于 x x x的元素；
- g t gt gt：儲存序列 s s s中所有大于 x x x的元素；
- 治：對 l t lt lt和 g t gt gt進行遞歸排序；
- 合：按照 l t lt lt、 e q eq eq和 g t gt gt的順序将其中的元素放回原序列 s s s中。
二、快速排序可視化
為便于讀者了解，同歸并排序一樣，我們也可以通過一個二叉樹來描述快速排序的具體過程，即一個節點代表一次遞歸處理，輸入為待排序的子序列，輸出為該子序列的已排序形式，類似地我們将其稱為快速排序樹。
同樣地，對于一個具有8個元素的待排序列，下面先從總體上給出任意節點遞歸調用傳回前後所代表的序列狀态，然後給出快速排序每一步的具體過程。
對于上圖，需要說明的是，圖(a)表示了每個節點輸入的待排（子）序列，圖(b)表示每個節點所代表的遞歸調用傳回後産生的已排序子序列，其中所有粗體的均為基準值。
下面給出快速排序的詳細步驟，且同樣對圖例作如下約定：
- 虛線節點表示目前還未發生遞歸調用；
- 粗實線節點表示目前正在進行遞歸調用；
- 細實線空節點表示遞歸調用已傳回；
- 其他節點表示等待遞歸調用傳回。
三、快速排序實作
1. 鍊式隊列實作快速排序
下面給出了當待排序的序列為鍊式結構的隊列時，對其使用快速排序的代碼實作，其中：
- 選擇隊頭元素作為基準值
pivot
- 根據待排序列 s s s的元素和基準值
pivot
class Empty(Exception):
"""嘗試對空隊列進行删除操作時抛出的異常"""
pass
class _Node:
"""節點類"""
def __init__(self, element, next=None):
"""
:param element: 節點代表的對象元素
:param next: 節點對象中用于指向下一個節點的執行個體屬性
"""
self.element = element
self.next = next
class LinkedQueue:
"""使用單連結清單儲存對象元素實作的隊列資料結構"""
def __init__(self):
"""建立一個空隊列"""
self._head = None # 初始化頭節點
self._tail = None # 初始化尾節點
self._size = 0 # 隊列元素個數
def __len__(self):
"""
傳回隊列中的元素個數
:return: 元素個數
"""
return self._size
def is_empty(self):
"""
如果隊列為空則傳回True
:return: 隊列是否為空的狀态
"""
return self._size == 0
def first(self):
"""
傳回但不删除隊頭元素
:return: 隊頭元素
"""
if self.is_empty():
raise Empty('目前隊列為空！')
return self._head.element
def enqueue(self, element):
"""
向隊列尾部插入對象元素
:param element: 待插入隊列尾部的對象元素
:return: None
"""
node = _Node(element)
if self.is_empty():
self._head = node
else:
self._tail.next = node
self._tail = node # 使新入隊尾的元素成為尾節點
self._size += 1
def dequeue(self):
"""
删除并傳回隊頭的節點，并傳回其中的對象元素，如此時隊列為空則抛出異常
:return: 隊頭節點的element域
"""
if self.is_empty():
raise Empty('隊列為空！')
ans = self._head.element
self._head = self._head.next
self._size -= 1
if self.is_empty(): # 如果執行本次出對操作時隊列中僅有一個節點，則此時該節點同時也是尾節點，需對此做處理
self._tail = None
return ans
def quick_sort(s: LinkedQueue):
"""Sort the elements of queue S using the quick-sort algorithm."""
num = len(s)
if num < 2:
return # 序列已有序
# 分——divide
pivot = s.first() # 使用隊頭元素作為基準值
lt = LinkedQueue()
eq = LinkedQueue()
gt = LinkedQueue()
while not s.is_empty(): # 将序列s分為lt、eq和gt三個部分
if s.first() < pivot:
lt.enqueue(s.dequeue())
elif s.first() > pivot:
gt.enqueue(s.dequeue())
else:
eq.enqueue(s.dequeue())
# 治——conquer
quick_sort(lt)
quick_sort(gt)
# 合——concatenate
while not lt.is_empty():
s.enqueue(lt.dequeue())
while not eq.is_empty():
s.enqueue(eq.dequeue())
while not gt.is_empty():
s.enqueue(gt.dequeue())
2. 快速排序時間複雜度分析
快速排序的時間複雜度取決于每次遞歸時劃分得到的兩個子序列是否元素個數相對均等，而這又在很大程度上取決于使用哪一個元素（或哪幾個元素）作為基準值。如果劃分得到的兩個子序列個數相對均等，那麼快速排序的效率基本和歸并排序一樣高；否則效率和插入排序相近。
2.1 最壞時間複雜度
當第 1 1 1次遞歸調用時，元素個數為 n n n的待排序列被分為個數分别為 n − 1 n-1 n−1和 0 0 0的兩個子序列，第 2 2 2次被劃分為個數分别為 n − 2 n-2 n−2和 0 0 0的兩個子序列，第 3 3 3次被劃分為個數分别為 n − 3 n-3 n−3和 0 0 0的兩個子序列，以此類推，此時将導緻快速排序的最壞時間複雜度。
假設對元素個數為 n n n的待排序列使用快速排序的時間複雜度為 T ( n ) T(n) T(n)，此時有如下遞歸公式：
T ( n ) = T ( n − 1 ) + Θ ( n ) T(n)=T(n-1)+{\Theta(n)} T(n)=T(n−1)+Θ(n)
其中 Θ ( n ) \Theta(n) Θ(n)表示對待排序列第一次調用快速排序算法的時間複雜度，顯然有 T ( 1 ) = Θ ( 1 ) T(1)=\Theta(1) T(1)=Θ(1)，利用高中數學知識可得 T ( n ) = Θ ( n 2 ) T(n)={\Theta(n^2)} T(n)=Θ(n2)。
實際上，對于固定選取待排（子）序列的第一個或最後一個元素作為基準值時，當待排序列已完全有序時，快速排序的最壞時間複雜度發生。
2.2 最好時間複雜度
如前所述，最好的情況下，每次遞歸劃分得到的兩個子序列的元素個數均不超過 n / 2 n/2 n/2，此時快速排序的時間複雜度遞歸公式如下：
T ( n ) = 2 T ( n / 2 ) + Θ ( n ) T(n)=2T(n/2)+{\Theta(n)} T(n)=2T(n/2)+Θ(n)
為避免繁瑣的數學證明，下面通過圖示的方式來得出 T ( n ) T(n) T(n)的結果為 Θ ( n l g n ) \Theta(nlgn) Θ(nlgn)，為進一步簡化，我們假定 n n n是 2 2 2的整數次幂， c c c代表既當 n = 1 n=1 n=1時使用進行快速排序所需時間即 T ( 1 ) = c T(1)=c T(1)=c，也代表對待排（子）序列中每個元素進行分與合所需的時間。1
具體地，首先我們通過遞歸公式展開得到下列的遞歸樹：
- 從圖 ( a ) (a) (a)到圖 ( b ) (b) (b)表示用使用上述遞歸公式對 T ( n ) T(n) T(n)進行展開；
- 從圖 ( b ) (b) (b)到圖 ( c ) (c) (c)表示用使用上述遞歸公式繼續對 T ( n / 2 ) T(n/2) T(n/2)進行展開;
- 從圖 ( c ) (c) (c)到圖 ( d ) (d) (d)表示繼續使用上述遞歸公式進行展開，直到最後一層每一個節點都代表 T ( 1 ) = c T(1)=c T(1)=c。
然後，我們計算圖 ( d ) (d) (d)中每一層所需的時間成本，其中：
- 第 0 0 0所需時間成本為 c n cn cn；
- 第 1 1 1層所需時間成本為 c ( n / 2 ) + c ( n / 2 ) = c n c(n/2)+c(n/2)=cn c(n/2)+c(n/2)=cn；
- 第 2 2 2層所需時間成本為 c ( n / 4 ) + c ( n / 4 ) + c ( n / 4 ) + c ( n / 4 ) = c n c(n/4)+c(n/4)+c(n/4)+c(n/4)=cn c(n/4)+c(n/4)+c(n/4)+c(n/4)=cn；
- 一般地，第 i i i層有 2 i 2^i 2i個節點，每個節點處所需時間成本為 c ( n / 2 i ) c(n/2^i) c(n/2i)，是以第 i i i總共所需時間成本為 2 i c ( n / 2 i ) = c n 2^i{c(n/2^i)}=cn 2ic(n/2i)=cn；
- 最底層有 n n n個節點，每個點所需時間成本為 c c c，是以該層總共所需時間時間成本為 c n cn cn。
顯然，上述遞歸樹的共有 l g n + 1 lgn+1 lgn+1層，每層都需 c n cn cn的時間成本，是以總體時間成本為 c n ( l g n + 1 ) = c n l g n + c n cn(lgn+1)=cnlgn+cn cn(lgn+1)=cnlgn+cn，忽略低階項和常數項，可得 T ( n ) = Θ ( n l g n ) T(n)={\Theta}(nlgn) T(n)=Θ(nlgn)。
2.3 平均時間複雜度
相較于最壞時間複雜度，快速排序的平均時間複雜度更接近其最好時間複雜度，下面假設每次遞歸調用都将待排（子）序列劃分為元素個數比為 9 : 1 9:1 9:1的兩個子序列，然後使用類似上述的方式證明此時 T ( n ) = O ( n l g n ) T(n)=O(nlgn) T(n)=O(nlgn)。
首先，易得此時快速排序的時間複雜度遞歸公式為：
T ( n ) = T ( 9 n / 10 ) + T ( n / 10 ) + Θ ( n ) T(n)=T(9n/10)+T(n/10)+\Theta(n) T(n)=T(9n/10)+T(n/10)+Θ(n)
下圖表示了按照上述公式對 T ( n ) T(n) T(n)進行展開後得到的遞歸樹，由圖中易得，在到達深度為 ( l o g 10 n ) = Θ ( l g n ) (log_{10}n)=\Theta(lgn) (log10n)=Θ(lgn)及之前，每一層所需時間成本為 c n cn cn，之後每一層所需時間成本均小于 c n cn cn，而遞歸在到達深度為 l o g 10 / 9 n = Θ ( l g n ) log_{10/9}n=\Theta(lgn) log10/9n=Θ(lgn)時結束，是以 T ( n ) = O ( n l g n ) T(n)=O(nlgn) T(n)=O(nlgn)。
四、快速排序其他實作
1. 雙端隊列實作快速排序
本文前面給出的快速排序算法實作假定待排序列是我們自己實作的
LinkedQueue
類，而Python的
collections
子產品中内置了一個雙端隊列資料結構
deque
，我們可以将其用作一個普通隊列，然後對其中的所有元素使用快速排序算法，具體實作如下：
from collections import deque
def quick_sort(s: deque):
"""對序列s使用快速排序算法進行排序"""
num = len(s)
if num < 2:
return
pivot = s[-1]
lt = deque()
eq = deque()
gt = deque()
while len(s) != 0:
if s[0] < pivot:
lt.append(s.popleft())
elif s[0] > pivot:
gt.append(s.popleft())
else:
eq.append(s.popleft())
quick_sort(lt)
quick_sort(gt)
while len(lt) != 0:
s.append(lt.popleft())
while len(eq) != 0:
s.append(eq.popleft())
while len(gt) != 0:
s.append(gt.popleft())
if __name__ == '__main__':
lst = [8, 3, 6, 1, 7, 4, 5, 10, 2, 9, 13, 18, 14, 20, 23, 19, 12]
s = deque(lst)
print(s) # deque([8, 3, 6, 1, 7, 4, 5, 10, 2, 9, 13, 18, 14, 20, 23, 19, 12])
quick_sort(s)
print(list(s)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 23]
上述實作的優點在于隻要待排序列是可疊代對象（如：
list
、
tuple
），均可以先将其轉化為
deque
對象然後應用上述
quick_sort
函數進行排序。
- 由于這兩種時間基本不可能相等，這裡簡便起見取二者較大值作為 c c c。 ↩︎