排序算法是計算機科學中的基礎課題，無論是在日常開發還是算法面試中都占據重要地位。本文將通過動態圖解和詳細代碼，帶你全面掌握十種經典排序算法。
一、冒泡排序（Bubble Sort）
原理：重復比較相鄰元素，將較大元素逐步“冒泡”至右側。
動態圖解：
假設數組 [5,3,8,6,4]
第一輪：
5>3 → 交換 → [3,5,8,6,4]
5<8 → 保持
8>6 → 交換 → [3,5,6,8,4]
8>4 → 交換 → [3,5,6,4,8]
后續輪次繼續處理未排序部分。
代碼實現（Python）：`python
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr`
二、選擇排序（Selection Sort）
原理：每次從未排序部分選擇最小元素，放到已排序序列末尾。
代碼實現：`python
def selectionsort(arr):
n = len(arr)
for i in range(n-1):
minidx = i
for j in range(i+1, n):
if arr[j] < arr[minidx]:
minidx = j
arr[i], arr[minidx] = arr[minidx], arr[i]
return arr`
三、插入排序（Insertion Sort）
原理：將每個元素插入到已排序序列的適當位置。
動態圖解：
初始：[5,3,8,6,4]
第一步：3插入5前 → [3,5,8,6,4]
第二步：8保持 → [3,5,8,6,4]
第三步：6插入5和8之間 → [3,5,6,8,4]
第四步：4插入3和5之間 → [3,4,5,6,8]
代碼實現：`python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr`
四、希爾排序（Shell Sort）
原理：改進的插入排序，通過增量分組進行預處理。
代碼實現：`python
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
return arr`
五、歸并排序（Merge Sort）
原理：分治策略，先遞歸分解數組，再合并有序子序列。
代碼實現：`python
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result`
六、快速排序（Quick Sort）
原理：選取基準值，將數組分為小于基準和大于基準的兩部分，遞歸排序。
動態圖解：
數組 [5,3,8,6,4]，選擇基準5：
分區過程：
3<5 → 放左側
8>5 → 放右側
6>5 → 放右側
4<5 → 放左側
得到 [3,4] 5 [8,6]
遞歸處理左右子數組。
代碼實現：`python
def quicksort(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 quicksort(left) + middle + quick_sort(right)`
七、堆排序（Heap Sort）
原理：構建最大堆，反復取出堆頂元素完成排序。
代碼實現：`python
def heapify(arr, n, i):
largest = i
left = 2i + 1
right = 2i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if 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 arr`
八、計數排序（Counting Sort）
原理：統計每個元素出現的次數，按統計結果輸出有序序列。
代碼實現：`python
def countingsort(arr):
if not arr:
return []
maxval = max(arr)
count = [0] (max_val+1)
for num in arr:
count[num] += 1
result = []
for i in range(len(count)):
result.extend([i] count[i])
return result`
九、桶排序（Bucket Sort）
原理：將數據分到有限數量的桶中，每個桶單獨排序。
代碼實現：`python
def bucketsort(arr, bucketsize=5):
if not arr:
return []
minval, maxval = min(arr), max(arr)
bucketcount = (maxval - minval) // bucketsize + 1
buckets = [[] for in range(bucketcount)]
for num in arr:
buckets[(num - minval) // bucketsize].append(num)
result = []
for bucket in buckets:
result.extend(sorted(bucket))
return result`
十、基數排序（Radix Sort）
原理：按位數從低位到高位依次進行穩定排序。
動態圖解：
數組 [170,45,75,90,802,24,2,66]
第一輪按個位排序：
桶0: 170,90
桶2: 802,2
桶4: 24
桶5: 45,75
桶6: 66
得到 [170,90,802,2,24,45,75,66]
第二輪按十位排序...
代碼實現：`python
def radixsort(arr):
maxnum = max(arr)
exp = 1
while maxnum // exp > 0:
buckets = [[] for in range(10)]
for num in arr:
buckets[(num // exp) % 10].append(num)
arr = []
for bucket in buckets:
arr.extend(bucket)
exp *= 10
return arr`
算法對比與
| 算法 | 平均時間復雜度 | 空間復雜度 | 穩定性 | 適用場景 |
|------|---------------|------------|--------|----------|
| 冒泡排序 | O(n2) | O(1) | 穩定 | 教學示例，小規模數據 |
| 選擇排序 | O(n2) | O(1) | 不穩定 | 簡單實現 |
| 插入排序 | O(n2) | O(1) | 穩定 | 小規模或基本有序數據 |
| 希爾排序 | O(n log n) | O(1) | 不穩定 | 中等規模數據 |
| 歸并排序 | O(n log n) | O(n) | 穩定 | 大數據量，需要穩定排序 |
| 快速排序 | O(n log n) | O(log n) | 不穩定 | 通用場景，平均性能最優 |
| 堆排序 | O(n log n) | O(1) | 不穩定 | 內存受限場景 |
| 計數排序 | O(n+k) | O(k) | 穩定 | 整數排序，值范圍較小 |
| 桶排序 | O(n+k) | O(n+k) | 穩定 | 均勻分布的數據 |
| 基數排序 | O(nk) | O(n+k) | 穩定 | 多關鍵字排序 |
學習建議
- 理解優先：先理解算法原理，再記憶代碼
- 可視化學習：使用排序可視化工具觀察算法執行過程
- 動手實現：獨立編寫每種算法的代碼
- 對比分析：通過不同數據集測試算法性能
- 場景選擇：根據實際需求選擇合適的排序算法
掌握這十種排序算法，不僅能夠應對技術面試，更能深入理解算法設計的核心思想。建議讀者將代碼實際運行，并嘗試用不同數據測試，觀察排序過程的變化。
