# 十大经典排序算法

URL: https://caijiao.org/sort/
Source: docs/sort/index.md
Description: 本文介绍十大经典排序算法，包括冒泡排序、快速排序、归并排序、堆排序等。涵盖其原理、时间复杂度、稳定性及适用场景，并提供分类比较和应用建议。

经典排序算法有很多，常见的包括**比较类排序**和**非比较类排序**两大类。以下是最具代表性的经典排序算法及其简要介绍：

## 🔢 比较类排序（基于元素比较，时间复杂度最差为 O(n²) 或 O(n log n)）

### 1. 冒泡排序（Bubble Sort）

- **原理**：相邻元素两两比较，大的往后“冒”。
- **时间复杂度**：最坏 O(n²)，最好 O(n)
- **空间复杂度**：O(1)
- **是否稳定**：✅ 稳定
- **详情**：[冒泡排序（Bubble Sort）](/sort/1-bubble-sort)

### 2. 选择排序（Selection Sort）

- **原理**：每次选择最小（大）元素，放到已排序序列尾部。
- **时间复杂度**：O(n²)
- **空间复杂度**：O(1)
- **是否稳定**：❌ 不稳定
- **详情**：[选择排序（Selection Sort）](/sort/2-selection-sort)

### 3. 插入排序（Insertion Sort）

- **原理**：将当前元素插入到前面已排序部分的合适位置。
- **时间复杂度**：最坏 O(n²)，最好 O(n)
- **空间复杂度**：O(1)
- **是否稳定**：✅ 稳定
- **详情**：[插入排序（Insertion Sort）](/sort/3-insertion-sort)

### 4. 希尔排序（Shell Sort）

- **原理**：分组插入排序，逐步缩小间隔。
- **时间复杂度**：平均 O(n^1.3)，具体取决于增量序列
- **空间复杂度**：O(1)
- **是否稳定**：❌ 不稳定
- **详情**：[希尔排序（Shell Sort）](/sort/4-shell-sort)

### 5. 归并排序（Merge Sort）

- **原理**：分治法，先递归分解，再合并有序数组。
- **时间复杂度**：O(n log n)
- **空间复杂度**：O(n)
- **是否稳定**：✅ 稳定
- **详情**：[归并排序（Merge Sort）](/sort/5-merge-sort)

### 6. 快速排序（Quick Sort）

- **原理**：分治法，选定一个基准元素，划分左右两边递归排序。
- **时间复杂度**：平均 O(n log n)，最坏 O(n²)
- **空间复杂度**：O(log n)
- **是否稳定**：❌ 不稳定
- **详情**：[快速排序（Quick Sort）](/sort/6-quick-sort)

### 7. 堆排序（Heap Sort）

- **原理**：构造最大（或最小）堆，依次取顶元素。
- **时间复杂度**：O(n log n)
- **空间复杂度**：O(1)
- **是否稳定**：❌ 不稳定
- **详情**：[堆排序（Heap Sort）](/sort/7-heap-sort)

## ⚙️ 非比较类排序（基于元素特征，不是基于比较）

### 8. 计数排序（Counting Sort）

- **原理**：统计每个数出现次数，适用于整数、范围小。
- **时间复杂度**：O(n + k)，k 是数值范围
- **空间复杂度**：O(k)
- **是否稳定**：✅ 稳定
- **详情**：[计数排序（Counting Sort）](/sort/8-counting-sort)

### 9. 桶排序（Bucket Sort）

- **原理**：将元素分到多个桶中，桶内排序。
- **时间复杂度**：平均 O(n)，最坏 O(n²)
- **空间复杂度**：O(n + k)
- **是否稳定**：✅ 稳定（若桶内排序稳定）
- **详情**：[桶排序（Bucket Sort）](/sort/9-bucket-sort)

### 10. 基数排序（Radix Sort）

- **原理**：按位排序（最低位开始），适合整数或字符串。
- **时间复杂度**：O(nk)，k 为最大位数
- **空间复杂度**：O(n + k)
- **是否稳定**：✅ 稳定
- **详情**：[基数排序（Radix Sort）](/sort/10-radix-sort)

## 🧠 按应用选择排序算法建议：

| 数据规模   | 数据特点      | 推荐算法            |
|------------|----------------|---------------------|
| 小规模     | 无明显特点     | 插入排序、冒泡排序 |
| 中等规模   | 稳定性要求高   | 归并排序           |
| 大规模     | 速度要求高     | 快速排序、堆排序   |
| 整数且范围小 | 非比较排序适用 | 计数、基数、桶排序 |