4

Java で静的メソッドを作成します。

public static void sortByFour (int[] arr)

これは、負でない数値 (ゼロまたは正) でいっぱいの配列をパラメーターとして受け取り、次の方法で配列を並べ替えます。

  • 配列の先頭には、4 で割り切れるすべての数値が表示されます。

  • それらの後に、4 で割り、余りが 1 である配列内のすべての数値が表示されます。

  • それらの後に、配列内の 4 で割り、余りが 2 であるすべての数値が表示されます。

  • 配列の最後には、すべての残りの数 (4 で割って 3 余りの数) が表示されます。

(各グループの数字の順番は関係ありません。)

この方法は、可能な限り効率的でなければなりません。

以下は私が書いたものですが、残念ながらうまくいきません... :(

public static void swap( int[] arr, int left, int right )
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

public static void sortByFour( int[] arr )
{
    int left = 0;
    int right = ( arr.length - 1 );
    int mid = ( arr.length / 2 );
    while ( left < right )
    {
        if ( ( arr[left] % 4 ) > ( arr[right] % 4 ) )
        {
            swap( arr, left, right );
            right--;
        }
        if ( ( arr[left] % 4 ) == ( arr[right] % 4 ) )
            left++;
        else
            left++;
    }
}

コードがうまく機能するようにコードを修正または書き直すにはどうすればよいですか?

4

6 に答える 6

2

ダニエルが言ったことを繰り返します：あなたはソートアルゴリズムのあなたの選択があります。それが要件である場合は、これまでにクラスでカバーした中で最も効率的なものを使用してください。ただし、アルゴリズムで2つのアイテムが比較されるポイントに到達したら、代わりにそれらの値mod4を比較します。つまり、のようなものにif A[i] > A[j]なりif A[i] % 4 > if A[j] % 4ます。次に、その配列要素で行うようにアルゴリズムで指定されていることをすべて実行し続けます。それを交換し、泡立て、戻し、必要なものは何でも。

あなたが投稿したコードに関しては、私はそれが迅速な修正に役立たないと思います。どのアルゴリズムを使用することになっていますか？何midのためにありますか？使用するアルゴリズムがわかっていて、コードのどの行に比較が含まれているのかがわかれば、ソリューションをすばやく確認してコーディングできるようになると思います。

一般に、これらの種類のものでは、効率を心配する前に、実用的なソリューションの取得に集中する場合に役立ちます。初めてこのような問題を起こさなければならなかったとき、私は選択ソートを使用しました。最初にそれを試してから、マージソートで得られた経験を使用することをお勧めします。これはO（n log n）です。

于 2010-06-08T07:20:39.413 に答える
2

線形時間ソリューション

これを行うための最も漸近的に効率的な方法は、bucket sortを使用することです。

  • 4 を法とする数値の合同クラスごとに 1 つずつ、合計 4 つのバケットがあります。
  • 配列内の数値を 1 回スキャンする
    • 各数値を右のバケットに入れます
  • 次に、出力配列を構築します
    • 最初にバケット 0 のすべての数値を入力し、次にバケット 1 のすべての数値を入力し、次にバケット 2、バケット 3 の順に入力します。

したがって、これは の数値をソートしますO(N)。これは最適です。ここで重要なのは、モジュロ 4 の数値でソートすることにより、基本的にソートする数値が 0、1、2、3 の 4 つだけになることです。

例示的なソリューションList

わかりやすくするために、 for-each をM使用した上記のアルゴリズム (一般的な modulo の場合) の実装を次に示します。Listチェックされていないキャストの警告は無視して、アルゴリズムを理解することに専念してください。

import java.util.*;

public class BucketModulo {
    public static void main(String[] args) {
        final int M = 4;
        List<Integer> nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5);
        List<Integer>[] buckets = (List<Integer>[]) new List[M];
        for (int i = 0; i < M; i++) {
            buckets[i] = new ArrayList<Integer>();
        }
        for (int num : nums) {
            buckets[num % M].add(num);
        }
        nums = new ArrayList<Integer>();
        for (List<Integer> bucket : buckets) {
            nums.addAll(bucket);
        }
        System.out.println(nums);
        // prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]"
    }
}

アルゴリズムを完全に理解したら、これを変換して配列を使用することは (必要な場合) 簡単です。

こちらもご覧ください

特記事項%

数学的に定義されているモジュロ演算子で%はないため、数値が負でないという規定は重要です。それは剰余演算子です。

System.out.println(-1 % 2); // prints "-1"

参考文献

于 2010-06-08T07:39:16.257 に答える
2

これを擬似コードで行いますが、コードで行うと答えが得られます。これは宿題なので、自分で作業できます。=P

リストなしでそれを行う方法は次のとおりです。この例は要件に基づいて制限されていますが、コーディングすると機能します。

int bucketSize = (arr.length() / 4) + 1;

int bucket1[bucketSize];
int bucket2[bucketSize];
int bucket3[bucketSize];
int bucket4[bucketSize];

for (int i=0; i<arr.length; i++) {
    if ((arr[i] % 4) == 0)
        put arr[i] in bucket 1
    else if ((arr[i] % 4) == 1)
        put arr[i] in bucket 2
    else if ((arr[i] % 4) == 2)
        put arr[i] in bucket 3
    else
        put arr[i] in bucket 4
}

for (int i=0; i<4; i++) {
    this will go for each bucket
    for (int j=0; j<bucketSize; j++) {
        do sort of your choice here to sort the given bucket
        the sort you used in your code will do fine (the swapping)
    }
}

次に、4 つのバケットをそれぞれの順序で連結して、最終結果を取得します

于 2010-06-07T18:53:42.817 に答える
2

次のように問題を攻撃できます。

  1. 使用するソート アルゴリズムを選択します。Quicksortをプログラムしようとしているように見えますが、 Bubble Sortを使用することもできます。
  2. 入力配列の 2 つの値が比較されるアルゴリズムのポイントを特定します。たとえば、ウィキペディアの記事にあるバブル ソートの疑似コードでは、唯一の比較は行if A[i] > A[i+1] then...です。
  3. 2 つの数を比較して、4 で割ったときに余りが 0 になる数sが、4 で割ったときに余りが 1 になる数tよりも小さいと見なされるようにする方法を見つけてください。アルゴリズムの比較演算をコンパレータの計算に置き換えます(例: if myIsGreater(A[i], A[i+1]) then...)。

ステップ 3 では、モジュラス演算子を考慮することで、間違いなく正しい方向に進んでいます。

于 2010-06-07T22:11:36.593 に答える
1

これがJava風の方法です...

    Arrays.sort(arr,new Comparator<Integer>(){
      public int compare(Integer a,Integer b)
      {
        return (a % 4) - (b % 4);
      }
    });
于 2010-06-19T16:54:18.197 に答える
1

このページを読んでください。http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms

それは長期的にはあなたに最も役立つはずです. それもかなり楽しいです！

于 2010-06-07T18:26:42.317 に答える