常用排序算法的时间复杂度
1. 常用排序算法时间复杂度
以下列出常见排序算法及其时间复杂度，涵盖比较排序和非比较排序。
(1) 比较排序算法
| 算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|---|---|
| 冒泡排序 | ( O(n) ) | ( O(n^2) ) | ( O(n^2) ) | ( O(1) ) | 稳定 | 简单，适合小数据集 |
| 选择排序 | ( O(n^2) ) | ( O(n^2) ) | ( O(n^2) ) | ( O(1) ) | 不稳定 | 原地排序，比较多 |
| 插入排序 | ( O(n) ) | ( O(n^2) ) | ( O(n^2) ) | ( O(1) ) | 稳定 | 适合部分有序数据 |
| 快速排序 | ( O(n \log n) ) | ( O(n \log n) ) | ( O(n^2) ) | ( 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) ) | ( O(n^{1.3}) ) | ( O(n^2) ) | ( O(1) ) | 不稳定 | 插入排序改进 |
(2) 非比较排序算法
| 算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|---|---|
| 计数排序 | ( O(n+k) ) | ( O(n+k) ) | ( O(n+k) ) | ( O(k) ) | 稳定 | 适合小范围整数，( k ) 为值范围 |
| 桶排序 | ( O(n) ) | ( O(n+k) ) | ( O(n^2) ) | ( O(n+k) ) | 稳定 | 依赖均匀分布，( k ) 为桶数 |
| 基数排序 | ( O(n \cdot d) ) | ( O(n \cdot d) ) | ( O(n \cdot d) ) | ( O(n+d) ) | 稳定 | 适合多位数，( d ) 为位数 |
2. 算法详解
(1) 冒泡排序（Bubble Sort）
- 原理：
- 相邻元素比较交换，大的“冒泡”到末尾，每轮确定一个最大值。
- 时间复杂度：
- 最佳：( O(n) )（已排序，提前退出）。
- 平均/最坏：( O(n^2) )（多次比较和交换）。
- 适用：
- 小数据集或教学。
(2) 选择排序（Selection Sort）
- 原理：
- 每轮从未排序部分选最小值，放到已排序部分。
- 时间复杂度：
- 始终 ( O(n^2) )（需扫描全部）。
- 适用：
- 交换次数少，适合写操作昂贵场景。
(3) 插入排序（Insertion Sort）
- 原理：
- 将元素插入已排序部分，逐步构建有序序列。
- 时间复杂度：
- 最佳：( O(n) )（近乎有序）。
- 平均/最坏：( O(n^2) )（多次移动）。
- 适用：
- 小数据集或部分有序。
(4) 快速排序（Quick Sort）
- 原理：
- 选基准（pivot），分区后递归排序。
- 时间复杂度：
- 最佳/平均：( O(n \log n) )（均匀划分）。
- 最坏：( O(n^2) )（有序或重复数据）。
- 适用：
- 通用高效，内存占用小。
(5) 归并排序（Merge Sort）
- 原理：
- 分治法，递归拆分后合并有序子序列。
- 时间复杂度：
- 始终 ( O(n \log n) )（稳定划分和合并）。
- 适用：
- 大数据，需稳定排序。
(6) 堆排序（Heap Sort）
- 原理：
- 构建最大/最小堆，逐步调整堆。
- 时间复杂度：
- 始终 ( O(n \log n) )（建堆 ( O(n) )，调整 ( O(n \log n) )）。
- 适用：
- 大数据集，无需额外空间。
(7) 希尔排序（Shell Sort）
- 原理：
- 插入排序的改进，按增量分组排序，逐步缩小增量。
- 时间复杂度：
- 依赖增量序列，平均 ( O(n^{1.3}) )，最坏 ( O(n^2) )。
- 适用：
- 中等数据集，性能介于简单和高级算法。
(8) 计数排序（Counting Sort）
- 原理：
- 统计每个值的出现次数，重建有序序列。
- 时间复杂度：
- ( O(n+k) )，( k ) 为值范围。
- 适用：
- 小范围整数（如 0-100）。
(9) 桶排序（Bucket Sort）
- 原理：
- 将数据分配到多个桶，桶内排序后合并。
- 时间复杂度：
- 最佳：( O(n) )（均匀分布）。
- 最坏：( O(n^2) )（数据集中）。
- 适用：
- 均匀分布数据。
(10) 基数排序（Radix Sort）
- 原理：
- 按位数逐位排序（从低到高）。
- 时间复杂度：
- ( O(n \cdot d) )，( d ) 为最大位数。
- 适用：
- 多位数或字符串。
3. 选择指南
- 小数据集（n < 100）：
- 冒泡、插入、选择（简单易实现）。
- 大数据集（n > 10^4）：
- 快速排序、归并排序、堆排序（高效）。
- 稳定排序：
- 归并排序、计数排序、基数排序。
- 特定数据：
- 计数排序（小范围整数）、基数排序（多位数）。
- 内存限制：
- 堆排序、选择排序（原地排序）。
4. 面试角度
- 问“时间复杂度”：
- 列举常见算法，提最佳/平均/最坏。
- 问“选择”：
- 根据数据规模、稳定性、内存分析。
- 问“实现”：
- 提供快速排序或归并排序代码：
// 快速排序
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
5. 总结
常用排序算法的 时间复杂度 从 ( O(n^2) )（冒泡、选择、插入）到 ( O(n \log n) )（快速、归并、堆），非比较排序如计数排序可达 ( O(n+k) )。比较排序中，归并和堆排序稳定高效，非比较排序适合特定数据。面试可提复杂度表或场景分析，清晰展示理解。
如果您想深入某算法（如快速排序实现）或有具体场景，请告诉我，我可以进一步优化！