首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

关于找寻中位数

2012-12-27 
关于寻找中位数?? ?今天无意中看到一篇关于快速排序的文章。毫无疑问,快速排序正如他的名字一样,如果不是一

关于寻找中位数

?? ?今天无意中看到一篇关于快速排序的文章。毫无疑问,快速排序正如他的名字一样,如果不是一些特殊情况(基本有序了,排序项目个数较少),他一般是最快的排序。但是,在快速排序中一般会有一个第一步选取切分值的过程。在快速排序中,这个值我们一般是随机抽取的,或者直接选取最右端或左端的数。但是,快速排序的一个变种是第一步选取这个值为中位数。于是,到了我关心的地方,中位数算法。

?? ? ? 一种流行的方法是基于searchKth()方法的。这种方法的平均复杂度为O(n),实现也比较简单。还有一种是传说中的BFPRT算法,实现复杂,而且复杂度为O(nlgn)。那那些大牛们为什么还要搞个第二种算法呢?原来,第一种算法会退化到n^2,而BFPRT则不会。好吧,明白了。。。。。。。。

热点排行