algorithm - 快速排序决策树

Question

我刚刚花了几个小时试图在一组元素上表示快速排序算法的决策树（我还搜索了网络）。我想知道每个节点实际代表什么。是两组之间的比较（由对Partition的调用产生）吗？还是只是集合中两个元素之间的比较？我希望我的问题足够清楚。

Answer 1

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