最快最稳定的排序算法
终极管理员 知识笔记 118阅读
各排序算法的稳定性是什么？
答：各排序算法的稳定性：. 1、堆排序、快速排序、希尔排序、直接选择排序 不是稳定 的排序算法；. 2、基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序 是稳定 的排序算法。. 一. 冒泡排序. 1、小的元素往前调或者把大的元素往后调；. 2、比较是相邻的两个元素比较，交换也发生在这两个元素之间；. 3、 稳定排序算法。. 二.
排序算法最优的时间复杂度是什么？
答：排序算法最优的时间复杂度：线性对数阶O(nlogn) 对应的排序算法有：堆排序、归并排序、快速排序（最好平均） 这或许是东半球讲十大排序算法最好的一篇文章 程序员吴师兄的博客
如何使用排序算法对序列进行排序？
答：如果使用某个排序算法对序列进行排序，得到的有序序列是： 红 2 依然位于绿 2 的左侧，这个排序算法就是稳定的；反之，如果红 2 和绿 2 的相对位置发生了改变，这个排序算法就是不稳定的。 通过优化代码、改进实现思路等方式，某些 "不稳定" 的算法也可以变得 "稳定"。 以桶排序算法为例，如果保证各个桶内存储相同元素时不改变它们的相对位置，且桶内排序时采用稳定的排序算法，那么桶排序算法就可以变得“稳定”。 除了稳定性，某些场景中还需要使用就地排序算法。 “就地排序”的含义是：排序算法在排序过程中，主要使用待排序序列占用的内存空间，最多额外创建几个辅助变量，不再申请过多的辅助空间。
归并排序算法为什么这么快？
答：这个算法之所以快，是因为它充分利用了现实世界的待排序数据里面，有很多子串是已经排好序的不需要再重新排序，利用这个特性并且加上合适的合并规则可以更加高效的排序剩下的待排序序列。 当Timsort运行在部分排序好的数组里面的时候，需要的比较次数要远小于 n l o g n ，也是远小于相同情况下的归并排序算法需要的比较次数。 但是和其他的归并排序算法一样，最坏情况下的时间复杂度是 O ( n l o g n) 的水平。 但是在最坏的情况下，Timsort需要的临时存储空间只有 n / 2 ，在最好的情况下，需要的额外空间是常数级别的。 从各个方面都能够击败需要 O ( n) 空间和稳定 O ( n l o g n) 时间的归并算法。 OK！