8种排序算法速记

排序算法的稳定性

排序算法的稳定性是指两个相等的元素在排序前后其相对位置是不变的。而与时间复杂度没有直接关系，所以要注意区分相关的概念。
稳定:冒(冒泡排序)直(直接插入排序)归(归并排序)基(基数排序，不常用)
不稳定:选(选择排序)希(希尔排序)快(快速排序)堆(堆排序)

常见的6种排序算法的平均时间复杂度分析

冒n2直n2
归nlog2n
选n2快nlog2n
堆nlog2n

归并，选择排序，堆排序，由于平均最差相同，所以初始顺序不影响其排序复杂度选择

直接插入，归并，快排，堆有关
冒泡，选择无关

冒泡n最好直接插入n最好
快排n2最差

只有快排的空间复杂度，和堆排序的空间复杂度比较多堆排序需要额外的辅助空间n
快排的空间复杂度，如果就地快排1
使用递归平均是logn，最差情况，退化成冒泡是n

上图有错:快排的空间复杂度，如果就地快排1
使用递归平均是logn，最差情况，退化成冒泡是n

最后编辑于：2017.12.05 16:40:52

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。