沈無(wú)奇 ·快速排序
今天我們來(lái)聊一聊無(wú)論是在筆試還是面試中常?？嫉降?，也是最經(jīng)典和最高效的快速排序算法。它的平均時(shí)間復(fù)雜度為 ，空間復(fù)雜度為 。
1. 快速排序算法原理
快速排序算法是基于這樣的思想：從待排序的列表選擇一個(gè)基準(zhǔn)數(shù)，然后將列表中比該基準(zhǔn)數(shù)大的放到該數(shù)的右邊，比該基準(zhǔn)數(shù)小的值放到該基準(zhǔn)數(shù)的左邊；接下來(lái)執(zhí)行遞歸操作，對(duì)基準(zhǔn)數(shù)左邊的待排序列表執(zhí)行前面同樣的操作，直到左邊的列表有序，對(duì)于基準(zhǔn)數(shù)右邊的待排序列表也執(zhí)行前面同樣的操作，直到右邊的列表有序。此時(shí)，整個(gè)列表有序。即對(duì)于輸入的數(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]中任何一個(gè)元素小于等于nums[p]， 而nums[p+1:right]中任何一個(gè)元素大于等于nums[p]； - 遞歸求解：通過(guò)遞歸調(diào)用快速排序算法分別對(duì)
nums[left:p -1]和nums[p+1:right]進(jìn)行排序； - 合并：由于對(duì)
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)化
可以看到，上述快速排序算法的一個(gè)核心步驟是：**將列表中的比基準(zhǔn)數(shù)小的全部移動(dòng)到基準(zhǔn)數(shù)的左邊，其余數(shù)移動(dòng)到基準(zhǔn)數(shù)的右邊，且整個(gè)算法的過(guò)程不能使用額外的空間。**這樣的算法才比較高效，空間復(fù)雜度為 O(1)。那么怎么做到不使用額外空間達(dá)到這一目的呢？請(qǐng)看下面的示意圖進(jìn)行理解。
可以看下快速排序動(dòng)態(tài)圖的演示：
接下來(lá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)值為第一個(gè)
base = nums[left]
while left < right:
# 從最右邊向左直到找到小于基準(zhǔn)值的數(shù)
while left < right and nums[right] >= base:
right -= 1
# 將小于基準(zhǔn)數(shù)的值放到右邊，left原來(lái)位置放的是基準(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í)例測(cè)試快速排序代碼
上面的函數(shù)中我們已經(jīng)做了詳細(xì)的注釋?zhuān)颓懊娴诙垐D描述的過(guò)程是一致的。接下來(lái)我們來(lái)對(duì)該方法進(jìn)行測(cè)試：
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 小的全部移動(dòng)到了左邊，比 10 大的全部移動(dòng)到了右邊。接下來(lái)就是實(shí)現(xiàn)快速排序算法。從第一張圖中很明顯可以看到快排算法是一個(gè)遞歸的過(guò)程，因此我們用遞歸完成快排算法，代碼如下：
# 代碼位置：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)
對(duì)于遞歸方法，后面會(huì)詳細(xì)介紹到。這里一定要注意，使用遞歸過(guò)程一定要先寫(xiě)終止條件，不然函數(shù)無(wú)窮遞歸下去，就會(huì)導(dǎo)致堆棧溢出錯(cuò)誤。接下來(lái)我們測(cè)試這個(gè)快排算法：
>>> 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)了我們想要的排序效果。接下來(lái)我們分析下快排算法，它被人們研究的最多，提出了許多改進(jìn)和優(yōu)化的方案，我們簡(jiǎn)單聊一下快排算法的優(yōu)化方案。
5. 優(yōu)化快速排序算法
對(duì)于優(yōu)化快速排序，在這里我們只考慮最簡(jiǎn)單的一種優(yōu)化思路，就是基準(zhǔn)數(shù)的選擇。前面的快排算法中，我們都是選擇列表的第一個(gè)元素作為基準(zhǔn)數(shù)，這在列表隨機(jī)的情況下是沒(méi)有什么問(wèn)題的，但對(duì)本身有序的列表進(jìn)行排序時(shí)，時(shí)間復(fù)雜度就會(huì)退化到 。我們來(lái)進(jìn)行相關(guān)測(cè)試：
# 冒泡排序算法
import datetime
import random
from sort_algorithms import get_num_position, quick_sort
# python默認(rèn)遞歸次數(shù)有限制，如果不進(jìn)行設(shè)置，會(huì)導(dǎo)致超出遞歸最大次數(shù)
import sys
sys.setrecursionlimit(1000000)
if __name__ == '__main__':
# 對(duì)于設(shè)置10000，本人電腦會(huì)出現(xiàn)棧溢出錯(cuò)誤
# 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))
第一個(gè)注釋的語(yǔ)言是對(duì) nums 列表隨機(jī)生成，而第二個(gè)直接情況是直接生成有序的列表。我們分別看執(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í)是純快排算法存在的一個(gè)問(wèn)題。如果我們往這個(gè)有序列表中插入少量隨機(jī)數(shù)，打破有序的情況，會(huì)看到性能會(huì)有較大提升。這個(gè)問(wèn)題的根源在于基準(zhǔn)數(shù)目的選擇，對(duì)于有序的列表排序時(shí)每次都是選擇的最小或者最大的值，這就是最壞的情況。一個(gè)顯而易見(jiàn)的改進(jìn)策略就是隨機(jī)選擇列表中的值作為基準(zhǔn)數(shù)，另一種是從頭 (left)、中 ([left + right] // 2) 和尾 (right) 這三個(gè)元素中取中間值作為基準(zhǔn)數(shù)。我們分別進(jìn)行測(cè)試：
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]:
# 說(shuō)明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:
# 和前面相同，以下兩個(gè)while語(yǔ)句用于將基準(zhǔn)數(shù)放到對(duì)應(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)后的測(cè)試結(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)值在有序列表情況下排序速度更快。最后還有一個(gè)簡(jiǎn)單的常用優(yōu)化方案，就是當(dāng)序列長(zhǎ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)
# 遞歸使用快排，對(duì)左邊使用快排算法
quick_sort(nums, start, pos - 1)
# 對(duì)右邊元素使用快排算法
quick_sort(nums, pos + 1, end)
下面是使用【隨機(jī)基準(zhǔn)+插入排序優(yōu)化】的測(cè)試結(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
# 無(wú)序列表-[隨機(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í)會(huì)有非常明顯的效果。更多的優(yōu)化方法以及測(cè)試，讀者可以自行去實(shí)驗(yàn)和測(cè)試，這里就不再繼續(xù)講解了。
6. 小結(jié)
本小節(jié)我們介紹了快速排序算法以及相關(guān)的優(yōu)化策略，并完成了簡(jiǎn)單的實(shí)驗(yàn)測(cè)試，方便大家理解改進(jìn)的效果。至此，排序算法介紹到此就要結(jié)束了。當(dāng)然高效的排序算法并不止快排算法，海域堆排序、歸并排序、桶排序以及基數(shù)排序等等，這些讀者可以自行學(xué)習(xí)并實(shí)現(xiàn)相關(guān)代碼，打好算法基礎(chǔ)。
Tips：文中動(dòng)圖制作參考：https://visualgo.net/zh/sorting。
2025 imooc.com All Rights Reserved |