Java数値補完アルゴリズムのバケットソート方法の詳細説明

この記事では、主にJavaのデータ構造とアルゴリズムのバケットソートの実装方法を紹介し、具体的な例に基づいてバケットソートの概念、原理、実装方法、および関連する操作スキルを詳細に分析します。この記事では、Java データ構造とアルゴリズムを使用してバケット ソートを実装する方法について説明します。参考のために皆さんと共有してください。詳細は次のとおりです。

基本的な考え方: 入力は、ランダム処理によって生成された区間 [0, M) 内に一様に分布した実数であると仮定します。区間 [0, M) を同じサイズの n 個のサブ区間 (バケット) に分割し、これらのバケットに n 個の入力要素を割り当て、バケット内の要素を並べ替えて、バケットを順番に接続して入力 0 ≤ A[1. .n] array

B[0..n-1] は、バケット (リンク リスト) を指すポインターの配列です。 n 個のレコードを各バケットに配布します。複数のレコードが同じバケットに割り当てられている場合は、バケット内で並べ替える必要があります。最後に、各バケット内のレコードを順番にリストし、順序付けられた順序で記憶します。

[バケット - キーワード] マッピング 関数 bindex=f(key) ここで、bindex はバケット配列 B (つまり、bindex 番目のバケット) の添字、k はバケット配列 B のキーですソートする列の文字。バケットソートの効率の鍵は、次のことを行う必要があるこのマッピング関数にあります:

キーワード k1明らかに、マッピング関数の決定はデータ自体の特性と大きく関係しています 以下に例を挙げてみましょう: 並べ替えられる列が K= {49, 38, 35, 97, 76 の場合。 、73、27、49}。これらのデータはすべて 1 ～ 100 の間です。したがって、10 個のバケットをカスタマイズし、マッピング関数 f(k)=k/10 を決定します。次に、最初のキーワード 49 は 4 番目のバケットに配置されます (49/10=4)。すべてのキーワードを順番にバケットに積み重ね、空ではない各バケットでクイック ソートを実行して、次の図を取得します。

上の図では、各 B[i] のデータを順番に出力するだけです。順序。

アルゴリズムのコアコードは次のとおりです:

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
/// <returns></returns>
static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
{
 int[] sorted = new int[maxNumber + 1];
 for (int i = 0; i < unsorted.Length; i++)
 {
  sorted[unsorted[i]] = unsorted[i];
 }
 return sorted;
}
static void Main(string[] args)
{
 int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
 var sorted = bucket_sort(x, 97);
 for (int i = 0; i < sorted.Length; i++)
 {
  if (sorted[i] > 0)
   Console.WriteLine(sorted[i]);
 }
 Console.ReadLine();
}

バケットソートコスト分析

バケットソートでは、関数のマッピング関係を使用して、ほぼすべての比較作業を削減します。実際、バケット ソートの f(k) 値の計算は、大量のデータを基本的に順序付けられたデータ ブロック (バケット) に分割するクイック ソートの分割に相当します。その後、バケット内の少量のデータに対して高度な比較並べ替えを実行するだけで済みます。

N 個のキーワードをバケットソートする時間計算量は 2 つの部分に分けられます:

(1)

ループ 各キーワードのバケットマッピング関数を計算します。この時間計算量は O(N) です。 (2) 高度な比較並べ替えアルゴリズムを使用して、各バケット内のすべてのデータを並べ替えます。その時間計算量は ∑ O(Ni*logNi) です。ここで、Ni は i 番目のバケットのデータ量です。
明らかに、パート (2) がバケット ソートのパフォーマンスの決定的な要素です。バケット内のデータの数を最小限に抑えることが、効率を向上させる唯一の方法です (比較並べ替えに基づく最適な平均時間計算量は O(N*logN) にしか達しないためです)。したがって、次の 2 点を達成するために最善を尽くす必要があります:

(1) マッピング関数 f(k) は、N 個のデータを M 個のバケットに均等に分散できるため、各バケットのデータ量は [N/M] になります。

(2)バケットの数をできるだけ増やす。極端な場合には、各バケットから取得できるデータは 1 つだけなので、バケット内のデータの「比較」並べ替え操作が完全に回避されます。もちろん、これを行うのは簡単ではありません。データ量が膨大な場合、f(k) 関数によって膨大な数のバケット セットが生成され、スペースが大幅に浪費されます。これは時間コストとスペースコストの間のトレードオフです。
並べ替える N 個のデータと M バケットの場合、バケットあたり [N/M] データの平均バケット並べ替え時間複雑さは次のようになります:

O(N)+O(M*(N/M )*log( N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

N=Mのとき、つまり極限の場合、それぞれバケットにはデータが 1 つだけあります。バケットソートの最高効率は O(N) に達します。

概要:

バケットソートの平均時間計算量は線形 O(N+C) で、C=N*(logN-logM) です。同じ N に対して、バケット数 M が大きいほど効率が高くなり、最適な時間計算量は O(N) に達します。 もちろん、バケットソートのスペースの複雑さは O(N+M) です。入力データが非常に大きく、バケットの数も非常に多い場合、スペースのコストは間違いなく高価になります。また、バケットソートも安定しています。 それは以下の3点です:

1.バケットソートは安定しています

2.バケットソートは一般的なソートの中で最も高速です...ほとんどの場合、バケットソートは非常に高速です。高速ですが、多くのスペースを消費します。基本的に、最もスペースを消費する並べ替えアルゴリズムです
。

補足: 検索アルゴリズムの中で、比較ベースの検索アルゴリズムの最高の時間計算量もO(logN)です。たとえば、二分探索、バランス二分木、赤黒木などです。ただし、Hashテーブルの検索効率はO(C)線形レベルです(検索効率は競合なしでO(1)に達します)。つまり、ハッシュ テーブルの考え方はバケット ソートと似ていますか?

実際、バケット ソートにはデータ条件に関する特別な要件があり、配列が大きい場合、数億のバケットを割り当てることは明らかに不可能です。したがって、バケットソートには制限があり、要素値のセットが大きくない状況に適しています。

【関連する推奨事項】

1. 特別な推奨事項: 「php Programmer Toolbox」V0.1 バージョンのダウンロード

2. Java アノテーションの包括的な分析

以上がJava数値補完アルゴリズムのバケットソート方法の詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。