排序算法的稳定性及其汇总 链表_各种排序方法的稳定性表格

排序算法的稳定性及其汇总

稳定性

稳定性表示的是一开始这个序号为1的数字1排序以后还是比后面那个序号为2的数字一前面后面的2也是如此

选择排序做不到稳定性，因为看到小的就和前面交换玩意中间刚好和交换的数一样那么位置就乱了所以做不到稳定性

冒泡排序能做到稳定性，因为冒泡排序是一个个下去比较可以选择遇到相同的不进行交换也就是<这个数交换其他不交换就可以了，所以能做到稳定性

插入排序也能做到稳定性，同样交换的时候可以进行选择是否具有稳定性0~0不用变0 ~ 1相同就不进行交换也就是<右边的才进行交换。

归并排序能做到稳定性，根据master的方法来断定是否右稳定性，两边对比相同的话就先赋值左边的数，这样就能做到稳定性。

快排做不到稳定性，如上图5对照等于的话就一直1往下走走到3小于5那就把三和第一个5交换，这样就跨越了中间很多5把位置搞乱了所以不能做到稳定性。

堆排序不能稳定性，因为6和4交换位置就把原来的前面的4变成了最后一个所以不能保证稳定性；
归并空间复杂度较高，具有稳定性
快排常数项最低但是空间复杂度不能做到O(logn)
堆不占空间

常见的坑

综合排序

就是小样本用插入，大样本用快排
一个调度优势，一个小样本常数量低的优势

哈希表

如果是基础类型传递的就是vlue也就是本身
如果不是key传递的就是内存地址一律八字节

不是基础类有序组织必须加上比较器

基础类有序组织key，所有操作哦都是logn级别

单链表

package class_03;
1