5

Javaでは、以下のようにintの配列を作成し、入力してからソートする方が高速です:

int[] a = int[1000];
for (int i = 0; i < a.length; i++) {
    // not sure about the syntax
    a[i] = Maths.rand(1, 500) // generate some random positive number less than 500
}
a.sort(); // (which algorithm is best?)

またはオンザフライで挿入ソート

int[] a = int[1000];
for (int i = 0; i < a.length; i++) {
    // not sure about the syntax
    int v = Maths.rand(1, 500) // generate some random positive number less than 500
    int p = findPosition(a, v); // where to insert
    if (a[p] == 0) a[p] = v;
    else {
        shift a by 1 to the right
        a[p] = v;
    }
}
4

1 に答える 1

10

これを行うには多くの方法があります。

  1. 配列を作成し、並べ替えます。新しい要素のためのスペースを作るために配列要素を移動するのに必要な時間がほぼ確実にソート時間の大半を占めるため、これは非常に遅くなる可能性があります。これには、使用するアルゴリズムに関係なく、せいぜい Ω(n 2 ) 時間かかると予想する必要があります。ここで、n は配列に入れたい要素の数です。オンザフライで挿入ソートを行うと、ここで予想される O(n 2 ) の時間がかかります。

  2. ソートされていない配列を構築してから、ソートします。これは、 quicksortやradix sortなどの優れた並べ替えアルゴリズムを使用すると、おそらく非常に高速になります。これには、O(n log n) 時間 (クイックソートの場合) または O(n lg U) 時間 (基数ソートの場合) かかると予想する必要があります。ここで、n は値の数で、U は最大値です。

  3. 番号を優先度キューに段階的に追加してから、優先度キューからすべての要素をデキューします。プライオリティ キューの実装方法によっては、これが非常に高速になる場合があります。たとえば、ここでバイナリ ヒープを使用すると、このプロセスに O(n log n) の時間がかかり、 van Emde Boas ツリーを使用するとO(n lg lg U) の時間がかかります。ここで、U は保存している最大の数値です。 . とはいえ、ここでの一定の要因により、このアプローチは単に値をソートするよりも遅くなる可能性があります。

お役に立てれば！

于 2012-08-21T22:18:40.543 に答える