6

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

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

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

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

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

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

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

以下是我的问题：

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

  2. 如果解释是选项'B'，为什么用于在二叉树中插入值的排序方法与快速排序相同？除了它们（以我目前所学的形式）都使用递归分治策略并将输入分成两部分之外，它们似乎本质上并不相似。

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

4

1 回答 1

8

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

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

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

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

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

这种联系非常紧密：在将元素插入 BST 时，将进行快速排序中的每个比较，反之亦然。比较不是按照相同的顺序进行的，但它们仍然进行。

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

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

于 2017-07-21T19:11:37.127 回答