十大内排序算法总结比较

发布时间:2020-05-27 00:58:49 作者:汇天下豪杰
来源:网络 阅读:1430

1、最基础排序算法


    时间复杂度
稳定性
冒泡排序      O(n^2)
稳定
选择排序
      O(n^2)不稳定
插入排序      O(n^2)稳定


2、5个中间改良排序算法


时间复杂度稳定性
归并排序
O(nlogn)
稳定
希尔排序
平均O(nlogn),最坏O(n^2)
不稳定
堆排序
O(nlogn)
不稳定
快速排序
平均O(nlogn),最坏O(n^2)不稳定
随机化快排
O(nlogn)不稳定

  (1)、归并、堆、快排是渐进性的最优排序算法(在大规模的数据下尤为体现);

  (2)、解决快排最坏情况的方案:随机化快排,随机选择主元;(与输入无关,就是随机器的概率问题了);

  (3)、以上都是比较模型的排序算法,最快时间复杂度为:O(nlogn);

  (4)、归并排序用并行算法的话,时间复杂度:O(n/logn);


3、3个局限性的排序算法


时间复杂度稳定性
桶排序
O(n)
稳定
计数排序
O(n)稳定
基数排序
O(n)稳定

  (1)、这3个排序算法的时间复杂度都为:O(n),都是稳定性的排序算法;

  (2)、都是以空间换时间为代价的算法,处理数据的规模在较小范围内;

  (3)、无重复数字出现:建议用桶排;

  (4)、有重复数字出现,用计数/基数排序;基数排序是对计数排序的优化,在辅助空间上的优化,基数排序所需辅助空间为:10个该元素空间,计数排序所需辅助空间为:最大数字+1个空间;


4、空间复杂度

  O(n):桶排,计数,基数

  O(logn):归并,快排,递归堆排

  O(1):非递归堆排,希尔





推荐阅读:
  1. 排序算法比较与分析
  2. 统治世界的十大算法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

十大内排序算法总结比较

上一篇:如何从python代码中直接访问Android的Service

下一篇:Android 隐藏功能

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》