# Python中常用排序算法有哪些
排序算法是計算機科學中最基礎且重要的算法類別之一。Python作為廣泛應用的高級編程語言，內置了高效的排序函數，但理解底層排序原理對開發者至關重要。本文將系統介紹Python中12種常用排序算法，包含原理分析、代碼實現、復雜度對比及適用場景。
## 目錄
1. [排序算法概述](#排序算法概述)
2. [內置排序函數](#內置排序函數)
3. [簡單排序算法](#簡單排序算法)
- [冒泡排序](#冒泡排序)
- [選擇排序](#選擇排序)
- [插入排序](#插入排序)
4. [高效排序算法](#高效排序算法)
- [快速排序](#快速排序)
- [歸并排序](#歸并排序)
- [堆排序](#堆排序)
5. [特殊場景排序](#特殊場景排序)
- [計數排序](#計數排序)
- [桶排序](#桶排序)
- [基數排序](#基數排序)
6. [其他排序算法](#其他排序算法)
- [希爾排序](#希爾排序)
- [TimSort](#TimSort)
- [Bogo排序](#Bogo排序)
7. [算法對比與選擇](#算法對比與選擇)
8. [Python排序實踐技巧](#Python排序實踐技巧)
9. [總結](#總結)
## 排序算法概述
排序算法可分為兩大類：
- **比較排序**：通過比較元素決定順序（如快速排序）
- **非比較排序**：利用元素特性無需比較（如計數排序）
主要評估指標：
- 時間復雜度（最好/最壞/平均）
- 空間復雜度
- 穩定性（相等元素相對位置是否改變）
## 內置排序函數
Python提供了開箱即用的排序方案：
```python
# list.sort() 原地排序
data = [5, 2, 9, 1]
data.sort() # [1, 2, 5, 9]
# sorted() 返回新列表
result = sorted([3, 1, 4]) # [1, 3, 4]
特點： - TimSort算法實現 - 時間復雜度O(n log n) - 穩定排序 - 支持自定義key函數
原理：重復比較相鄰元素，將較大值逐步”冒泡”到右側
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
原理：每次選擇未排序部分的最小值放到已排序末尾
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
原理：構建有序序列，逐個將未排序元素插入正確位置
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
原理：分治法，選取基準值將數組分為兩部分遞歸排序
def 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)
原理：分治法，將數組分成兩半分別排序后合并
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(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
原理：利用堆數據結構進行選擇排序
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
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)
原理：統計每個元素的出現次數，按統計結果輸出
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
output = []
for i in range(len(count)):
output.extend([i] * count[i])
return output
原理：將數據分到有限數量的桶里，每個桶單獨排序
def bucket_sort(arr, bucket_size=5):
min_val, max_val = min(arr), max(arr)
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for num in arr:
buckets[(num - min_val) // bucket_size].append(num)
return [num for bucket in buckets for num in sorted(bucket)]
原理：按位數從低到高依次排序（LSD方法）
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
def counting_sort_by_digit(arr, exp):
output = [0] * len(arr)
count = [0] * 10
for num in arr:
digit = (num // exp) % 10
count[digit] += 1
for i in range(1, 10):
count[i] += count[i-1]
for num in reversed(arr):
digit = (num // exp) % 10
output[count[digit]-1] = num
count[digit] -= 1
for i in range(len(arr)):
arr[i] = output[i]
原理：改進的插入排序，通過增量序列分組排序
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
Python內置排序算法，結合歸并排序和插入排序優點：
特點： - 自適應算法（根據數據特性調整策略） - 時間復雜度：O(n log n) - 空間復雜度：O(n) - 穩定排序
原理：隨機打亂數組直到有序（理論分析用）
import random
def bogo_sort(arr):
while not is_sorted(arr):
random.shuffle(arr)
def is_sorted(arr):
return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
| 算法 | 平均時間復雜度 | 最壞時間復雜度 | 空間復雜度 | 穩定性 | 適用場景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) | 穩定 | 教學、小規模數據 |
| 選擇排序 | O(n2) | O(n2) | O(1) | 不穩定 | 交換成本高場景 |
| 插入排序 | O(n2) | O(n2) | O(1) | 穩定 | 小規?；蚧居行驍祿?/td> |
| 快速排序 | O(n log n) | O(n2) | O(log n) | 不穩定 | 通用排序、大規模數據 |
| 歸并排序 | O(n log n) | O(n log n) | O(n) | 穩定 | 鏈表排序、外部排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不穩定 | 實時系統、TopK問題 |
| 計數排序 | O(n + k) | O(n + k) | O(k) | 穩定 | 整數小范圍數據 |
| 桶排序 | O(n + k) | O(n2) | O(n + k) | 穩定 | 均勻分布數據 |
| 基數排序 | O(nk) | O(nk) | O(n + k) | 穩定 | 多位數排序 |
| TimSort | O(n log n) | O(n log n) | O(n) | 穩定 | Python內置通用排序 |
選擇建議： 1. 小數據量（n < 100）：插入排序 2. 大數據量通用排序：快速排序/TimSort 3. 需要穩定性：歸并排序/TimSort 4. 數據范圍有限：計數排序/桶排序 5. 內存受限：堆排序
# 按字符串長度排序
sorted(lst, key=lambda x: len(x))
# 多級排序
sorted(tuples, key=lambda x: (x[1], x[0]))
# 使用operator模塊加速
from operator import itemgetter
sorted(lst, key=itemgetter(1))
# 對復雜對象排序時預先計算key
decorated = [(obj.key, obj) for obj in objects]
decorated.sort()
result = [obj for (key, obj) in decorated]
# 多次排序實現復雜排序需求
data.sort(key=lambda x: x['age']) # 次要鍵先排序
data.sort(key=lambda x: x['score'], reverse=True) # 主鍵后排序
# 使用生成器減少內存消耗
def large_sort(file):
with open(file) as f:
yield from sorted(f)
# 分塊排序合并（外部排序）
Python提供了豐富的排序算法選擇，從簡單的O(n2)算法到高效的O(n log n)算法，再到特殊場景下的線性排序算法。實際開發中：
sorted()和list.sort()排序算法的選擇本質上是時間、空間和穩定性之間的權衡，優秀的開發者應當根據具體場景做出合理決策。 “`
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
