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

伯纳乌の夢

可以挽回么?我们按“ Ctrl+Z”撤销掉吧。对不起啦~~

 
 
 

日志

 
 
 
 

排序的认识  

2008-11-25 21:43:07|  分类: 数据结构与算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

排序总的可以分为插入排序交换排序选择排序归并排序基数排序等。


其中插入排序又可以细分为直接插入排序折半排序希尔排序

直接排序的基本思想是:当插入第i i>=1)个对象时,前面的v[0]v[1],…….v[i-1]已经排好序,这时,用v[i]的关键码与v[i-1],v[i-2]……的关键码顺序进行比较,找到插入位置即将v[i]插入,原来位置上的对象向后顺移。直接插入排序的时间复杂度为n2,直接插入排序是一种稳定的排序方法。

折半排序的基本思想是:设在顺序表中有一个对象序列v[0]v[1],….v[n-1],其中,v[0]v[1],….v[i-1]是已经排好序的对象。在插入v[i]时,利用折半查找法寻找v[i]的插入位置。折半插入是一种稳定的排序方法。

希尔排序:当待排序的数列很长时,(即n很大时),关键码平均比较次数和对象平均移动次数大约在n1.25(即n1.25次方,以下同样)到1.6n1.25范围内。


交换排序又可细分为冒泡排序快速排序

冒泡排序的基本思想是:设待排序的数列的大小为n,首先比较v[n-2]v[n-1]的大小,如果v[n-2]>v[n-1],则交换v[n-2]v[n-1],然后对v[n-2]v[n-3]作相同的处理,如此处理, 直到处理完v[0]v[1],这个称为一趟冒泡,所以只要经过n-1 趟冒泡就可以排好所有对象。 在最坏情况下总的关键码比较次数为0.5n(n-1),对象移动次数为1.5nn-1

快速排序的基本思想是:取待排序的数列的某个对象(例如第一个对象)作为基准,将对象分为左右两个数列,左边的全都小于基准,右边的全都大于基准,然后对左右两个树列重复以上操作,直到全部完成。它是一种不稳定的方法,对于待排序的数列很大时,快速排序的确很快,但当待排序的数列很小时,它往往比其它简单的排序方法还要慢。


选择排序又可以细分为直接选择排序堆排序

直接选择排序的最坏情况是每一趟都要进行交换,总的对象移动次数是3(n-1)

堆排序可以分为两个步骤:首先,根据初始输入数据,利用堆的调整算法FilterDown()形成初始堆, 第二步通过一系列的对象交换和重新调整堆进行排序。堆排序的是一个不稳定的排序方法,并且当待排序的数列很大时,堆排序不可取。


归并排序就是将两个或两个以上的有序表合并成一个新的有序表。


基数排序的基本思想是:待排序的对象按m个关键码key[0],…..key[m-1]排序,每个对象的关键码域用一个数组key[m]表示,对各关键码的排序采用箱排序。


从上面可以得出结论(本人观点),当待排序的数列很小时,可以采取直接插入排序,折半排序,希尔排序,直接选择排序,堆排序,归并排序,基数排序等众多排序方法,但当待排序的数列很大时,采用快速排序为优。


就平均性能而言,我认为快速排序最好。

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

历史上的今天

评论

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

页脚

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