Java教程

冒泡排序、希尔排序和排序算法大总结03：基于比较的排序算法总结

本文主要是介绍冒泡排序、希尔排序和排序算法大总结03：基于比较的排序算法总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

复杂度总结

7大比较排序算法 时间复杂度 空间复杂度 特殊情况下的优化 应用
选择排序 O(n^2) O(1) \ \
插入排序 O(n^2) O(1) 完全有序数组，O(n) \
冒泡排序 O(n^2) O(1) 完全有序数组，O(n) \
归并排序 O(nlogn) O(n) 完全有序数组，O(n) 求解数组中逆序对个数
快速排序 O(nlogn)* O(1) 元素相同数组，O(n) 求解SelectK、TopK问题
堆排序 O(nlogn) O(1) \ 优先队列求解SelectK、TopK问题
希尔排序 O(nlogn)—O(n^2) O(1) \ 分组的思想

*代表随机算法，其时间复杂度为期望复杂度

排序算法的稳定性

对于有多个属性的元素，当基于某一种属性排序时，如果这个属性相等，那排序后相对位置一定不变，即另一种属性的顺序也不变

因此，如果排序过程中相同的元素会发生“跳跃”的话，就是不稳定

7大比较排序算法 算法稳定性 原因
选择排序 不稳定 元素交换位置的时候，会发生“跳跃”
插入排序 稳定 元素移动，不会发生“跳跃”
冒泡排序 稳定 只比较相邻的元素，不会发生“跳跃”
归并排序 稳定 归并时优先选择前面的元素，不会发生“跳跃”
快速排序 不稳定 随机选择标定点，会发生“跳跃”
堆排序 不稳定 二叉树交换元素，会发生“跳跃”
希尔排序 不稳定 分组后不同组的元素会发生“跳跃”

如果在具体的类中，明确定义了多个属性排序的规则，那么也就不需要考虑排序算法的稳定性了

例如当score相等时，指定按照name进行排序，相对位置就不会发生改变

@Override
public int compareTo(Student another){
    
    if (another.score != this.score){
        return another.score - this.score;
    }
    else {
        return this.name.compareTo(another.name);
    }
}
这篇关于冒泡排序、希尔排序和排序算法大总结03：基于比较的排序算法总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航