快速排序的基本思路¶
快速排序是一種高效的排序算法，它基於“分而治之”的思想。簡單來說，就是先從數組中選一個元素作爲“基準值”（pivot），然後把數組分成兩部分：一部分所有元素都比基準值小，另一部分所有元素都比基準值大。接着，對這兩部分分別遞歸地應用快速排序，直到整個數組有序。
分區過程詳解¶
分區是快速排序的核心步驟，我們通過一個例子來理解它：
假設數組爲 [5, 3, 8, 4, 2, 7, 1, 6]，我們選第一個元素 5 作爲基準值。分區過程如下：
- 初始化指針：
left指向數組左側（初始爲0，對應元素5），right指向數組右側（初始爲7，對應元素6）。 - 移動指針：
- 先移動right指針，直到找到比基準值小的元素。這裏right從7開始，元素6>5，左移到6（元素1），1<5，停止移動。
- 再移動left指針，直到找到比基準值大的元素。left從0開始，元素5是基準，左移到1（元素3），3<5，繼續左移到2（元素8），8>5，停止移動。
- 交換元素：交換left（2）和right（6）的元素，數組變爲[5, 3, 1, 4, 2, 7, 8, 6]。 - 重複過程：繼續移動指針，直到
left >= right。最終left和right會在中間位置（此時left=right=4），交換基準值（位置0）和left位置的元素，得到分區結果：[2, 3, 1, 4, 5, 7, 8, 6]。
此時，基準值 5 左邊的元素（[2, 3, 1, 4]）都小於5，右邊的元素（[7, 8, 6]）都大於5。
Python代碼實現¶
分區函數（partition）¶
分區函數的作用是確定基準值的最終位置，並將數組分爲左右兩部分：
def partition(arr, low, high):
pivot = arr[low] # 選擇第一個元素作爲基準值
left = low # 左指針
right = high # 右指針
while left < right:
# 右指針向左移動，直到找到比基準值小的元素
while left < right and arr[right] > pivot:
right -= 1
# 左指針向右移動，直到找到比基準值大的元素
while left < right and arr[left] < pivot:
left += 1
# 交換左右指針指向的元素
if left < right:
arr[left], arr[right] = arr[right], arr[left]
# 將基準值放到最終位置（left=right處）
arr[low], arr[left] = arr[left], arr[low]
return left # 返回基準值的索引
快速排序函數（quick_sort）¶
遞歸調用分區函數，對左右子數組分別排序：
def quick_sort(arr, low, high):
if low < high: # 遞歸終止條件：子數組長度爲1或0時停止
# 分區，獲取基準值位置
pivot_index = partition(arr, low, high)
# 遞歸排序左子數組（基準值左側）
quick_sort(arr, low, pivot_index - 1)
# 遞歸排序右子數組（基準值右側）
quick_sort(arr, pivot_index + 1, high)
測試代碼¶
# 測試快速排序
arr = [5, 3, 8, 4, 2, 7, 1, 6]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("排序後的數組：", arr) # 輸出：排序後的數組： [1, 2, 3, 4, 5, 6, 7, 8]
代碼解釋¶
- 基準值選擇：我們選數組第一個元素作爲基準值（也可隨機選擇，避免極端情況）。
- 分區邏輯：通過左右指針
left和right遍歷數組，交換不滿足條件的元素，最終讓基準值左邊都是小於它的元素，右邊都是大於它的元素。 - 遞歸終止條件：當
low >= high時，子數組長度爲1或0，已經有序，無需排序。
複雜度分析¶
- 時間複雜度：平均情況下爲 O(n log n)（每次分區將數組分爲大致相等的兩部分，遞歸深度爲 log n，每層分區需遍歷 n 個元素）。
- 最壞情況：若數組已排序且每次選第一個元素爲基準，時間複雜度退化爲 O(n²)（可通過隨機選基準優化）。
總結¶
快速排序通過“分治+遞歸”的思想，高效地對數組進行排序。核心是分區過程：選基準、調整元素、遞歸處理子數組。它是實際應用中最常用的排序算法之一，理解其原理和實現對掌握排序算法至關重要。
通過本文的例子和代碼，你可以逐步理解快速排序的執行過程，並嘗試修改基準值選擇方式（如隨機選基準）來優化算法。