快速排序分区和二进制搜索树之间是如何一一对应的

Question

如果我们取一些元素，则在第一个元素上对它们进行分区。现在将分区元素作为二叉树的根，我们将这些元素插入二进制中。会有一对一的信件吗？

有人能解释一下元素之间是如何一一对应的吗？？

Answer 1

在未优化的快速排序中，数组的每个元素都作为枢轴出现在一个递归调用中。递归调用树可以看作是一个二进制搜索树。

例如，对3 1 4 5 9 2 6进行排序，^标记每个级别的枢轴(在这种情况下，始终是子阵列的第一个元素(，|标记子阵列之间的边界：

3 1 4 5 9 2 6
^
1 2 | 3 | 4 5 9 6 
^         ^
1 | 2 | 3 | 4 | 5 9 6 
^           ^
1 | 2 | 3 | 4 | 5 | 9 6 
^
1 | 2 | 3 | 4 | 5 | 6 | 9
^
3
/ 
/   
1     4
     
2     5

9
/
6