0

a と b の配列を調べて、a と b の要素をコンボにコピーし、コンボがソートされるようにする必要があります。

たとえば、a が {3, 5, 7, 7, 9} で、b が {2, 5, 8, 1234} の場合 (したがって、コンボには 9 つの要素が必要です)、この関数はコンボを {2, 3, 5、5、7、7、8、9、1234}。これを効率的に行う必要があります。値をコンボに入れるときは、それらを正しい場所に配置する必要があります。でたらめではなく、後で並べ替えます。

while ループでネストされた for ループを試しましたが、奇妙な結果が得られます。最低数を超える方法を見つけられないようです。たとえば、コンボ配列に最小値を追加すると、それ自体を破棄する方法がわかりません。助けてくれてありがとう。

void merge( 
    unsigned combo[], 
    const unsigned a[],
    unsigned aElements,
    const unsigned b[],
    unsigned bElements 
){

    if (mySort(a, aElements) == 0) {
        cout << "The first array is not sorted";
        exit(1);
    }

    if (mySort(b, bElements) == 0) {
        cout << "The second array is not sorted";
        exit(1);
    }

    unsigned combinedElements;
    unsigned lowest = 0;
    unsigned i = 0;

    combinedElements = aElements + bElements;

    while (i < combinedElements) {
        for (int n = 0; n < combinedElements; n++) {
            if (a[i] < b[n]) {
                lowest = a[i];
            }

            else {
                lowest = b[n];
            }
        }

        combo[i] = lowest;
        i++;
        cout << combo[i] << endl;
    }


}
4

5 に答える 5

3

これはある種の宿題だと思います。そうでない場合は、 を使用してstd::mergeください。

これを手動でロールアウトする場合は、3 つのカーソルで作業していることを考慮する必要があります。2 つは 2 つの異なる配列への入力カーソルで、もう 1 つは出力 (書き込み) カーソルです。

どの配列から次の要素を移動するかを決定したら、その配列の読み取りカーソル (その要素は既に消費されているため) と最終配列の書き込みカーソル (そのため) の 2 つのカーソルをコピーして更新する必要があります。場所はすでに書き込まれています)。

これが解決策につながることを願っています:)

于 2013-02-14T23:27:53.410 に答える
1

試すことができる標準的なもののリストは次のとおりです。 http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/

また、疑似コードで次のようなことを考えましたか:

新しい配列を作成 [古い配列のサイズから 1 を引いたサイズ] mempcy(新しい配列、開始点から削除点 -1) mempcy(新しい配列、削除点 + 1 から終了点)

新しい配列から並べ替える

もう一度最小の数字を罰金します...

于 2013-02-14T23:26:04.163 に答える
0

これは、読みやすく理解しやすい非常にコンパクトなソリューションです。

combo結果に収まる十分なスペースがaありb、すでに注文されていると想定しています（例が示すように）：

void merge(unsigned combo[], 
           const unsigned a[],
           unsigned aElements,
           const unsigned b[],
           unsigned bElements)
{
    while(aElements + bElements > 0)
    {
      if(bElements == 0 || (aElements > 0  && *a < *b))
      {
          aElements--;
          *combo++ = *a++;
      }
      else
      {
          bElements--;
          *combo++ = *b++;
      }
   }
}

パフォーマンスを向上させるために少し調整することもできますが、非常にエレガントで読みやすいです。さらに、このコードは C と C++ の両方に準拠しています。

于 2013-02-14T23:29:36.180 に答える
0

これが宿題または同様のものであり、のような標準的なものを使用することが許可されていないと仮定するとstd::merge、2 つのソートされたリストのマージ アルゴリズムは、次のように線形の複雑さで達成できます。

void merge( unsigned combo[], const unsigned a[], unsigned aElements, const unsigned 
b[],    unsigned bElements ){

    if (mySort(a, aElements) == 0) {
        cout << "The first array is not sorted";
        exit(1);
    }

    if (mySort(b, bElements) == 0) {
        cout << "The second array is not sorted";
        exit(1);
    }

    int i,j,k =0;
    while (i<aElements && j<bElements)
    {
        if (a[i]<=b[j])
        {
            combo[j++]=a[i++];
        } else
        {
            combo[j++]=b[j++];
        }
    }

    //add remaining elements. at least one of these loops will not happen
    while (i < aElements) combo[j++]=a[i++];
    while (j < bElements) combo[j++]=b[j++];
}
于 2013-02-14T23:35:33.357 に答える