1

我想知道是否有人可以帮助我了解如何为递归排序创建决策树。我了解如何使用冒泡排序或插入排序来做到这一点。但是，当涉及到递归排序时，我无法想象。如果伪代码类似于：

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

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

谢谢你能给我的任何指示。

4

2 回答 2

0

（这是作业吗？）

再看看你的代码！您目前正在if-then-else构造内部进行双向分支。解决这个问题，你应该得到一个正确的结果。

此外，您正在那里展开调用堆栈，因此返回将“更正确”。维基百科可能会让您了解它是如何工作的。

祝你好运！

于 2011-07-10T04:39:41.287 回答
0

根据您的陈述，结果将是这样的：

                            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 --swap-> A:B,C --sort-> A,B,C 或 A,C,B。

我希望它对你有帮助。

于 2011-07-10T04:55:33.847 回答