随笔 - 13  文章 - 36  trackbacks - 0
<2009年10月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(2)

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

                                                                              快速排序算法、计数排序算法
   
                                                                                                               C++博客    Alex-Lee  2009-10-20

      快速排序是分治算法,将数组分为几部分,在各部分内完成排序,递归排序。算法时间复杂度O(nlgn)。这是比较排序算法中速度最快的一个算法了。计数排序、基数排序、桶排序算法是非比较排序算法,他们的算法复杂度是O(n)。快速排序算法在选取支点上要有技巧,最好能达到随即要求。
1,快速排序算法:
普通快速排序

2,改进版本的快速排序(随机分布版本的快速排序)
随机分布快速排序

3,计数排序算法
   计数排序算法是需要知道数组元素的上下限,并且最好是对整数元素排序,计数每个元素的个数,需要占用比较多的空间。
计数排序
4,测试代码
   在测试整数时,1kw整数,快速排序5秒,堆排序20秒,计数排序是0.43秒。
  排序算法代码
posted on 2009-10-20 22:18 Alex-Lee 阅读(1864) 评论(2)  编辑 收藏 引用

FeedBack:
# re: 快速排序算法、计数排序算法 2009-10-21 16:42 tiny
good job!!!  回复  更多评论
  
# re: 快速排序算法、计数排序算法 2009-10-24 09:25 tiny
不过这个改进比较担心。随机数一次多少指令?
首要做的可能是把递归算法改成非递归的。
针对元素低于8个的时候,用插入排序。
下面就是尽可能地让分区平衡。
一个好的快速太难了。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理