Re: [問題] quick sort最差為O(n^2)有實例嗎?
※ 引述《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
推
01/11 21:39, , 1F
01/11 21:39, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：