-6

新しいソートアルゴリズムについて考えましたが、明らかな解決策の問題を理解できませんでした:

public int[] sort(int[] arr){

    //Find the biggest number in the array
    int max=1;
    for(int i : arr)
        if(i>max)
            max=i;

    //Sorting the figures into big array
    int[] LongSorted= new int[max+1];
    for(int i=1; i<LongSorted.length; i++)
        LongSorted[i]=0;
    for(int i : arr)
        LongSorted[i]+=i;

    //Transfer the sorted figures into the original array
    int index=0;
    for(int i=0; i<arr.length; i++){
        while(LongSorted[index]==0){
            index++;
        }
        arr[i]=index;
        if(LongSorted[index]!=(index)){
            for(int j=0; j<(LongSorted[index]/index)-1; j++){
                i++;
                arr[i]=index;
            }
        }
        index++;
    }

    return arr;
}

基本的に、アルゴリズムは数値の値をインデックスとして使用します。

この方法を使用する場合、数字の「0」は考慮されないことに注意してください。
次の手順で修正できます。
1 . LongSorted タイプを「Integer」に変更します。
2 . LongSorted の初期化 "for" の 'i' の値を '1' に変更します。
3 . 最後の「for」の前の前の行に、次の条件を追加します。

       if(LongSorted[0]!=null)
          arr[0]=0;

4 . 最後の「for」の「i」の値を「1」に変更します。
Tnx！

4

2 に答える 2

3

これがまったく効率的であると思われる場合、そうではありません。まず、さまざまな配列を何度もループします。これらのいくつかは必要ではなく、大量のデータセットでアルゴリズムの速度を低下させます。

次に、次のリストを並べ替えようとするとどうなりますか？[1; 1000000000]

2つの数値を並べ替えるだけで、サイズが10億+1の配列を作成することになります。これは40億バイトです。

最後に、重複する要素がある場合はどうなりますか？

そして、コメントで指摘されているように、これは負の数では失敗します。

このアイデアを完全に自分で思いついた場合で、プログラミングに慣れていない場合は、実際には本当に重要なもの、つまりハッシュテーブルへの正しい道を進んでいます。

于 2012-12-15T22:13:37.580 に答える
0

私は救助に来なければなりません：

確かに、このアルゴリズムが効率的であるかどうかは非常に依存しており、0 を超える正の値のみをカバーしています。

インプレースソートを使用して、もう少し読みやすく書き直しました。

public static int[] sort(int[] arr) {

    // Find the biggest number in the array
    int max = 1;
    for (int i : arr) {
        if (i > max) {
            max = i;
        }
    }

    // Sorting the figures into big array
    // indexOccurrences[i] is how often the value i occures in arr.
    int[] indexOccurrences = new int[max + 1];
    for (int i : arr) {
        ++indexOccurrences[i];
    }

    // Transfer the sorted figures into the original array
    int arrIndex = 0;
    for (int j = 1; j < indexOccurrences.length; ++j) {
        for (int k = 0; k < indexOccurrences[j]; ++k) {
            arr[arrIndex] = j;
            ++arrIndex;
        }
    }
    assert arrIndex == arr.length;
    return arr;
}

public static void main(String[] args) {
    int[] values = new int[] { 23, 6, 67, 6, 6, 45, 3 };
    values = sort(values);
    System.out.println(Arrays.toString(values));
}

[3, 6, 6, 6, 23, 45, 67]

ところで、このアイデアは新しいものではありませんが、それはそれをサポートするものと見なされるかもしれません.

于 2012-12-15T22:38:20.767 に答える