0

私は問題があります。マージソートがどのように機能するかを学び始めましたが、今は行き詰まっています。マージ関数の 2 回目の再帰がわかりません。

int merge_sort(int input[], int p, int r)
{
      if ( p >= r ) return 0; 

        int mid = floor((p + r) / 2);
        merge_sort(input, p, mid);
        **merge_sort(input, mid + 1, r);** 
        merge(input, p, r);
}

最初の再帰が終了すると、次のような結果になります: 元の配列: 3 4 5 6 7 8

3 4 5 | 6 7 8

3 4 | 5

3 | 4

3

そして、2回目の再帰が始まります。だから、私の質問は次のとおりです。2番目の再帰は、要素が1つだけの配列（この場合は3つの数字のみの配列）または元の配列（最初から6要素の配列）から始まりますか？私の言いたいことを理解していただければ幸いです。ありがとう。

4

1 に答える 1

0

常に入力配列を渡しているため、コードからはわかりません。しかし、はい、アイデアは分割して征服することであるため、最初の呼び出しは

マージ_ソート: 3 4 5 6 7 8

最初の再帰: 3 4 5

2 回目の再帰: 6 7 8

このウィキペディアの写真を見てください: http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

于 2013-04-24T14:08:18.787 に答える