作者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