[問題] quick sort最差為O(n^2)有實例嗎?

看板Programming作者 (...)時間12年前 (2012/01/11 16:58), 編輯推噓1(1推 0噓 7→)
留言8則, 3人參與, 最新討論串1/2 (看更多)
網路上google知道quick sort的最差情況是O(n^2) 但都沒有實例 不然就是留個問號給讀者 可以請問板上高手 到底quick sort的最差情況發生在怎樣的陣列呢? 小妹不是資訊人員 若問題太簡單請見諒<(_ _)> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.2.197
→
01/11 17:39, , 1F
實務大多是O(n^2) 但理論可以O(nlgn)
01/11 17:39, 1F
→
01/11 17:43, , 2F
pivot selection 是整個問題的核心
01/11 17:43, 2F
→
01/11 17:43, , 3F
假設都選陣列第一個當pivot
01/11 17:43, 3F
→
01/11 17:45, , 4F
這是input array 6, 5, 4, 3, 2, 1
01/11 17:45, 4F
→
01/11 17:46, , 5F
那他就會退化成SELECTION SORT
01/11 17:46, 5F
→
01/11 21:35, , 6F
所以排序好資料 且pivot選第一個
01/11 21:35, 6F
→
01/11 21:35, , 7F
情況最差....感謝c大^^
01/11 21:35, 7F
推
01/12 08:40, , 8F
排序好的資料即為實例
01/12 08:40, 8F
‣ 更多 confess2007 的文章
文章代碼(AID): #1F3Kz4fk (Programming)
‣ 更多 confess2007 的文章
文章代碼(AID): #1F3Kz4fk (Programming)