我刚刚花了几个小时试图在一组元素上表示快速排序算法的决策树(我还搜索了网络)。我想知道每个节点实际代表什么。它是两组之间的比较(由调用 Partition 产生)吗？或者只是集合中两个元素之间的比较？ 我希望我的问题足够清楚。
最佳答案
这取决于你想称呼什么为决定。由于唯一可能有不同结果的是枢轴元素的选择，我认为树中的每条边都是这样的选择。因此，一个节点是一个部分分区的数组，带有尚未排序的间隔标记。换句话说，除了每个节点中的数组之外，您还需要一个枢轴索引列表。
关于algorithm - 快速排序决策树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3972370/