1

アルゴリズムを改善しなければならない演習があります。このアルゴリズムは配列を取り、偶数を左側 (SORTED) に、オッズを右側 (NOT-SORTED) に配置します。アルゴリズムが非効率なので、改善する必要があります。

これは、私が「改善」しなければならない、演習の元のコードです。

public void what (int [] arr) {
    int temp;
    for (int i=0; i<arr.length; i++)
        if (arr[i]%2 == 0) {
            temp = arr[i];
            for (int j=i; j>0; j--)
                arr[j] = arr[j-1];
            arr[0] = temp;
    }
}

この演習でクイックソートアルゴリズムを実装したかったのですが、問題はピボットの使用方法がわからないことです。通常、ピボットは中央値であり、配列の数字の半分は小さく、残りの半分は大きくなります。

ここでの問題は、左側の部分が偶数で、右側の部分がオッズでなければならないことです。

この「並べ替え」を O(n^2) 未満の効率で実装する必要があります。

何か案は？

ありがとうございました！

4

3 に答える 3

0

@zerocool が提案したように、コードで実装:

private static int medianEven(int [] arr){
        int i=-1, j=arr.length; int temp=0; int w=0;
        while ((w<j)){
            if (arr[w]%2==0){
                i++;
                w++;
            }
            else
            {
                temp=arr[j-1];
                arr[j-1]=arr[w];
                arr[w]=temp;
                j--;
            }
        }
        return i;

    }

その後、arr[0] から arr[i] に quickSort メソッドを呼び出します。

quicksort(arr,0,i);

アドバイスありがとう。

于 2013-06-15T14:20:11.757 に答える
0

2 つのインデックスを持つことはどうでしょうか。1 つは先頭 (i=-1) から開始し、もう 1 つは末尾 (j=a.length) から開始します。i をインクリメントして偶数を入れ、j をデクリメントして奇数を入れます。反復が完了すると、偶数要素の最後の要素を指します。中間要素をピボットとして (つまり、0 から i まで) クイック ソートを適用します。

于 2013-06-15T12:52:51.447 に答える
0

提案 1: 配列を直線的に通過させ、偶数要素と奇数要素の 2 つに分割します。これには Theta(n) 時間がかかります。線形スイープを行っていて、とにかく各要素をチェックすると、最大の要素と最小の要素を見つけることができます。次に、偶数の整数の配列にカウントソートを実装できます。カウントソートの例:

並べ替えインタラクティブ カウント並べ替えビデオ

並べ替えの実行時間のカウントは O(n) 償却されるため、アルゴリズムの全体的な実行時間は O(n) になります。

提案 2: クイックソートを使用する場合は、すべての奇数の値を + 無限大として脅し、比較せずに自然にリストの最後に移動します。奇妙なピボットを選択した場合は、最後に置いて、もう一度試してください。最初/最後ではなく、ランダムなピボットを使用することをお勧めします。

于 2013-06-15T13:12:55.333 に答える