具有递归排序算法的决策树
我想知道是否有人可以帮助我理解如何创建递归排序的决策树。我知道如何使用冒泡排序或插入排序来做到这一点。但是，当涉及到递归排序时，我无法想象它。如果伪代码类似于：
if length == 1
return;
else
int elem = head of array;
array tail = tail of array;
recursive sort;
if (elem <= head of sorted list)
add elem to the beginning of sorted list
else
swap elem and first element of sorted list
sort smaller list again
add elem to the beginning of sorted list
return
我最初的想法是决策树将如下所示：
A, B, C
yes / \ no is length <= 1?
/ \
remove head
/ \
A B, C
yes / \ no is length <= 1?
/ \
remove head
/ \
B C
yes / \ no is length <= 1?
/ \
B:C
/ \
B,C C,B
| |
A:B,C A:C,B
/ \ / \
A,B,C B:A,C A,C,B C:A,B
/ \ / \
B,A,C A:B,C C,A,B A:C,B
我显然在某个地方出错了，我只是不太确定在哪里。我走在正确的轨道上吗？
感谢您能给我的任何指点。
I was wondering if someone can help me understand how to create a decision tree for a recursive sort. I understand how to do it with, say, bubble sort or insertion sort. When it comes to a recursive sort, though, I just can't picture it. If the pseudo-code is something like:
if length == 1
return;
else
int elem = head of array;
array tail = tail of array;
recursive sort;
if (elem <= head of sorted list)
add elem to the beginning of sorted list
else
swap elem and first element of sorted list
sort smaller list again
add elem to the beginning of sorted list
return
My initial thought is that the decision tree would look like the following:
A, B, C
yes / \ no is length <= 1?
/ \
remove head
/ \
A B, C
yes / \ no is length <= 1?
/ \
remove head
/ \
B C
yes / \ no is length <= 1?
/ \
B:C
/ \
B,C C,B
| |
A:B,C A:C,B
/ \ / \
A,B,C B:A,C A,C,B C:A,B
/ \ / \
B,A,C A:B,C C,A,B A:C,B
I am obviously going wrong somewhere, I'm just not quite sure where. Am I on the right track here?
Thank you for any pointers you can give me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
（这是作业吗？）
再看看你的代码！您当前正在
if-then-else构造内双向分支。解决这个问题，您应该会得到一个正确的结果。另外，您正在那里展开调用堆栈，因此返回会“更正确”。 维基百科可能会让您了解其工作原理。
祝你好运！
(Is this homework?)
Look at your code again! You're currently branching both ways inside the
if-then-elseconstruct. Fix that and you should get a single correct result.Also, you're unwinding the call stack down there, so going back up would be "more correct". Wikipedia might give you an idea of how this works.
Good luck!
按照您的表述，结果将如下所示：
在最后一步中，您决定是否需要交换或对左侧的两个进行排序。如果是，则无需继续排序，因为右侧已排序，如果不是，则首先交换最左边的元素，然后对右侧的两个元素进行排序。
例如，B:A,C --交换-> A:B,C --排序-> A、B、C 或 A、C、B。
我希望它对你有帮助。
Following your representation, the result would be something like this:
In the last step, you decide if swapping is needed or the two at the left side are sorted. If they are, there's no need to keep sorting since the right side is sorted, if they're not, you first swap the leftmost elements, and sort the two at the right.
e.g., B:A,C --swap-> A:B,C --sort-> A,B,C or A,C,B.
I hope it helps you.