思想方法与思考过程：
快速排序对主元的划分决定了其运行时间，如果最坏是Ο(nlgn)，那么就不允许出现极端划分情况。因为我们学习了最坏时间了线性的选择算法，我们何不利用其每次选择都选中位数作为主元的方法来避免极端情况的发生？既然每次都选择中位数作为主元，那么其递归运行时间总是T(n)=2T(n/2)+Ο(n) 这样根据主方法case 2 知道T(n)=Ο(nlgn)。快速排序对主元的划分决定了其运行时间，如果最坏是Ο(nlgn)，那么
阅读背景：
最坏情况快速排序的运行时间为Ο(nlgn)的算法
来源：互联网
分享到：
