# 常见的排序算法有哪些
排序算法是计算机科学中最基础且重要的算法类别之一，用于将一组数据按照特定顺序（升序或降序）重新排列。本文将详细介绍12种常见的排序算法，包括它们的原理、时间复杂度、空间复杂度及适用场景。
## 目录
1. [冒泡排序](#冒泡排序)
2. [选择排序](#选择排序)
3. [插入排序](#插入排序)
4. [希尔排序](#希尔排序)
5. [归并排序](#归并排序)
6. [快速排序](#快速排序)
7. [堆排序](#堆排序)
8. [计数排序](#计数排序)
9. [桶排序](#桶排序)
10. [基数排序](#基数排序)
11. [Tim排序](#Tim排序)
12. [总结对比](#总结对比)
---
## 冒泡排序
### 原理
通过重复遍历待排序列表，比较相邻元素并交换位置，使较大元素逐渐"浮"到列表末端。
### 代码示例
```python
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 merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L, R = arr[:mid], arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
大数据量排序，需要稳定性的场景。
选取基准元素（pivot），将列表分为小于和大于基准的两部分，递归排序子列表。
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)
大规模数据排序，实际应用中最快的通用排序算法。
利用堆数据结构（完全二叉树）的特性进行排序。
统计每个元素出现次数，然后计算元素在输出数组中的位置。
将数据分到有限数量的桶里，每个桶单独排序（可能使用其他算法）。
按位数从低到高（或相反）依次进行稳定排序（通常用计数排序）。
Python内置排序算法，结合归并排序和插入排序的混合算法。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学、小规模数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 教学 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模或基本有序数据 |
| 希尔排序 | O(n^(3⁄2)) | O(n²) | O(1) | 不稳定 | 中等规模数据 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 | 大数据量、需要稳定性 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 | 通用排序、大规模数据 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 内存受限场景 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | 稳定 | 整数、范围小 |
| 桶排序 | O(n+k) | O(n²) | O(n+k) | 可变 | 均匀分布数据 |
| 基数排序 | O(nk) | O(nk) | O(n+k) | 稳定 | 整数、字符串等可分解数据 |
| Tim排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 | 通用（Python/Java默认实现） |
注：k表示数据范围或位数，n表示数据量
在实际应用中，通常会根据以下因素选择排序算法： 1. 数据规模 2. 数据分布特征 3. 是否需要稳定性 4. 内存限制 5. 实现复杂度 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
