几种常见的算法比较

谁践踏了优雅 2021-09-23 03:26 535阅读 0赞

这里写图片描述
排序算法总结：

时间复杂度：

-平方阶O(n2)的排序：各类简单排序、直接插入、直接选择、冒泡排序
- 线性对数O(nlg2n)排序：快速排序、堆排序和归并排序
- O(n1+)排序：为介于0-1之间的常数：希尔排序
- 线性O(n)排序：基数排序、桶排序、箱排序

空间复杂度：

  • 空间复杂度为O(1)：冒泡排序、选择排序、直接插入排序、折半插入排序、希尔排序、堆排序

稳定性：

  • 稳定的排序算法有：冒泡排序、直接插入排序、折半插入排序、归并排序、基数排序和计数排序

特别注意：

  1. 当输入数组有序或者基本有序时，直接插入和冒泡排序将大大减少比较次数和移动次数。时间复杂度降为O(n)。
  2. 快速排序恰恰相反，当输入数组基本有序时，将退化为冒泡排序，时间复杂度增加到O(n2)
  3. 输入数组有序与否对简单排序、堆排序、归并排序、和基数排序的时间复杂度影响不大。

常用算法比较图：
这里写图片描述

原文链接：

https://itimetraveler.github.io/2017/07/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8Ejava%E5%AE%9E%E7%8E%B0/

发表评论

表情：
评论列表 （有 0 条评论，535人围观）

还没有评论，来说两句吧...

相关阅读

    相关 几种常见的加密算法

     一、概念       [数据加密][Link 1]的基本过程就是对原来为明文的文件或数据按某种[算法][Link 2]进行处理，使其成为不可读的一段代码为“密文”，使其

    墨蓝墨蓝/ 0 赞/ 157 阅读

    相关 几种常用加密算法比较

    > 由于计算机软件的非法复制，通信的泄密、数据安全受到威胁，解密及盗版问题日益严重，甚至引发国际争端，所以在信息安全技术中，加密技术占有不可替代的位置，因此对信息加密技术和加密

    Dear 丶Dear 丶/ 0 赞/ 318 阅读

    相关 几种排序算法的稳定性比较

    排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。例如，如果Ai=Aj，原来在位置前，排序后Ai还是要在Aj位置前

    朱雀朱雀/ 0 赞/ 345 阅读

    相关 几种常用加密算法比较

    由于计算机软件的非法复制，通信的泄密、数据安全受到威胁，解密及盗版问题日益严重，甚至引发国际争端，所以在信息安全技术中，[加密][Link 1]技术占有不可替代的位置，因此对信

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 341 阅读

    相关 几种面消隐算法的比较

    【摘 要 】本文就 目前现有面消隐算法进行 了分类，对每类算法特 点进行 了总结。从每种 算法本 身的特点 、消隐空间、排序效率和对场景的限制这几方面 ．重点分析比较 了几种常

    小鱼儿小鱼儿/ 0 赞/ 337 阅读