数据结构与算法 · 主观题 · 第 63 题
计算机基础面试八股 · 第 63 题
比较冒泡、插入、选择、归并、快速、堆排序的时间复杂度、空间复杂度和稳定性,并说明实际工程中如何选用。
参考答案
1. 冒泡:平均和最坏 O(n²),最好 O(n)(带提前结束标记),空间 O(1),稳定。
2. 插入:平均和最坏 O(n²),最好 O(n),空间 O(1),稳定;数据近乎有序或规模小时很快。
3. 选择:始终 O(n²),空间 O(1),不稳定。
4. 归并:始终 O(n log n),空间 O(n),稳定;适合链表排序和外部排序。
5. 快速:平均 O(n log n),最坏 O(n²),递归栈平均 O(log n),不稳定;常数小,实际最快。
6. 堆:始终 O(n log n),空间 O(1),不稳定;适合 Top K。
7. 工程选用:标准库多用混合算法。Java 对基本类型用双轴快排,对对象用 TimSort(归并 + 插入,稳定);C++ 的 std::sort 用 introsort(快排 + 堆排 + 插入)防止退化。小数组切换到插入排序。
解析
表格式作答最清楚,稳定性和最坏情况是常被追问的点。