快速排序决策树
我刚刚花了几个小时尝试在一组元素上表示快速排序算法的决策树（我还搜索了网络）。我想知道每个节点实际上代表什么。是两个集合之间的比较（由调用 Partition 产生）吗？或者只是集合中两个元素之间的比较？ 我希望我的问题足够清楚。
I have just spent a couple of hours trying to represent the decision tree for the quicksort algorithm on a set of elements (and I also searched the web). I would like to know what each node actually represents. Is it the comparison between two sets (resulting from the call to Partition)? or just the comparison between two elements of the set?
I hope that my question is clear enough.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这取决于您想要称之为决定的内容。由于唯一可能产生不同结果的是枢轴元素的选择，因此我认为树中的每个边都是这样的选择。因此，节点是部分分区的数组，带有尚未排序的间隔标记。换句话说，除了每个节点中的数组之外，您还需要一个主元索引列表。
It depends on what you want to call a decision. Since the only thing that can have different outcome is the choice of pivot element, I think that each edge in your tree is such a choice. A node is thus a partially partitioned array, with marks for the intervals yet to be sorted. In other words, you need a list of pivot indices in addition to the array in each node.