1 
merge1(int low, int high, int S[], U[]) 
{ 
    int k = (high - low + 1)/2
    for q (from low to high) U[q] = S[q]
    int j = low 
    int p = low 
    int i = low + k 

    while (j <= low + k - 1) and (i <= high) do 
    { 
        if ( U[j] <= U[i] ) 
        {
            S[p] := U[j] 
            j := j+1
        } 
        else 
        { 
            S[p] := U[i] 
            i := i+1 
        } 
        p := p+1 
    } 

    if (j <= low + k - 1) 
    { 
        for q from p to high do 
        { 
            S[q] := U[j] 
            j := j+1 
        } 
    }
}


merge_sort1(int low, int high, int S[], U[]) 
{ 
    if low < high 
    { 
        int k := (high - low + 1)/2 
        merge_sort1(low, low+k-1, S, U) 
        merge_sort1(low+k, high, S, U) 
        merge1(low, high, S, U) 
    } 
}

だから、基本的に、これは私の講義ノートにあります。私はそれが一般的にかなり混乱していると思いますが、私はそれの大部分を理解しています。私が理解していないのは、「if（j <= low + k-1）」の部分の必要性です。左側に「左」の要素があるかどうかをチェックしているようです。マージソーティング時にも可能ですか？

4

1 に答える 1

2

2つのソートされたリストをマージする場合（それらleftをandと呼びましょう）、またはリストのいずれかのアイテムがなくなるまでright、1つのアイテムを取得してリストに追加し続けます。これは最初のループによって行われます。次に、左側または右側のリストに残っている要素を結果リストに追加する必要があります。2つのオプションがあります。resultleftrightwhile

  • 左側のリストには要素がありませんが、右側のリストにはまだいくつかの要素があります。ここでのコードの記述方法では、配列の最後にリストSの最後の要素がすでに含まれているため、何もする必要はありません。right

  • 右のリストには要素がありませんが、左のリストにはまだいくつかあります。次に、残りの要素をの末尾にコピーしますS。これはif最後にmerge1行うことです。

このコードが「悪い」かどうかの質問について：コードは正しいですが、読みやすくするためにいくつかの変更を加えます。

  • 記述的な変数名。
  • 再計算する代わりに、リストleftとrightリストを区切る中点をに渡します。merge1
于 2010-04-23T23:45:01.503 に答える