数据结构面试之十二——排序3(排序算法归类、排序时间、空间复杂度、稳定性总结)

题注:《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。


十一、数据结构面试之十二——排序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)


稳定


上一篇:理解常见的算法时间复杂度


下一篇:《Java 7程序设计入门经典》一2.13 使用强制类型转换