このO（n）ソート方法はすでに存在しますか？

Question

考えられるのは、すべての値を最終配列の親インデックスに設定し、すべてのヌル値を削除することです。それが唯一のユニークな非ゼロ値をソートし、注意点としては

int x[] = {9,3,4,2,1,12,5}; 
sortList(x) 

public static int[] sortList(int[] x){ 
    int[] y = new int[15]; 
    for (int i=0; i < x.length; i++){ 
     int value = x[i]; 
     y[value] = value; 
    } 
    return removeNull(y); 
} 
public static int[] removeNull(int[] array) { 
    return Arrays.stream(array).filter(i -> i != 0).toArray(); 
} 

： はここにいくつかの単純な実装です。配列を通過するときにメソッドが実行しているのは次のとおりです。

配列 - > 9,3,4,2,1,5は - > 0,1,2,3,4,5に変換されます。 0,0,0,9,0,0そして次に - > 1,2,3,4,5,9 私がこの問題を解決するのであれば、この解決法は配列を3回ループし、記憶域としてyサイズを取ります。このソート方法はすでに存在しますか？

Answer 1

このアルゴリズムはCounting Sortとして知られています。

ここではWikipediaの説明です：コンピュータサイエンスの

、ソートをカウントする小さな整数であるキーに応じたオブジェクトのコレクションをソートするためのアルゴリズムですが。つまり、整数ソートアルゴリズムです。これは、それぞれ異なるキー値を持つオブジェクトの数を数え、それらの数に算術演算を使用して出力シーケンスの各キー値の位置を決定することによって動作します。その実行時間は、アイテム数と最大と最小のキー値の差が線形であるため、キーの変化がアイテムの数よりも大幅に大きくない状況での直接使用にのみ適しています。

あなたの指摘どおり、アルゴリズムは重複を破棄します。ソートを数えることは、各キーの項目数を数えて、この問題を解決することによって名前を取得します。このアルゴリズムは実際には線形ですが、時間と空間の両方で高い定数係数は実際にほとんど使用されません。