快速排序

Posted on 2008-10-03 14:10 xan 阅读(7) 评论(0)  编辑  收藏 所属分类: Algorithms

实践中最快的已知排序算法, O(NlogN),最坏O(N2)
loop:
1. 如果S中元素个数为0或者1,返回
2. 取S中任意元素v为枢纽
3. 将S中余下元素按>v 和 <v分成两个不同部分
4. 对这两个部分快速排序

枢纽元选择:
一般采用S中起始,结束,中间位置的三个值的中值为枢纽元 (三数中值分割法)


标题  
姓名  
主页
验证码 *  
内容(请不要发表任何与政治相关的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
 
 

相关链接:
网站导航:



posts - 36, comments - 2, trackbacks - 0, articles - 0

Copyright © xan