問題詳情

1. 以下演算法何者可包含隨機化(Randomization)的過程？
(A)二元搜尋法(Binary Search)
(B)克魯斯克爾演算法(Kruskal's Algorithm)
(C)快速排序法(Quick Sort)
(D)內插搜尋法(Interpolation Search)

參考答案

答案：C
難度：計算中-1
書單：沒有書單，新增

用户評論

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】快速排序 (Quick Sort) 的想法是說，先找一個基準點，然後派兩個代理人分別從資料的兩邊開始往中間找，如果右邊找到一個值比基準點小，左邊找到一個值比基準點大，就讓他們互換。反覆找並互換，直到兩個人相遇。然後再將相遇的點跟基準點互換。第一輪結束。原始狀態： 基準點 + 一堆資料......第一輪後的狀態： 比基準點小的資料 ＋ 基準點 ＋ 比基準點大的資料接下來再分別從兩邊資料做子循環，但做法跟上面一樣，這就用到了遞迴的概念。較小資料： (小)基準點 + 小資料 --> 小小資料 + (小)基準點 + 小大資料較大資料： (大)基準點 + 大資料 --> 大小資料 + (大)基準點 + 大大資料接下來就重複以上的動作，直到排列完畢。

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】快速排序 (Quick Sort) 的想法是說，先找一個基準點，然後派兩個代理人分別從資料的兩邊開始往中間找，如果右邊找到一個值比基準點小，左邊找到一個值比基準點大，就讓他們互換。反覆找並互換，直到兩個人相遇。然後再將相遇的點跟基準點互換。第一輪結束。原始狀態： 基準點 + 一堆資料......第一輪後的狀態： 比基準點小的資料 ＋ 基準點 ＋ 比基準點大的資料接下來再分別從兩邊資料做子循環，但做法跟上面一樣，這就用到了遞迴的概念。較小資料： (小)基準點 + 小資料 --> 小小資料 + (小)基準點 + 小大資料較大資料： (大)基準點 + 大資料 --> 大小資料 + (大)基準點 + 大大資料接下來就重複以上的動作，直到排列完畢。