注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

在路上...

点滴感悟,成长记录...

 
 
 

日志

 
 

【Reading】关于排序算法  

2012-02-12 17:27:11|  分类: Reading |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

以前一直搞不大明白这些排序算法是咋回事,总觉得排序算法太多太杂,记起来比较费力。今天通过看MIT的《算法导论》视频课这个博客的两篇博文,终于对这些排序算法有了一个新的认识,下面简单记录一下。

1、排序算法分类,按平均时间复杂度将排序分为四类
(1)平方阶(O(n2))排序
 一般称为简单排序,例如直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlgn))排序

 如快速、堆和归并排序;
(3)O(n1+£)阶排序

 £是介于0和1之间的常数,即0<£<1,如希尔排序;
(4)线性阶(O(n))排序

 如桶、箱和基数排序。

2、各种排序算法的理解

(1)简单排序就是不借助辅助存储空间,也就是原地排序,不使用分治策略,而仅仅依次交换两个元素,所以是一种很朴素很原始的方法。自然,其效率很低,时间复杂度比较高,是平方级的。

(2)对数阶排序算法的一个共同点就是都使用了分治策略,进行递归运算,故它们可以把时间复杂度降低至对数阶。而这里面堆排序和归并排序还需要借助于辅助空间,所以它们的时间复杂度在最坏情况下依然是对数阶的。而快速排序,最初的朴素快速排序由于定点选取某个元素为主元,所以受制于原始序列的影响,以至于当原始序列已经是排好序的情况下,该算法会退化为简单排序,复杂度降为平方级,这也就是所说的最坏情况。后来改进的随机化快速排序算法,随机选取主元,这样就摆脱了原始序列带来的限制,从而不管原始序列是什么样,都可以达到对数阶的复杂度。最重要的一点,快速排序也是一种原地排序,相对于堆排序和归并排序来说,它在空间复杂度上又取得了优势,我想,这也许就是“快速”一词的根源吧!

(3)希尔排序是对插入排序的改进,主要体现在步长的不断改变,而不是插入排序那种只有步长为1.

(4)线性级的几个算法不熟悉,等看完视频课再说吧,haha...

  评论这张
 
阅读(114)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017