快速排序决策树

Question

我刚花了几个小时试图在一组元素上表示quicksort算法的决策树（我也搜索了网页）。我想知道每个节点实际代表什么。它是两组之间的比较（由于致电分区）？或者仅仅是集合中两个元素之间的比较？ 我希望我的问题很清楚。

Answer 1

这取决于你想要做出决定。由于唯一可以产生不同结果的是主元素的选择，我认为树中的每个边都是这样的选择。因此节点是部分分区的数组，具有尚未排序区间的标记。换句话说，除了每个节点中的数组外，还需要一个枢轴索引列表。