快速排序決策樹

Question

我剛花了幾個小時試圖在一組元素上表示quicksort算法的決策樹（我也搜索了網頁）。我想知道每個節點實際代表什麼。它是兩組之間的比較（由於致電分區）？或者僅僅是集合中兩個元素之間的比較？ 我希望我的問題很清楚。

Answer 1

這取決於你想要做出決定。由於唯一可以產生不同結果的是主元素的選擇，我認爲樹中的每個邊都是這樣的選擇。因此節點是部分分區的數組，具有尚未排序區間的標記。換句話說，除了每個節點中的數組外，還需要一個樞軸索引列表。