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

あなたの表現に続いて、結果は次のようになります：

                            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**

最後のステップでは、スワッピングが必要か、左側の2つをソートするかを決定します。そうである場合は、右側が並べ替えられるため、並べ替えを続ける必要はありません。そうでない場合は、最初に左端の要素を入れ替えて、右側の2つを並べ替えます。

例：B：A、C --swap-> A：B、C --sort-> A、B、CまたはA、C、B。

お役に立てば幸いです。

于 2011-07-10T04:55:33.847 に答える
0

（これは宿題ですか？）

コードをもう一度見てください。if-then-else現在、コンストラクト内で双方向に分岐しています。それを修正すると、単一の正しい結果が得られるはずです。

また、コールスタックを巻き戻しているので、上に戻る方が「より正しい」でしょう。ウィキペディアは、これがどのように機能するかについてのアイデアを提供するかもしれません。

幸運を！

于 2011-07-10T04:39:41.287 に答える