标签：总结 归并 八大 复杂度 基于 空间 logN 排序
基于比较的排序 时间复杂度 空间复杂度 稳定性
选择排序 O(N^2) O(1) 无
冒泡排序 O(N^2) O(1) 有
插入排序 O(N^2) O(1) 有
归并排序 O(N*logN) O(N) 有
随机快排 O(N*logN) O(logN) 无
堆排序 O(N*logN) O(1) 无
不基于比较的排序 时间复杂度 空间复杂度 稳定性
计数排序 O(N) O(M) 有
基数排序 O(N) O(N) 有
不基于比较的排序，对样本数据有严格要求，不易改写
基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
基于比较的排序，时间复杂度极限为O(N*logN)
时间复杂度O(N*logN)，空间复杂度低于O(N)，且稳定的基于比较的排序是不存在的
一般情况下：
为了绝对的速度选择快排，为了省空间选则堆排，为了稳定性选择归并
归并排序的额外的空间复杂度可以为O(1),可以用归并排序 内部缓存法，但是会变得不再稳定，
所以考虑直接用堆排序
原地归并排序不太行，虽然额外空间复杂度为O(1) , 但是会让时间复杂度变为O(N*2)，
所以考虑直接用插入排序
快速排序稳定性改进，"O1 stable sort" , 但是会对样本数据要求更多
标签：总结,
归并,
八大,
复杂度,
基于,
空间,
logN,
排序
From： https://blog.csdn.net/2401_83010439/article/details/141473054