您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 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(n²) | O(n²) | O(1) | 稳定 | 教学、小规模数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 交换成本高场景 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模或基本有序数据 |
| 快速排序 | O(n log n) | O(n²) | 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(n²) | 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(n²)算法到高效的O(n log n)算法，再到特殊场景下的线性排序算法。实际开发中：
sorted()和list.sort()排序算法的选择本质上是时间、空间和稳定性之间的权衡，优秀的开发者应当根据具体场景做出合理决策。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。