题注:《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。
十一、数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)
排序算法归类
插入排序类
选择排序类
交换排序类
归并排序类
直接插入排序
希尔排序
直接选择排序
堆排序
冒泡排序
快速排序
归并排序
排序算法汇总:
平均时间复杂度
最好情况
最差情况
空间复杂度
稳定性
直接插入排序
O(n2)
O(n)
O(n2)
O(1)
稳定
冒泡排序
O(n2)
O(n)
O(n2)
O(1)
稳定
直接选择排序
O(n2)
O(n2)
O(n2)
O(1)
不稳定
希尔排序
O(nlogn)~O(n2)
O(n1.3)
O(n2)
O(1)
不稳定
快速排序
O(nlogn)
O(nlogn)
O(n2)
O(logn)
不稳定
堆排序
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
稳定