1. 快速排序（Quick Sort）
原理：
- 選擇一個基準值（pivot）
- 將數組分成兩部分：小于 pivot 的放左邊，大于 pivot 的放右邊。然后遞歸處理
工作過程示例：
示例數組：[5, 3, 8, 4, 2]
- 選擇 pivot = 8
左：[5, 3, 4, 2]，中：[8]，右：[] - 遞歸左部分 pivot = 4
左：[3, 2]，中：[4]，右：[5] - 遞歸 [3, 2] pivot = 2
左：[]，中：[2]，右：[3] - 合并結果：
[] + [2] + [3]→[2, 3] - 逐步合并：
[2, 3] + [4] + [5]→[2, 3, 4, 5]
[2, 3, 4, 5] + [8]→[2, 3, 4, 5, 8]
代碼：
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2] # 選中間值left = [x for x in arr if x < pivot] # 左邊mid = [x for x in arr if x == pivot] # 中間right = [x for x in arr if x > pivot] # 右邊return quick_sort(left) + mid + quick_sort(right)print(quick_sort([5, 3, 8, 4, 2]))
2. 堆排序（Heap Sort）
原理：
- 構建最大堆（堆頂是最大元素）
- 將堆頂與末尾交換，縮小堆的范圍
- 重新堆化，直到數組有序
工作過程示例：
示例數組：[5, 3, 8, 4, 2]
- 建最大堆 →
[8, 4, 5, 3, 2]（堆頂是最大值 8） - 交換堆頂與末尾 →
[2, 4, 5, 3, 8]，縮小堆范圍 - 堆化 →
[5, 4, 2, 3, 8] - 交換堆頂與末尾 →
[3, 4, 2, 5, 8] - 堆化 →
[4, 3, 2, 5, 8] - 交換堆頂與末尾 →
[2, 3, 4, 5, 8] - 完成排序：
[2, 3, 4, 5, 8]
代碼：
def heapify(arr, n, i):largest = il, r = 2*i + 1, 2*i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n//2 - 1, -1, -1): # 建堆heapify(arr, n, i)for i in range(n - 1, 0, -1): # 排序arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arrprint(heap_sort([5, 3, 8, 4, 2]))
3. 歸并排序（Merge Sort）
原理：
- 遞歸將數組拆分成左右兩半
- 分別排序后，合并兩個有序數組
- 典型的分治算法，穩定
工作過程示例
示例數組：[5, 3, 8, 4, 2]
- 拆分：
[5, 3, 8]和[4, 2]
[5, 3]和[8]→[5][3][8]
[4][2] - 合并（按順序）：
[5] + [3]→[3, 5]
[4] + [2]→[2, 4] - 合并
[3, 5]和[8]→[3, 5, 8] - 合并
[3, 5, 8]和[2, 4]→[2, 3, 4, 5, 8]
代碼：
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):res = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:res.append(left[i])i += 1else:res.append(right[j])j += 1res.extend(left[i:])res.extend(right[j:])return resprint(merge_sort([5, 3, 8, 4, 2]))
4. 希爾排序（Shell Sort）
原理：
- 插入排序的改進版
- 先分成間隔為
gap的多個子序列，對每個子序列做插入排序 - 逐步縮小
gap，直到gap=1時完成排序
工作過程示例：
示例數組：[5, 3, 8, 4, 2]
- gap = 2（分組做插入排序）
組1:[5, 8, 2]→[2, 8, 5]
組2:[3, 4]→[3, 4]
排序結果：[2, 3, 8, 4, 5] - gap = 1（普通插入排序）
[2, 3, 4, 5, 8]→ 完成
代碼：
def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2return arrprint(shell_sort([5, 3, 8, 4, 2]))
5. 計數排序（Counting Sort）
原理：
- 適用于整數且范圍不大的情況
- 統計每個值出現的次數
- 按次數依次回填到數組中
工作過程示例：
示例數組：[5, 3, 8, 4, 2]
- 找范圍：min=2，max=8
- 計數數組（索引表示值-2）：
值：2 3 4 5 6 7 8
次數：[1,1,1,1,0,0,1] - 回填：
輸出[2, 3, 4, 5, 8]
代碼：
def counting_sort(arr):if not arr:return arrmin_val, max_val = min(arr), max(arr)count = [0] * (max_val - min_val + 1)for num in arr:count[num - min_val] += 1res = []for i, c in enumerate(count):res.extend([i + min_val] * c)return resprint(counting_sort([5, 3, 8, 4, 2]))
