排序算法是将元素按特定顺序（通常是升序或降序）排列的基本过程。本页面涵盖了 Hello Algo 仓库中各种排序算法的原理、实现和计算效率。有关搜索算法，请参阅 搜索算法。
排序是计算机科学中最常见的操作之一，并且是许多其他算法的基础。排序算法以元素集合作为输入，并将其重新排列成某种顺序，最常见的是数值顺序或字典顺序。
来源： docs/chapter_computational_complexity/time_complexity.md1096-1183
排序算法可以根据各种属性进行分类
来源： docs/chapter_computational_complexity/time_complexity.md1096-1183
冒泡排序是一种最简单的排序算法，它重复地遍历列表，比较相邻元素，如果它们的顺序不对就交换它们。
算法步骤
时间复杂度
空间复杂度：O(1)
来源： docs/chapter_computational_complexity/time_complexity.md1112-1118 docs/chapter_sorting/bubble_sort.md1-5
快速排序是一种高效的“分而治之”的排序算法，它通过选择一个“枢轴”元素并将数组围绕该枢轴进行分区来实现。
算法步骤
时间复杂度
空间复杂度：O(log n)（由于递归栈）
来源： docs/chapter_sorting/quick_sort.md1-7
堆排序利用堆数据结构的特性高效地对元素进行排序。
算法步骤
时间复杂度：所有情况均为 O(n log n) 空间复杂度：O(1)
来源： docs/chapter_heap/heap.md537-538
归并排序是一种分而治之算法，它将输入数组分成两半，递归地对它们进行排序，然后合并已排序的半部分。
算法步骤
时间复杂度：所有情况均为 O(n log n) 空间复杂度：O(n)
来源： docs/chapter_computational_complexity/time_complexity.md1181-1182
下表总结了不同排序算法的关键特征
| 算法 | 时间复杂度（最佳） | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 是 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) | 是 |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n*k) | 是 |
其中 n 是元素数量，k 是输入范围或数字位数。
来源： docs/chapter_computational_complexity/time_complexity.md1052-1061
下图显示了排序算法中常见时间复杂度的增长率
来源： docs/chapter_computational_complexity/time_complexity.md1065-1072
选择排序算法时，请考虑以下因素
来源： docs/chapter_heap/heap.md537-538 docs/chapter_computational_complexity/time_complexity.md1181-1182
排序算法是许多应用中的基本构建块
排序算法的实际选择通常取决于具体的应用需求、数据特征和系统约束。