作者confess2007 (...)
站内Programming
标题[问题] quick sort最差为O(n^2)有实例吗?
时间Wed Jan 11 16:58:42 2012
网路上google知道quick sort的最差情况是O(n^2)
但都没有实例 不然就是留个问号给读者
可以请问板上高手 到底quick sort的最差情况发生在怎样的阵列呢?
小妹不是资讯人员 若问题太简单请见谅<(_ _)>
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.133.2.197
1F：→ chunhsiang:实务大多是O(n^2) 但理论可以O(nlgn) 114.25.38.46 01/11 17:39
2F：→ chunhsiang:pivot selection 是整个问题的核心 114.25.38.46 01/11 17:43
3F：→ chunhsiang:假设都选阵列第一个当pivot 114.25.38.46 01/11 17:43
4F：→ chunhsiang:这是input array 6, 5, 4, 3, 2, 1 114.25.38.46 01/11 17:45
5F：→ chunhsiang:那他就会退化成SELECTION SORT 114.25.38.46 01/11 17:46
6F：→ confess2007:所以排序好资料 且pivot选第一个 220.133.2.197 01/11 21:35
7F：→ confess2007:情况最差....感谢c大^^ 220.133.2.197 01/11 21:35
8F：推 yauhh:排序好的资料即为实例 49.215.94.7 01/12 08:40