Posted on 2008-10-03 14:10
xan 閱讀(189)
評(píng)論(0) 編輯 收藏 所屬分類:
Algorithms
實(shí)踐中最快的已知排序算法, O(NlogN),最壞O(N2)
loop:
1. 如果S中元素個(gè)數(shù)為0或者1,返回
2. 取S中任意元素v為樞紐
3. 將S中余下元素按>v 和 <v分成兩個(gè)不同部分
4. 對(duì)這兩個(gè)部分快速排序
樞紐元選擇:
一般采用S中起始,結(jié)束,中間位置的三個(gè)值的中值為樞紐元 (三數(shù)中值分割法)