快速排序

今天我們來聊一聊無論是在筆試還是面試中常常考到的，也是最經典和最高效的快速排序算法。它的平均時間復雜度為 $O(NlogN)$，空間復雜度為 $O(1)$。

1. 快速排序算法原理

快速排序算法是基于這樣的思想：從待排序的列表選擇一個基準數，然后將列表中比該基準數大的放到該數的右邊，比該基準數小的值放到該基準數的左邊；接下來執行遞歸操作，對基準數左邊的待排序列表執行前面同樣的操作，直到左邊的列表有序，對于基準數右邊的待排序列表也執行前面同樣的操作，直到右邊的列表有序。此時，整個列表有序。即對于輸入的數組 nums[left:right]：

• 分解：以 nums[p] 為基準將 nums[left: right] 劃分為三部分: nums[left:p-1]，nums[p] 和 a[p+1:right]，使得 nums[left:p-1] 中任何一個元素小于等于 nums[p]， 而 nums[p+1:right] 中任何一個元素大于等于 nums[p]；
• 遞歸求解：通過遞歸調用快速排序算法分別對 nums[left:p -1] 和 nums[p+1:right] 進行排序；
• 合并：由于對 nums[left:p-1] 和 nums[p+1:right] 的排序是就地進行的，所以在 nums[left:p-1] 和 nums[p+1:right] 都已排好序后，不需要執行任何計算，nums[left:right] 就已經排好序了；

下面是算法示意圖：

2. 快速排序空間復雜度優化

可以看到，上述快速排序算法的一個核心步驟是：**將列表中的比基準數小的全部移動到基準數的左邊，其余數移動到基準數的右邊，且整個算法的過程不能使用額外的空間。**這樣的算法才比較高效，空間復雜度為 O(1)。那么怎么做到不使用額外空間達到這一目的呢？請看下面的示意圖進行理解。

可以看下快速排序動態圖的演示：

接下來，我們就要使用 Python 實現上面的核心步驟以及最后的快排算法。

3. 快速排序算法的 Python 實現

首先我們實現上面的核心步驟，代碼如下：

# 代碼位置：sort_algorithms.py

def get_num_position(nums, left, right):
    # 默認基準值為第一個
    base = nums[left]
    while left < right:
        # 從最右邊向左直到找到小于基準值的數
        while left < right and nums[right] >= base:
            right -= 1
        # 將小于基準數的值放到右邊，left原來位置放的是基準值(base)
        nums[left] = nums[right]
        # 然后從左邊往右遍歷，直到找到大于基準值的數
        while left < right and nums[left] <= base:
            left += 1
        # 然后將left位置上的值放到right位置上，right位置上的值原本為base值
        nums[right] = nums[left]
    # left=right的位置上就是基準值
    nums[left] = base
    return left

4. 實例測試快速排序代碼

上面的函數中我們已經做了詳細的注釋，和前面第二張圖描述的過程是一致的。接下來我們來對該方法進行測試：

PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> python
Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 22:45:29) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from sort_algorithms import get_num_position
>>> nums = [10, 2, 16, 8, 4, 17, 12, 11]
>>> get_num_position(nums, 0, len(nums) - 1)        
3
>>> nums      
[4, 2, 8, 10, 16, 17, 12, 11]

可以看到，代碼確實實現了我們想要的結果，將比 10 小的全部移動到了左邊，比 10 大的全部移動到了右邊。接下來就是實現快速排序算法。從第一張圖中很明顯可以看到快排算法是一個遞歸的過程，因此我們用遞歸完成快排算法，代碼如下：

# 代碼位置：sort_algorithms.py

def quick_sort(nums, start, end):
    """
    快速排序算法
    """
    if start >= end:
        return 
    pos = get_num_position(nums, start, end)
    # 左邊遞歸下去，直到排好序
    quick_sort(nums, start, pos - 1)
    # 右邊遞歸下去，直到排好序
    quick_sort(nums, pos + 1, end)

對于遞歸方法，后面會詳細介紹到。這里一定要注意，使用遞歸過程一定要先寫終止條件，不然函數無窮遞歸下去，就會導致堆棧溢出錯誤。接下來我們測試這個快排算法：

>>> from sort_algorithms import quick_sort
>>> nums = [8, 7, 9, 6, 11, 3, 12, 20, 9, 5, 1, 10]
>>> quick_sort(nums, 0, len(nums) - 1)
>>> nums
[1, 3, 5, 6, 7, 8, 9, 9, 10, 11, 12, 20] 

可以看到上面的代碼實現了我們想要的排序效果。接下來我們分析下快排算法，它被人們研究的最多，提出了許多改進和優化的方案，我們簡單聊一下快排算法的優化方案。

5. 優化快速排序算法

對于優化快速排序，在這里我們只考慮最簡單的一種優化思路，就是基準數的選擇。前面的快排算法中，我們都是選擇列表的第一個元素作為基準數，這在列表隨機的情況下是沒有什么問題的，但對本身有序的列表進行排序時，時間復雜度就會退化到 $O(n^2)$。我們來進行相關測試：

# 冒泡排序算法
import datetime
import random
from sort_algorithms import get_num_position, quick_sort

# python默認遞歸次數有限制，如果不進行設置，會導致超出遞歸最大次數
import sys   
sys.setrecursionlimit(1000000)

if __name__ == '__main__':
    # 對于設置10000，本人電腦會出現棧溢出錯誤
    # nums = [random.randint(10, 10000) for i in range(6000)] 
    nums = [i for i in range(6000)] 
    start = datetime.datetime.now()
    quick_sort(nums, 0, len(nums) - 1)
    end = datetime.datetime.now()
    print('Running time: %s Seconds' % (end-start))

第一個注釋的語言是對 nums 列表隨機生成，而第二個直接情況是直接生成有序的列表。我們分別看執行結果：

# 隨機列表快排
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.027907 Seconds

# 有序列表快排
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:02.159677 Seconds

可以看到明顯的差別，差不多差了 80 倍，這確實是純快排算法存在的一個問題。如果我們往這個有序列表中插入少量隨機數，打破有序的情況，會看到性能會有較大提升。這個問題的根源在于基準數目的選擇，對于有序的列表排序時每次都是選擇的最小或者最大的值，這就是最壞的情況。一個顯而易見的改進策略就是隨機選擇列表中的值作為基準數，另一種是從頭 (left)、中 ([left + right] // 2) 和尾 (right) 這三個元素中取中間值作為基準數。我們分別進行測試：

import random
def get_base(nums, left, right):
    index = random.randint(left, right)
    if index != left:
        nums[left], nums[index] = nums[index], nums[left]
    return nums[left]


def get_base_middle(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) >> 1

    if nums[mid] > nums[right]:
	    nums[mid], nums[right] = nums[right], nums[mid]

    if nums[left] > nums[right]:
        # nums[left]最大，nums[right]中間，所以交換
	    nums[left], nums[right] = nums[left], nums[mid]

    if nums[mid] > nums[left]:
        # 說明nums[left]最小, nums[mid]為中間值
	    nums[left], nums[mid] = nums[mid], nums[left]

    return nums[left]


def get_num_position(nums, left, right):
    # base = nums[left]
    # 隨機基準數
    base = get_base(nums, left, right)
    # base = get_base_middle(nums, left, right)
    while left < right:
        # 和前面相同，以下兩個while語句用于將基準數放到對應位置，使得基準數左邊的元素都小于它，右邊的數都大于它
        while left < right and nums[right] >= base:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= base:
            left += 1
        nums[right] = nums[left]
    # 基準數的位置，并返回該位置值
    nums[left] = base
    return left

改進后的測試結果如下：

# 有序列表-隨機基準值
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.021890 Seconds

# 隨機列表-隨機基準值
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.026948 Seconds

# 有序列表-中位數基準值
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.012944 Seconds

# 隨機列表-中位數基準值         
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.020933 Seconds

可以看到使用中位數基準值在有序列表情況下排序速度更快。最后還有一個簡單的常用優化方案，就是當序列長度達到一定大小時，使用插入排序。

# 改造前面的插入排序算法
def insert_sort(nums, start, end):
    """
    插入排序
    """
    if not nums:
        return False
    for i in range(start + 1, end + 1):
        t = nums[i]
        for j in range(i - 1, start - 1, -1):
            k = j
            if nums[j] <= t:
                k = k + 1
                break
            nums[j + 1] = nums[j]
        nums[k] = t
    return True 

# ...

def quick_sort(nums, start, end):
    """
    快速排序算法
    """
    if (end - start + 1 < 10):
        # 在排序的數組小到一定程度時，使用插入排序
        insert_sort(nums, start, end)
        return
    # 找到基準數位置，同時調整好數組，使得基準數的左邊小于它，基準數的右邊都是大于它
    pos = get_num_position(nums, start, end)
    # 遞歸使用快排，對左邊使用快排算法
    quick_sort(nums, start, pos - 1)
    # 對右邊元素使用快排算法
    quick_sort(nums, pos + 1, end)

下面是使用【隨機基準+插入排序優化】的測試結果如下：

# 有序列表-[隨機基準+使用插入排序優化]
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.010962 Seconds

# 無序列表-[隨機基準+使用插入排序優化]
PS C:\Users\spyinx\Desktop\學習教程\慕課網教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學習教程/慕課網教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.018935 Seconds

可以看到這些小技巧在真正大規模數據排序時會有非常明顯的效果。更多的優化方法以及測試，讀者可以自行去實驗和測試，這里就不再繼續講解了。

6. 小結

本小節我們介紹了快速排序算法以及相關的優化策略，并完成了簡單的實驗測試，方便大家理解改進的效果。至此，排序算法介紹到此就要結束了。當然高效的排序算法并不止快排算法，海域堆排序、歸并排序、桶排序以及基數排序等等，這些讀者可以自行學習并實現相關代碼，打好算法基礎。

Tips：文中動圖制作參考：https://visualgo.net/zh/sorting。