排序算法对比总结-Python

2018-12-07 本文已影响4人苏啦啦哇咔咔

时间复杂度空间复杂度备注

选择排序（不稳定） $O(n^2)$ $O(1)$ 比较次数与序列初始状态无关

插入排序（稳定） $O(n^2)$ $O(1)$

冒泡排序（稳定） $O(n^2)$ $O(1)$

快速排序（不稳定） $O(nlog_2n) 到 O(n^2)$ $O(log_2n) 到 O(n)$ 逆序时时间复杂度大

合并排序（稳定） $O(nlog_2n)$ $O(n)$ 比较次数与序列初始状态无关

另外还有折半插入排序（稳定）、希尔排序（不稳定）、堆排序（不稳定）和基数排序（稳定）没有在我参考的《数据结构（Python语言描述）》中描述。