二叉树和快速排序？

Question

我有一个家庭作业，内容如下（不要发火/担心，我不是要你做我的家庭作业）：

编写一个程序，通过使用二叉搜索树的快速排序方法对一组数字进行排序。推荐的实现是使用递归算法。

这是什么意思？以下是我迄今为止的解释，正如我在下面解释的那样，我认为两者都有缺陷：

A. 从​​用户那里获取一组数字（整数或其他）。使用数组上的普通快速排序算法对它们进行快速排序。然后将东西放入二叉搜索树中，使数组的中间元素成为根，等等，完成。

B. 从用户那里获取数字，使用二叉搜索树的标准属性，将它们直接一一放入树中。树已经“排序”了，一切都很好——做得很好。

这就是我困惑的原因。选项“A”完成了作业要求的一切，除了它并没有真正使用二叉树，因为它是在二叉树上的家庭作业，所以它在最后一分钟抛出它。这让我认为预期的练习不可能是“A”，因为主要主题不是快速排序，而是二叉树。

但是选项“B”也好不到哪里去——它根本不使用快速排序！所以，我很困惑。

以下是我的问题：

1. 如果解释是选项'A'，就这么说，我没有问题，谢谢你的时间，再见。

2. 如果解释是选项'B'，为什么在二叉树中插入值的排序方法与快速排序相同？他们不似乎天生就比一个事实，即他们都（在表格我已经学会为止）使用递归分而治之的策略和划分他们的投入在两个类似的其他。

3. 如果解释是别的……我该怎么办？

Answer 1

这是一个非常酷的观察。假设您按照您选择的某种顺序将一系列值插入到二叉搜索树中。有些值将在左子树中结束，有些值将在右子树中结束。具体来说，左子树的值小于根，右子树的值大于根。

现在，假设您正在对相同的元素进行快速排序，只是您使用 BST 根中的值作为主元。然后将一堆元素放入左子数组 - 小于主元的元素 - 将一堆元素放入右子数组 - 大于主元的元素。请注意，BST 的左子树和右子树中的元素将与第一个快速排序步骤的左子数组和右子数组中的元素完美对应！

当您将东西放入 BST 时，在将元素与根进行比较之后，您将下降到左子树或右子树并与那里的根进行比较。在快速排序中，将数组划分为左右子数组后，您将为左侧选择一个主元并对其进行分区，然后选择右侧的一个主元并对其进行分区。同样，这里有一个很好的对应关系——整个 BST 中的每个子树都对应于使用子树的根在快速排序中执行一个枢轴步骤，然后在左右子树中递归地执行相同的操作。

更进一步，我们得到以下声明：

每次快速排序运行对应一个 BST，其中根是初始主元，每个左右子树对应于适当子数组中的快速排序递归调用。

这种联系非常牢固：在将元素插入 BST 时，将在该快速排序运行中进行的每一次比较，反之亦然。比较不是按相同的顺序进行的，但仍然进行了比较。

所以我怀疑你的老师要求你做的是以不同的方式实现快速排序：而不是对数组和枢轴进行操作，而是按照你想要的任何顺序将所有东西都扔到 BST 中，然后用中序遍历以按排序顺序取回元素。

这样做的一个非常酷的结果是，您可以将快速排序视为本质上是二叉树排序的空间优化实现。分区和旋转步骤对应于构建左子树和右子树，不需要显式指针。