递归排序算法的决策树

Question

我想知道如果有人能帮助我理解如何为递归排序创建决策树。我知道如何处理，比如说冒泡排序或插入排序。但是，当涉及到递归排序时，我无法想象它。如果伪代码是一样的东西：

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 

我显然会错了地方，我只是不太确定在哪里。我在正确的轨道上吗？

谢谢你给我的任何指针。

Answer 1

（这是作业？）你的代码

再看看！您目前在if-then-else构建中分支两种方式。解决这个问题，你应该得到一个正确的结果。

此外，你在那里展开调用堆栈，所以回去会更“正确”。 Wikipedia可能会告诉你这是如何工作的。

祝你好运！

Answer 2

按照你的表示，结果会是这样的：

      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 **B,C,A** C,A,B **C,B,A** 

在最后一步，你决定是否需要交换或两个在左侧进行排序。如果是，则不需要继续排序，因为右侧已排序，如果不是，则首先交换最左侧的元素，然后将右侧的两个排序。例如，B：A，C - 开关 - > A：B，C - 排序 - > A，B，C或A，C，B。

我希望它能帮助你。