Javaでソートをカウントする-＆＃＆チュートリアル-php.cn

Javaでソートをカウントする

WBOY

リリース： 2024-08-30 15:58:33

オリジナル

1149 人が閲覧しました

カウンティングソートは、どのプログラミング言語でも重要な役割を果たすアルゴリズムであり、Java も同様です。カウンティングソートアルゴリズムの主な目的は、アルゴリズムをソートするための小さな整数として存在するキーに従ってオブジェクトコレクションをソートすることです。これは主に、キーと値のペアのカウントを操作して実行し、出力シーケンスに従って要素の位置を示します。この並べ替えの実行時間は項目に関して線形であり、キー値の差は最大値と最小値の間にあります。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェアテスト、その他

構文

Java でカウントソートを実行するための特定の構文はありませんが、入力に従ってカウントソートを実行するアルゴリズムの形式で段階的に適用されるロジックフローがあり、次のように表されます。

Class name {
Method name following sorting ()
{
# Find the length of array defined;
#the output character array will have sorted array
#Create a count arr to store count of each element, characters and initialize it 0
#Store count of each character element in the array
#Build output character and write the logic to make it operated in reverse order
#that builds output can now be copied from the previous array to the current
#Make use of the driver code to move and proceed.
}

ログイン後にコピー

Java でのカウントソートはどのように機能しますか?

前述したように、カウンティングソートアルゴリズムはプログラミングにおいて重要な役割を果たします。これは、収集された形式で存在するオブジェクトの並べ替えに使用され、個別のキーと値のペアを持つ存在する要素の数をカウントするために使用され、また、各キーと値を持つ存在する各要素の位置を決定する算術カウントとともに使用されます。最小値と最大値の差。
チェックされている場合の実行時間または時間計算量は、配列内のすべての要素と最小キー値と最大キー値の差を含む本質的に線形であるため、これらの要素とソート手法は、キーが変化する場合に直接使用する場合に適しています。必要なキーを持つ要素より大幅に大きいことはありません。
ほとんどのキー処理をサポートできる別のアルゴリズムがありますが、要件に従ってソートをカウントするほど効率的ではなく、ハッシュを基数ソートに置き換えて、以前と比較して大量のキーの状況を処理できます。 .
カウントソートは配列のインデックス値の一部としてキーと値のペアを使用するため、比較ソートとはみなされません。また、比較ソートの下限は許可されません。
バケットソートには、同じタスクセットと同様の時間分析の場合にのみ過少カウントソートも含まれますが、カウントソートと比較すると、その時点でバケットソートには動的配列、リンクリスト、または保持するために大量のメモリが必要です。バケット内に存在する要素をカウントして並べ替えると、バケットごとに個別の単一の数値である値のみが保存されます。
カウントソートへの入力が n 個の項目のコレクションで構成され、各項目が k として何らかの値を持つ最大値の非負の整数のキー値を持つという事実に基づく、特定の入力および出力の仮説シーケンスがあります。カウンティングソートの説明の一部は、単純に線形形式の整数シーケンスをソートするための入力です。
配列の出力は、ほとんどの場合、何らかの順序のキーを持つ主要な項目で構成されませんが、その使用は要件に関してチェックする必要があります。
Sort のカウントに関する時間計算量は O (n+l) になります。ここで、n は要素の数、l は入力を考慮する範囲です。
また、補助空間は O(n+l) のみであることがわかります。

Java でのカウントソートの例

このプログラムは、Java でのソートの一部として設定された入出力シーケンスの一部を考慮することにより、カウントソートを示します。

コード:

public class Counting_Sort_1{
void sort_0(char arr_0[])
{
int n_8 = arr_0.length;
char output_val[] = new char[n_8];
int count_0[] = new int[528];
for (int l_0 = 0; l_0 < 528; ++l_0)
count_0[l_0] = 0;
for (int y_1 = 0; y_1 < n_8; ++y_1)
++count_0[arr_0[y_1]];
for (int l_0 = 1; l_0 <= 526; ++l_0)
count_0[l_0] += count_0[l_0 - 1];
for (int l_0 = n_8 - 1; l_0 >= 0; l_0--) {
output_val[count_0[arr_0[l_0]] - 1] = arr_0[l_0];
--count_0[arr_0[l_0]];
}
for (int l_0 = 0; l_0 < n_8; ++l_0)
arr_0[l_0] = output_val[l_0];
}
public static void main(String []args){
Counting_Sort_1 ob = new Counting_Sort_1();
char arr_0[] = { 's', 'a', 'r', 'c', 's', 'f', 'o',
'i', 'n', 'c', 'a', 'r', 'm' };
ob.sort_0(arr_0);
System.out.print("Sorted_character_array_in_Counting_Sort ");
for (int l = 0; l < arr_0.length; ++l)
System.out.print(arr_0[l]);
}
}

ログイン後にコピー

出力:

Javaでソートをカウントする