1

以下の並べ替えはどのような種類の並べ替えで、実行時間はビッグ O 表記でどのくらいなのか気になりました。私の友人は、アルゴリズムの知識をまったく持たずにこのソート関数を作成しましたが、現在、その速度/メモリ効率について議論しています。よろしければ、分析にご協力ください。

void sort(int* a, int size)
{
    if (size <= 1) return;
    else if (size == 2)
    {
        if (a[0] > a[1])
            swap (a[0], a[1]);
        return;
    }
    else
    {
        int i = size / 2;
        sort(a, i);
        sort(a+i, size - i);
        int j = 0, k = i ;
        while (k < size && j < k)
        {
            if (a[j] > a[k])
            {
                int temp = k;
                while (temp > j)
                {
                    swap(a[temp - 1], a[temp]);
                    temp--;
                }
                k++;
            }
            j++;
        }
    }
}

ありがとうございました ：）

4

1 に答える 1

2

これは基本的にマージソートですが、^2 インプレース マージ ステップがあります。マージソートを分析するように、標準的な計算を行うと、実行時間が n^2 であることがわかります。これを行うために解く必要がある関連方程式は ですf(n) = n^2 + 2f(n/2)。

于 2012-09-17T19:00:23.483 に答える