今天想熟悉一下python的基礎寫法，那就從最經典的快速排序來開始吧：

1、經典分治寫法（原地排序）
時間復雜度：平均O(nlogn)，最壞O(n2)
空間復雜度：O(logn)遞歸棧空間
特點：通過左右指針交換實現原地排序

def quick_sort(arr, low, high):
? ? if low < high:
? ? ? ? pi = partition(arr, low, high)
? ? ? ? quick_sort(arr, low, pi-1)
? ? ? ? quick_sort(arr, pi+1, high)

def partition(arr, low, high):
? ? pivot = arr[high]
? ? i = low - 1
? ? for j in range(low, high):
? ? ? ? if arr[j] <= pivot:
? ? ? ? ? ? i += 1
? ? ? ? ? ? arr[i], arr[j] = arr[j], arr[i]
? ? arr[i+1], arr[high] = arr[high], arr[i+1]
? ? return i + 1

2、Pythonic簡潔寫法（非原地）
特點：利用列表推導式，代碼更簡潔但需要額外空間

quick_sort(arr):
? ? if len(arr) <= 1:
? ? ? ? return arr
? ? pivot = arr[len(arr)//2]
? ? left = [x for x in arr if x < pivot]
? ? middle = [x for x in arr if x == pivot]
? ? right = [x for x in arr if x > pivot]
? ? return quick_sort(left) + middle + quick_sort(right)

?

3、尾遞歸優化寫法
特點：減少遞歸深度，避免棧溢出風險

quick_sort(arr, low=0, high=None):
? ? if high is None:
? ? ? ? high = len(arr) - 1
? ? while low < high:
? ? ? ? pi = partition(arr, low, high)
? ? ? ? if pi - low < high - pi:
? ? ? ? ? ? quick_sort(arr, low, pi-1)
? ? ? ? ? ? low = pi + 1
? ? ? ? else:
? ? ? ? ? ? quick_sort(arr, pi+1, high)
? ? ? ? ? ? high = pi - 1
? ? return arr

算法核心思想：分治法+基準值選取。第一種實現最接近傳統快速排序定義，第二種適合教學演示，第三種適合處理大數據集。實際使用時建議添加隨機化基準值選擇來避免最壞情況。