五大类排序算法完整总结

以下是整合后的五大类排序算法完整总结，涵盖选择、交换、插入、归并、分配五大类，包括算法原理、时间/空间复杂度及稳定性对比：

---

一、选择排序（Selection Sort）

1. 简单选择排序

原理：

1. 每次从未排序部分选择最小（或最大）元素。
2. 与未排序部分的第一个元素交换。
3. 重复直到全部有序。

复杂度：

• 时间：O(n²)（始终需遍历剩余部分）
• 空间：O(1)
• 稳定性：不稳定（交换可能破坏顺序）

2. 堆排序（Heap Sort）

原理：

1. 构建最大堆（或最小堆）。
2. 将堆顶元素（最大值）与末尾交换，堆大小减1。
3. 调整堆，重复直到堆为空。

复杂度：

• 时间：O(n log n)（建堆O(n) + 每次调整O(log n)）
• 空间：O(1)
• 稳定性：不稳定

---

二、交换排序（Exchange Sort）

1. 快速排序（Quick Sort）

原理：

1. 选择基准（pivot），分区（左小右大）。
2. 递归排序左右子数组。

复杂度：

• 时间：
  • 平均/最好：O(n log n)
  • 最坏：O(n²)（如数组已有序且基准选择不当）
• 空间：O(log n)（递归栈）
• 稳定性：不稳定

2. 冒泡排序（Bubble Sort）

原理：

1. 相邻元素比较交换，每轮将最大值“冒泡”到末尾。
2. 优化：可提前终止（无交换时）。

复杂度：

• 时间：
  • 最好：O(n)（已有序）
  • 最坏/平均：O(n²)
• 空间：O(1)
• 稳定性：稳定

---

三、插入排序（Insertion Sort）

1. 直接插入排序

原理：

1. 将未排序元素逐个插入已排序部分的正确位置。

复杂度：

• 时间：
  • 最好：O(n)（已有序）
  • 最坏/平均：O(n²)
• 空间：O(1)
• 稳定性：稳定

2. 希尔排序（Shell Sort）

原理：

1. 按增量分组，每组插入排序。
2. 逐步缩小增量至1。

复杂度：

• 时间：O(n^1.3)（依赖增量序列）
• 空间：O(1)
• 稳定性：不稳定

---

四、归并排序（Merge Sort）

原理：

1. 递归分治，将数组分成两半。
2. 合并两个有序子数组。

复杂度：

• 时间：O(n log n)（所有情况）
• 空间：O(n)（需额外存储合并结果）
• 稳定性：稳定

---

五、分配排序（Distribution Sort）

1. 计数排序（Counting Sort）

原理：

1. 统计元素出现次数，按计数填充结果数组。

复杂度：

• 时间：O(n + k)（k为数据范围）
• 空间：O(n + k)
• 稳定性：稳定

2. 桶排序（Bucket Sort）

原理：

1. 将元素分配到桶中，对每个桶单独排序。

复杂度：

• 时间：
  • 最好：O(n)（均匀分布）
  • 最坏：O(n²)（所有元素集中在一个桶）
• 空间：O(n + k)
• 稳定性：稳定

3. 基数排序（Radix Sort）

原理：

1. 按位数从低到高（或相反）依次排序（通常用计数排序作为子算法）。

复杂度：

• 时间：O(d(n + k))（d为最大位数）
• 空间：O(n + k)
• 稳定性：稳定

---

完整对比表

---

关键总结

1. 时间复杂度最优：
   • O(n log n)：堆排序、快速排序、归并排序。
   • O(n)：桶排序（均匀分布时）、基数排序（d较小时）。
2. 空间复杂度最优：
   • O(1)：简单选择、堆排序、插入排序、希尔排序、冒泡排序。
3. 稳定性需求：
   • 稳定算法：冒泡、插入、归并、计数、桶排序、基数排序。
4. 适用场景：
   • 大规模数据：快速排序（平均高效）、堆排序（避免最坏情况）。
   • 小规模或近乎有序：插入排序、冒泡排序。
   • 非比较排序：计数/桶/基数排序（数据范围有限时极快）。