作者chucheng (时间太少事情太多)
看板Programming
标题Re: [问题] quick sort最差为O(n^2)有实例吗?
时间Wed Jan 11 17:27:36 2012
※ 引述《confess2007 (...)》之铭言：
: 网路上google知道quick sort的最差情况是O(n^2)
: 但都没有实例 不然就是留个问号给读者
: 可以请问板上高手 到底quick sort的最差情况发生在怎样的阵列呢?
: 小妹不是资讯人员 若问题太简单请见谅<(_ _)>
quick sort 分为二个steps
(1) Pick a pivot
(2) Left of pivot < Right of pivot
Worst case发生在pivot刚好每次都挑到最小或最大
基本上pivot的挑法有很多，假使PIVOT你都选第1 个
这样的话
9 8 7 6 5 .... 1 --> 排序时就会刚好n^2
如果你pivot选择是中间，那上面就不会有问题
你可以参考
http://bit.ly/xJiSXZ
因此通常PIVOT是选中间位置的数，而不选第一或最後一个数
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 76.169.69.1
1F：推 confess2007:感谢大大 哇~原文的耶...很详细 220.133.2.197 01/11 21:39