快速排序

今天我們來聊一聊無論是在筆試還是面試中常?？嫉降?，也是最經(jīng)典和最高效的快速排序算法。它的平均時(shí)間復(fù)雜度為 $O(NlogN)$，空間復(fù)雜度為 $O(1)$。

1. 快速排序算法原理

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

• 分解：以 nums[p] 為基準(zhǔn)將 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]；
• 遞歸求解：通過遞歸調(diào)用快速排序算法分別對 nums[left:p -1] 和 nums[p+1:right] 進(jìn)行排序；
• 合并：由于對 nums[left:p-1] 和 nums[p+1:right] 的排序是就地進(jìn)行的，所以在 nums[left:p-1] 和 nums[p+1:right] 都已排好序后，不需要執(zhí)行任何計(jì)算，nums[left:right] 就已經(jīng)排好序了；

下面是算法示意圖：

2. 快速排序空間復(fù)雜度優(yōu)化

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

可以看下快速排序動態(tài)圖的演示：

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

3. 快速排序算法的 Python 實(shí)現(xiàn)

首先我們實(shí)現(xiàn)上面的核心步驟，代碼如下：

# 代碼位置：sort_algorithms.py

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

4. 實(shí)例測試快速排序代碼

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

PS C:\Users\spyinx\Desktop\學(xué)習(xí)教程\慕課網(wǎng)教程\算法慕課教程\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]

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

# 代碼位置：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)

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

>>> 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] 

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

5. 優(yōu)化快速排序算法

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

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

# python默認(rèn)遞歸次數(shù)有限制，如果不進(jìn)行設(shè)置，會導(dǎo)致超出遞歸最大次數(shù)
import sys   
sys.setrecursionlimit(1000000)

if __name__ == '__main__':
    # 對于設(shè)置10000，本人電腦會出現(xiàn)棧溢出錯誤
    # 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 列表隨機(jī)生成，而第二個直接情況是直接生成有序的列表。我們分別看執(zhí)行結(jié)果：

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

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

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

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]
    # 隨機(jī)基準(zhǔn)數(shù)
    base = get_base(nums, left, right)
    # base = get_base_middle(nums, left, right)
    while left < right:
        # 和前面相同，以下兩個while語句用于將基準(zhǔn)數(shù)放到對應(yīng)位置，使得基準(zhǔn)數(shù)左邊的元素都小于它，右邊的數(shù)都大于它
        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]
    # 基準(zhǔn)數(shù)的位置，并返回該位置值
    nums[left] = base
    return left

改進(jìn)后的測試結(jié)果如下：

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

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

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

# 隨機(jī)列表-中位數(shù)基準(zhǔn)值         
PS C:\Users\spyinx\Desktop\學(xué)習(xí)教程\慕課網(wǎng)教程\算法慕課教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/學(xué)習(xí)教程/慕課網(wǎng)教程/算法慕課教程/code/test_algorithms.py
Running time: 0:00:00.020933 Seconds

可以看到使用中位數(shù)基準(zhǔn)值在有序列表情況下排序速度更快。最后還有一個簡單的常用優(yōu)化方案，就是當(dāng)序列長度達(dá)到一定大小時(shí)，使用插入排序。

# 改造前面的插入排序算法
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):
        # 在排序的數(shù)組小到一定程度時(shí)，使用插入排序
        insert_sort(nums, start, end)
        return
    # 找到基準(zhǔn)數(shù)位置，同時(shí)調(diào)整好數(shù)組，使得基準(zhǔn)數(shù)的左邊小于它，基準(zhǔn)數(shù)的右邊都是大于它
    pos = get_num_position(nums, start, end)
    # 遞歸使用快排，對左邊使用快排算法
    quick_sort(nums, start, pos - 1)
    # 對右邊元素使用快排算法
    quick_sort(nums, pos + 1, end)

下面是使用【隨機(jī)基準(zhǔn)+插入排序優(yōu)化】的測試結(jié)果如下：

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

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

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

6. 小結(jié)

本小節(jié)我們介紹了快速排序算法以及相關(guān)的優(yōu)化策略，并完成了簡單的實(shí)驗(yàn)測試，方便大家理解改進(jìn)的效果。至此，排序算法介紹到此就要結(jié)束了。當(dāng)然高效的排序算法并不止快排算法，海域堆排序、歸并排序、桶排序以及基數(shù)排序等等，這些讀者可以自行學(xué)習(xí)并實(shí)現(xiàn)相關(guān)代碼，打好算法基礎(chǔ)。

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