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

碳基体

http://weibo.com/tanjiti

 
 
 
 
 

日志

 
 

排序  

2011-05-25 09:50:12|  分类: basic |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

算法复杂度

插入排序

直接插入排序

当插入第i(i>=1)个对象时,前面的V[0],V[1],...,V[i-1]已经排好序,这时,用V[i]的关键码与V[i-1],V[i-2],。。。的关键码比较,找到插入位置时即将V[i]插入,原来位置上的对象向后顺移。

稳定

O(n2)

折半插入排序

稳定

O(n2)

希尔排序

先将整个待排序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序

不稳定

交换排序

Bubble sort

首先比较待排序对象的关键码V[n-2].key 和V[n-1].key,如果逆序则交换;然后对V[n-3].key  和V[n-2].key 做同样处理,重复此过程直到处理完V[0],V[1]

稳定

O(n2)

快速排序

任取待排序对象序列中的某个对象作为基准,按照该对象的关键码大小,将整个对象序列划分为左右两个子序列;左侧子序列中所有对象的关键码都小于或等于基准对象的关键码,右侧子序列中所有对象的关键码都大于基准对象的关键码,基准对象则排在这两个子序列中间,然后分别对这两个子序列重复施行上述方法

不稳定

O(nlog2n)

选择排序

直接选择排序

在一组对象V[i]~V[i-1]中选择具有最小关键码的对象;若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调;在这组对象中剔除这个具有最小关键码的对象,在剩下的对象中V[i+1]~V[n-1]中重复,直到剩余对象只有一个

不稳定

O(n2)

锦标赛排序

首先取得n个对象的关键码,进行两两比较,得到[N/2]个比较的优胜者,作为第一步比较的结果保留下来,然后对[N/2]个对象再进行关键码的两两比较,。。。如此重复,直到选出一个关键码最小的对象为止(winner tree)

稳定

O(nlog2n)

堆排序

根据初始输入数据形成初始堆,通过一个系列的对象交换和重新调整堆进行排序

不稳定

O(nlog2n)

归并排序

稳定

O(nlog2n)

基数排序

多关键字排序

外排序

K路平衡归并

  评论这张
 
阅读(326)| 评论(0)
推荐

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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