一、排序算法的分类
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
二、排序算法的复杂度
为了方便记忆，给出一些记忆规律。
时间复杂度
- 选择排序：都是
- 堆排序、归并排序：都是
- 计数排序：都是
- 基数排序：都是
- 插入排序、冒泡排序：最好是
![]() ，其它情况都是
- 快速排序：最坏是
![]() ，其它情况都是
- 希尔排序：三种情况皆不同。也是插入排序的一种，跟插入排序差不多，但平均复杂度更好些，是
- 桶排序：三种情况皆不同。平均是
![]() ，最坏是
![]() ，最好是
空间复杂度
- 线性排序都是
- 快速排序是：
- 归并排序是：
- 其它都是：
稳定性
- 希、选、快、堆：不稳定。
- 其余：稳定。
原文链接：
十大经典排序算法的复杂度分析_网络_lzzw的学习之路-CSDN博客
如有错误，请更正指出，谢谢！
| 
转播
