Re: [問題] 排序演算法問題請教
※ 引述《fjf1980 (聽說 侯佩岑是豬頭)》之銘言：
: for internal sorting algorithm:selection sort, insertion sort, bubble sort,
: and quick sort.
: which method runs faster for a file in reverse order?
: 答案是Quick sort,
: 我的疑問：
: reverse order對Quick sort是worst case, O(N平方)
: selection sort的O(N平方),且selection sort交換固定是n-1次
: 我本來答案寫selction sort, 不懂為何正確答案要選Quick sort,
: 還請高手指教！！ 感謝！
Quicksort 的實作其實有很多種，
有些版本固定會拿第一個元素當作 pivot，
也有些版本選擇中間的元素，
甚至也有隨機選 pivot，和選九個元素的中位數作 pivot 的版本。
在以上所提版本中，
只有選擇第一個(或是最後一個)作 pivot 的版本，
reverse order 才會是 worst case。
假設題目真是這個意思，那毫無疑問，
Quicksort 的 average case 時間複雜度確實就是較低。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
推
02/27 19:47, , 1F
02/27 19:47, 1F
→
02/27 19:48, , 2F
02/27 19:48, 2F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
