快速排序

Posted on 2008-10-03 14:10 xan 阅读(172) 评论(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