脚本宝典收集整理的这篇文章主要介绍了

Java数据结构与算法——排序(基础概念)

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。

前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。在介绍各类排序算法之前,本篇先聊聊算法中的一些必备知识。

0、排序算法索引(待更)

Java数据结构与算法——桶排序
Java数据结构与算法——快速排序

1、时间复杂度

算法的时间复杂度是一个函数,其定量的描述了一个算法运行时间和输入规模之间的关系。通常用O表示,且不包括这个函数的低阶和首项系数。如果一个算法的执行时间为2n^2+5n+4,那么该算法时间复杂度就可以表示为O(n^2)。

一般的时间复杂度,由好到坏大概有这么几种O(1)、O(logn)、O(n)、O(nlogn)、O(n^k)(k>=2),一般情况下,当算法时间复杂度高于O(n^2)时,性能就变得相当差,此时就该想办法寻求更优的方案。


O(n^2)的情形

    for(int i=0;i<n;i++){         //code...         for(int j=0;j<n;j++){             //code...         }     }

O(nlogn)的情形

    for(int i=0;i<n;i++){         //code...         for(int j=i;j<n;j++){             //code...         }     }

O(logn)的情形

    for(int i=0;i<n;i+=2){         //code...     }

O(1)的情形

    //与n无关的有限次的表达式,例如赋值,简单的运算等

2、空间复杂度

空间复杂度是一个算法执行过程中所消耗的临时空间的一个度量。同时间复杂度一样,也不包括这个度量函数的低阶项和首项系数。相对的应的,空间复杂度也有O(1)、O(logn)、O(n)、O(nlogn)、O(n^k)(k>=2)。

3、稳定性

在排序算法中,评估一个算法的优劣,除了时间复杂度和空间复杂度以外,还有一个衡量指标就是稳定性。在一个待排序的序列中,可能存在多个相等的项,经过排序后如果这些项的相对次序保持不变,则我们说这个算法是稳定的,否则就是不稳定的。

研究稳定性的意义在于,如果算法是稳定的,那么第一个元素排序的结果可以被第二个等值的元素在排序时所用,也就是说可以避免多余的比较。

4、总结

在介绍排序算法之前,本篇先对后面排序算法的基本概念说叨说叨,打下一个基础铺垫。

排序算法索引(待更)
Java数据结构与算法——桶排序
Java数据结构与算法——快速排序
码字不易,如对您有帮助,欢迎点赞收藏打赏^_^

总结

以上是脚本宝典为你收集整理的

Java数据结构与算法——排序(基础概念)

全部内容,希望文章能够帮你解决

Java数据结构与算法——排序(基础概念)

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过