アニメーション + 原理 + コード、トップ 10 の古典的なソート アルゴリズムを解釈する

アニメーション + 原理 + コード、トップ 10 の古典的なソート アルゴリズムを解釈する

ソートアルゴリズムは、「データ構造とアルゴリズム」における最も基本的なアルゴリズムの 1 つです。

ソートアルゴリズムは、内部ソートと外部ソートに分けられます。内部ソートはメモリ内のデータレコードをソートするのに対し、外部ソートはソートするデータが非常に大きく、一度にすべてのソートレコードを収容できないため、ソート処理中に外部メモリにアクセスする必要があるためです。一般的な内部ソート アルゴリズムには、挿入ソート、シェル ソート、選択ソート、バブル ソート、マージ ソート、クイック ソート、ヒープ ソート、基数ソートなどがあります。図でまとめると次のようになります。

時間の計算量について:

  1. 平方順序 (O(n2)) ソート さまざまな単純なソート方法: 直接挿入、直接選択、バブル ソート。
  2. 線形対数順序 (O(nlog2n)) ソート: クイックソート、ヒープソート、マージソート。
  3. O(n1+§))のソート、§は0から1の間の定数です。 ヒルソート。
  4. 線形順序 (O(n)) ソート バケット ソートとボックス ソートに加えて、基数ソートも実行できます。

安定性について:

安定したソートアルゴリズム: バブルソート、挿入ソート、マージソート、基数ソート。

安定したソートアルゴリズムではありません: 選択ソート、クイックソート、シェルソート、ヒープソート。

用語集:

n: データサイズ

k: 「バケット」の数

インプレース: 一定のメモリを占有し、追加のメモリを占有しない

アウトプレース: 追加のメモリを占有します

安定性: ソート後の2つの等しいキー値の順序は、ソート前の順序と同じである

1. バブルソート

バブルソートもシンプルで直感的なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

最も単純なソートアルゴリズムの 1 つであるバブルソートは、辞書に出てくる「Abandon」と同じような感覚です。最初のページの最初の位置に必ずあるので、最も馴染みがあります。バブルソートには、フラグを設定する最適化アルゴリズムもあります。シーケンスのトラバーサル中に要素が交換されない場合、シーケンスがすでに順序付けられていることが証明されます。しかし、この改善はパフォーマンスの向上にはあまり役立ちません。

1. アルゴリズムの手順

  1. 隣接する要素を比較します。最初の値が 2 番目の値より大きい場合は、それらを交換します。
  2. 最初のペアから最後のペアまで、隣接する要素の各ペアに対して同じ操作を実行します。このステップが完了すると、*** 要素は *** 数値になります。
  3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。
  4. 比較する数字のペアがなくなるまで、要素の数を少しずつ減らしながら上記の手順を繰り返します。

2. アニメーションデモ

3. 最速タイムはいつですか?

入力データがすでに正の順序になっている場合 (すでに正の順序になっているのに、なぜバブル ソートを実行する必要があるのでしょうか)。

4. 最も遅い時間はいつですか?

入力データが逆順の場合 (データを逆順に出力するために for ループを記述しないのはなぜですか。バブル ソートを使用するのはなぜですか。私は自由ですか)。

5. Javaコードの実装

  1. パブリッククラスBubbleSortはIArraySortを実装します{  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7.  ( int i = 1; i < arr.length; i++) {
  8.             // フラグを設定します。trueの場合、このループでは交換が実行されないことを意味します。つまり、ソートするシーケンスはすでに整列しており、ソートが完了しています。
  9.             ブールフラグ = true ; 
  10.  
  11.  ( int j = 0; j < arr.length - i; j++) {
  12.                 もし(arr[j] > arr[j + 1]) {
  13.  tmp = arr[j];
  14.                     arr[j] = arr[j + 1];
  15.                     arr[j + 1] = tmp; 
  16.  
  17.                     フラグ = false ;
  18.                 }
  19.             } 
  20.  
  21.             if (フラグ) {
  22.                 壊す;
  23.             }
  24.         }
  25.  arrを返します。
  26.     }
  27.  }

2. 選択ソート

選択ソートはシンプルで直感的なソートアルゴリズムです。どのようなデータが入力されても、時間の計算量は O(n²) です。したがって、使用する場合、データサイズが小さいほど良いです。唯一の利点は、余分なメモリスペースを占有しないことです。

1. アルゴリズムの手順

  1. まず、ソートされていないシーケンス内の最小 (最大) の要素を見つけて、それをソートされたシーケンスの先頭に格納します。
  2. 残りのソートされていない要素から最小 (最大) の要素を探し続け、それをソートされたシーケンスの最後に配置します。
  3. すべての要素がソートされるまで手順 2 を繰り返します。

2. アニメーションデモ

3. Javaコードの実装

  1. パブリッククラスSelectionSortはIArraySortを実装します{  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.  int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  5.  
  6.         // 合計N-1回の比較が必要です
  7. ( int i = 0; i < arr.length - 1; i++) {
  8. 整数 最小値= i; 
  9.  
  10.             // 各ラウンドで必要な比較回数 Ni
  11.  ( int j = i + 1; j < arr.length; j++) {
  12.                 （arr[j] < arr[ min ]）の場合{
  13.                     // これまでに見つかった最小の要素の添え字を記録する
  14. 最小値= j;
  15.                 }
  16.             } 
  17.  
  18.             // 見つかった最小値を位置 i の値と交換します
  19.             もし (i != min ) {
  20.  tmp = arr[i];
  21.                 arr[i] = arr[分];
  22.                 arr[分] = tmp;
  23.             } 
  24.  
  25.         }
  26.  arrを返します。
  27.     }
  28.  }

3. 挿入ソート

挿入ソートのコード実装はバブルソートや選択ソートほど単純で粗雑ではありませんが、その原理は最も理解しやすいはずです。ポーカーをプレイしたことがある人なら誰でも数秒で理解できるはずです。挿入ソートは、最も単純で直感的なソート アルゴリズムです。順序付けられたシーケンスを構築することで機能します。ソートされていないデータの場合は、ソートされたシーケンスの後ろから前へスキャンし、対応する位置を見つけて挿入します。

挿入ソートには、バブルソートと同様に、半挿入と呼ばれる最適化アルゴリズムもあります。

1. アルゴリズムの手順

  • ソートするシーケンスの最初の要素を順序付きシーケンスとして扱い、最初の要素の 2 番目の要素をソートされていないシーケンスとして扱います。
  • ソートされていないシーケンスを最初から最後までスキャンし、スキャンされた各要素をソートされたシーケンスの適切な位置に挿入します。 (挿入する要素が順序付けられたシーケンス内の要素と等しい場合、挿入する要素は等しい要素の後に挿入されます。)

2. アニメーションデモ

3. Javaコードの実装

  1. パブリッククラス InsertSort は IArraySort を実装します {  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7.         // インデックス 1 の要素から開始し、挿入する適切な位置を選択します。インデックス 0 の要素は 1 つしかなく、デフォルトで順序付けされているためです。
  8.  ( int i = 1; i < arr.length; i++) { 
  9.  
  10.             //挿入するデータを記録する
  11. tmp = arr[i]; 
  12.  
  13.             // ソートされたシーケンスの右端から始めて、それより小さい数を見つけます
  14. 整数j = i;
  15.             (j > 0 && tmp < arr[j - 1]) の場合 {
  16.                 arr[j] = arr[j - 1];
  17.                 j --;  
  18.             } 
  19.  
  20.             // より小さい数字がある場合は、挿入します
  21.             もし (j != i) {
  22.                 arr[j] = tmp;
  23.             } 
  24.  
  25.         }
  26.  arrを返します。
  27.     }
  28.  }

4. シェルソート

ヒル ソートは、降順増分ソート アルゴリズムとも呼ばれ、挿入ソートのより効率的な改良版です。しかし、シェルソートは不安定なソートアルゴリズムです。

ヒルソートは、挿入ソートの次の 2 つの特性に基づいた改良された方法を提案します。

  • 挿入ソートは、ほぼソートされたデータに対して操作する場合に効率的です。つまり、線形ソートの効率を実現できます。
  • しかし、挿入ソートは一度に 1 ビットしかデータを移動できないため、一般的に非効率的です。

シェルソートの基本的な考え方は、まずソートするレコードのシーケンス全体をいくつかのサブシーケンスに分割し、それらを個別に直接挿入してソートすることです。シーケンス全体のレコードが「基本的に順序付けられている」場合、すべてのレコードが直接挿入され、順番にソートされます。

1. アルゴリズムの手順

  1. 増分シーケンス t1、t2、...、tk を選択します。ここで、ti > tj、tk = 1 です。
  2. 増分シーケンスの数 k に従ってシーケンスを k 回ソートします。
  3. 各ソートラウンドでは、ソート対象のシーケンスは、対応する増分 ti に従って長さ m の複数のサブシーケンスに分割され、各サブシーケンスに対して直接挿入ソートが実行されます。増分係数が 1 の場合のみ、シーケンス全体がテーブルとして扱われ、テーブルの長さがシーケンス全体の長さになります。

2. Javaコードの実装

  1. パブリッククラスShellSortはIArraySortを実装します{  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7. ギャップ= 1;
  8.         ギャップ < arr.length の場合
  9.             ギャップ = ギャップ * 3 + 1;
  10.         } 
  11.  
  12.         ギャップ > 0 の場合
  13. ( int i = ギャップ; i < arr.length; i++) {
  14.  tmp = arr[i];
  15.  int j = i - ギャップ;
  16.                 j >= 0 && arr[j] > tmp の場合
  17.                     arr[j + ギャップ] = arr[j];
  18.                     j -= ギャップ;
  19.                 }
  20.                 arr[j + ギャップ] = tmp;
  21.             }
  22.             ギャップ = ( int ) Math.floor(ギャップ / 3);
  23.         } 
  24.  
  25.  arrを返します。
  26.     }
  27.  }

5. マージソート

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。

分割統治の考え方の典型的なアルゴリズムの応用として、マージソートは次の 2 つの方法で実装されます。

  • トップダウン再帰（すべての再帰メソッドは反復を使用して書き換えることができるため、2 番目のメソッドがあります）
  • ボトムアップ反復

「データ構造とアルゴリズムの JavaScript 記述」では、著者はボトムアップの反復法を紹介しています。しかし、再帰的な方法については、著者は次のように考えています。

ただし、再帰が深すぎて言語が処理できないため、JavaScript ではこれを行うことはできません。

ただし、アルゴリズムの再帰の深さが深すぎるため、JavaScript ではこれは実現できません。

正直に言うと、この文章はよく分かりません。これは、JavaScript コンパイラのメモリが少なすぎて、再帰が深すぎるとメモリ オーバーフローが簡単に発生する可能性があることを意味しますか? どなたかアドバイスをいただければ幸いです。

選択ソートと同様に、マージソートのパフォーマンスは入力データの影響を受けませんが、時間の計算量が常に O(nlogn) であるため、選択ソートよりもはるかに優れたパフォーマンスを発揮します。コストは、必要な追加のメモリスペースです。

1. アルゴリズムの手順

  1. 2 つのソートされたシーケンスの合計サイズを持つスペースを申請します。このスペースは、結合されたシーケンスを格納するために使用されます。
  2. 2 つのポインタを設定します。その初期位置は、2 つのソートされたシーケンスの開始位置です。
  3. 2 つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインタを次の位置に移動します。
  4. ポインタがシーケンスの末尾に到達するまで手順 3 を繰り返します。
  5. 他のシーケンスの残りのすべての要素を、結合されたシーケンスの末尾に直接コピーします。

2. アニメーションデモ

3. Javaコードの実装

  1. パブリッククラスMergeSortはIArraySortを実装します{  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7.         （arr.length < 2）の場合{
  8.  arrを返します。
  9.         }
  10.  int中間 = ( int ) Math.floor(arr.length / 2); 
  11.  
  12.  int []左= Arrays.copyOfRange(arr, 0, 中央);
  13.  int [] right = Arrays.copyOfRange(arr, middle, arr.length); 
  14.  
  15.  merge(sort( left ), sort( right ))を返します。
  16.     } 
  17.  
  18.     保護されたint [] マージ ( int []左、 int []右) {
  19.  int [] 結果 = 新しいint [左.length +右.length];
  20. 整数i = 0;
  21.         while (左.length > 0 &&右.length > 0) {
  22.             （左[0] <=右[0]）の場合{
  23.                 結果[i++] =左[0];
  24.  left = Arrays.copyOfRange( left , 1, left .length);
  25.             }それ以外{
  26.                 結果[i++] =右[0];
  27.  right = Arrays.copyOfRange( right , 1, right .length);
  28.             }
  29.         } 
  30.  
  31.         while (左.長さ > 0) {
  32.             結果[i++] =左[0];
  33.  left = Arrays.copyOfRange( left , 1, left .length);
  34.         } 
  35.  
  36.         while (右.長さ > 0) {
  37.             結果[i++] =右[0];
  38.  right = Arrays.copyOfRange( right , 1, right .length);
  39.         } 
  40.  
  41. 結果を返します。
  42.     } 
  43.  
  44.  }

6. クイックソート

クイックソートは、Tony Hall によって開発されたソートアルゴリズムです。平均すると、n 個の項目をソートするには O(nlogn) 回の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、これはまれです。実際、クイックソートは、その内部ループがほとんどのアーキテクチャで効率的に実装できるため、他の O(nlogn) アルゴリズムよりも大幅に高速になることがよくあります。

クイックソートでは、分割統治戦略を使用してリストを 2 つのサブリストに分割します。

クイックソートは、ソートアルゴリズムにおける分割統治の考え方のもう 1 つの典型的な応用です。本質的に、クイックソートはバブルソートに基づく再帰的な分割統治法とみなされるべきです。

クイック ソートという名前は単純で大雑把です。この名前を聞いた瞬間に、その存在目的が高速かつ効率的であることが分かるからです。これは、ビッグ データを処理するための最速のソート アルゴリズムの 1 つです。最悪ケースの時間計算量は O(n²) に達しますが、これは優れた結果です。ほとんどの場合、平均時間計算量が O(n logn) のソート アルゴリズムよりも優れたパフォーマンスを発揮します。しかし、その理由はわかりません。幸いなことに、私の強迫性障害は再発し、多くの情報を確認した後、ついに「アルゴリズム アートおよび情報科学コンテスト」で満足のいく答えを見つけました。

クイックソートの最悪ケースの実行時間は、例えばシーケンシャルシーケンスのクイックソートの場合、O(n²) です。しかし、償却予想時間は O(nlogn) であり、O(nlogn) 表記法で暗示される定数係数は非常に小さく、複雑さが安定して O(nlogn) に等しいマージ ソートよりもはるかに小さくなります。したがって、弱い順序を持つほとんどの乱数シーケンスでは、クイック ソートがマージ ソートよりも常に優れています。

1. アルゴリズムの手順

  1. シーケンスから要素を選択することを「ピボット」と呼びます。
  2. 基本値より小さいすべての要素が基本値の前に配置され、基本値より大きいすべての要素が基本値の後に配置されるようにシーケンスを並べ替えます (同じ数字をどちらの側にも配置できます)。このパーティションを抜けると、ベンチマークはシリーズの途中になります。これはパーティション操作と呼ばれます。
  3. 基本値より小さい要素の部分シーケンスと基本値より大きい要素の部分シーケンスを再帰的にソートします。

再帰の最後のケースは、シーケンスのサイズが 0 または 1 の場合であり、これは常にソートされていることを意味します。再帰は継続されますが、各反復で少なくとも 1 つの要素を最適な位置に移動するため、アルゴリズムは常に終了します。

2. アニメーションデモ

3. Javaコードの実装

  1. パブリッククラス QuickSort は IArraySort を実装します {  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7.  quickSort(arr, 0, arr.length - 1) を返します。
  8.     } 
  9.  
  10.     プライベートint [] クイックソート( int [] arr, int  左、 int  右） {
  11.         （左<右）の場合{
  12.  intパーティションインデックス = パーティション(arr、左、右);
  13.             クイックソート(arr,左, パーティションインデックス - 1);
  14.             クイックソート(arr, パーティションインデックス + 1,右);
  15.         }
  16.  arrを返します。
  17.     } 
  18.  
  19.     プライベートintパーティション( int []arr, int  左、 int  右） {
  20.         // ピボット値を設定する
  21. intピボット =左;
  22. 整数 インデックス= ピボット + 1;
  23.  for ( int i =インデックス; i <=右; i++) {
  24.             （arr[i] < arr[pivot]）の場合{
  25.                 swap(arr, i,インデックス);
  26. インデックス++;
  27.             }
  28.         }
  29.         swap(arr, ピボット,インデックス- 1);
  30. 戻る インデックス- 1;
  31.     } 
  32.  
  33.     プライベートvoid swap( int [] arr, int i, int j) {
  34. 整数  temp = arr[i];
  35.         arr[i] = arr[j];
  36.         arr[j] =一時;
  37.     } 
  38.  
  39.  }

7. ヒープソート

ヒープソートとは、ヒープ データ構造を使用して設計されたソート アルゴリズムを指します。スタックは、完全な二分木を近似し、スタックの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。ヒープソートは、ヒープの概念を使用してソートする選択ソートであると言えます。方法は2つあります。

  1. ビッグトップヒープ: 各ノードの値は、その子ノードの値以上であり、ヒープソートアルゴリズムの昇順のために使用されます。
  2. ミニトップヒープ: 各ノードの値は、その子ノードの値以下であり、ヒープソートアルゴリズムの降順のために使用されます。

ヒープソートの平均時間計算量は O(nlogn) です。

1. アルゴリズムの手順

  1. ヒープH[0...n-1]を作成します。
  2. ヒープ先頭 (最高値) とヒープ末尾を交換します。
  3. ヒープサイズを1減らし、shift_down(0)を呼び出して、新しい配列の先頭データを対応する位置に調整します。
  4. ヒープ サイズが 1 になるまで手順 2 を繰り返します。

2. アニメーションデモ

3. Javaコードの実装

  1. パブリッククラスHeapSortはIArraySortを実装します{  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7.  int len ​​= arr.length; 
  8.  
  9.         ビルドMaxHeap(arr, len); 
  10.  
  11.  ( int i = len - 1; i > 0; i --) {  
  12.             スワップ(arr, 0, i);
  13.             長さ--;  
  14.             ヒープ化(arr, 0, len);
  15.         }
  16.  arrを返します。
  17.     } 
  18.  
  19.     プライベートvoid buildMaxHeap( int [] arr, int len) {
  20.  ( int i = ( int ) Math.floor(len / 2); i >= 0; i -- ) {  
  21.             ヒープ化(arr, i, len);
  22.         }
  23.     } 
  24.  
  25.     プライベートvoidヒープ化( int [] arr, int i, int len) {
  26. 整数 左= 2 * i + 1;
  27. 整数 右= 2 * i + 2;
  28.  int最大 = i; 
  29.  
  30.         if ( left < len && arr[ left ] > arr[largest]) {
  31.             最大 =左;
  32.         } 
  33.  
  34.         if ( right < len && arr[ right ] > arr[largest]) {
  35.             最大 =右;
  36.         } 
  37.  
  38.         （最大 != i）の場合{
  39.             swap(arr, i, 最大);
  40.             ヒープ化(arr, 最大, len);
  41.         }
  42.     } 
  43.  
  44.     プライベートvoid swap( int [] arr, int i, int j) {
  45. 整数  temp = arr[i];
  46.         arr[i] = arr[j];
  47.         arr[j] =一時;
  48.     } 
  49.  
  50.  }

8. カウントソート

カウンティングソートの中核は、入力データの値をキーに変換し、それを追加の配列スペースに格納することです。線形時間計算量を持つソート方法として、カウンティングソートでは、入力データが特定の範囲の整数である必要があります。

1. アニメーションデモ

2. Javaコードの実装

  1. パブリッククラスCountingSortはIArraySortを実装します{  
  2.     @オーバーライド
  3. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  4.         //パラメータの内容を変更せずにarrをコピーする
  5. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  6.  
  7. 戻り値: 
  8.  
  9.  countingSort(arr, maxValue) を返します。
  10.     } 
  11.  
  12.     プライベートint [] countingSort( int [] arr, int maxValue) {
  13.  intバケット長さ = 最大値 + 1;
  14.  int [] バケット = 新しいint [bucketLen]; 
  15.  
  16.  for ( int値: arr ) {
  17.             バケット[値]++;
  18.         } 
  19.  
  20.  intソートインデックス = 0;
  21.  ( int j = 0; j < バケット長さ; j++) {
  22.             （バケット[j] > 0）{
  23.                 arr[ソートされたインデックス++] = j;
  24.                 バケット[j] --;  
  25.             }
  26.         }
  27.  arrを返します。
  28.     } 
  29.  
  30.     プライベートint getMaxValue( int [] arr) {
  31. 整数最大値 = arr[0];
  32.  for ( int値: arr ) {
  33.             （最大値<値）の場合{
  34.                 最大値 = 値;
  35.             }
  36.         }
  37.  maxValueを返します。
  38.     } 
  39.  
  40.  }

9. バケットソート

バケットソートは、カウントソートのアップグレード版です。これは関数のマッピング関係を利用しますが、その効率の鍵はこのマッピング関数の決定にあります。バケットソートをより効率的にするには、次の 2 つのことを行う必要があります。

  • 十分な余裕がある場合は、バケットの数を増やしてみてください
  • 使用されるマッピング関数は、N個の入力データをK個のバケットに均等に分配することができる。

同時に、バケット内の要素のソートでは、比較ソート アルゴリズムの選択がパフォーマンスに大きく影響します。

1. 最も速いのはいつですか

入力データを各バケットに均等に分散できる場合。

2. 最も遅い時間はいつですか?

入力データが同じバケットに割り当てられている場合。

3. Javaコードの実装

  1. パブリッククラスBucketSortはIArraySortを実装します{ 
  2.  
  3.     プライベート静的最終 InsertSort insertSort = new InsertSort(); 
  4.  
  5.     @オーバーライド
  6. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  7.         //パラメータの内容を変更せずにarrをコピーする
  8. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  9.  
  10. バケットソート(arr, 5)を返します。
  11.     } 
  12.  
  13.     プライベートint [] bucketSort( int [] arr, int bucketSize) 例外をスローします {
  14.         （arr.length == 0）の場合{
  15.  arrを返します。
  16.         } 
  17.  
  18. 整数最小値 = arr[0];
  19. 整数最大値 = arr[0];
  20.  for ( int値: arr ) {
  21.             （値<最小値）の場合{
  22.                 minValue = 値;
  23.             }それ以外の場合 (値 > 最大値) {
  24.                 最大値 = 値;
  25.             }
  26.         } 
  27.  
  28.  intバケット数 = ( int ) Math.floor((maxValue - minValue) / バケットサイズ) + 1;
  29.  int [][] バケット = 新しいint [bucketCount][0]; 
  30.  
  31.         // マッピング関数を使用して各バケットにデータを分配します
  32. ( int i = 0; i < arr.length; i++) {
  33. 整数 インデックス= ( int ) Math.floor((arr[i] - minValue) / bucketSize);
  34.             バケット[インデックス] = arrAppend(バケット[インデックス], arr[i]);
  35.         } 
  36.  
  37. 整数arrIndex = 0;
  38.  for ( int [] バケット : バケット) {
  39.             バケットの長さが0以下の場合
  40. 続く;
  41.             }
  42.             // ここで挿入ソートを使用して各バケットをソートします
  43.             バケット = insertSort.sort(バケット);
  44.  for ( int値 : バケット) {
  45.                 arr[arrIndex++] = 値;
  46.             }
  47.         } 
  48.  
  49.  arrを返します。
  50.     } 
  51.  
  52.     /**
  53.      * 自動的に容量を拡張し、データを節約
  54.      *
  55.      * @param arr
  56.      * @パラメータ値
  57.      */
  58.     プライベートint [] arrAppend( int [] arr, int値) {
  59.         arr = Arrays.copyOf(arr, arr.length + 1);
  60.         arr[arr.length - 1] = 値;
  61.  arrを返します。
  62.     } 
  63.  
  64.  }

10. 基数ソート

基数ソートは、非比較の整数ソートアルゴリズムです。その原理は、整数を桁数に応じて異なる数値に分割し、各桁を個別に比較することです。整数は文字列 (名前や日付など) や浮動小数点数を特定の形式で表現することもできるため、基数ソートは整数に限定されません。

1. 基数ソートとカウンティングソートとバケットソート

基数ソートには 2 つの方法があります。

これら 3 つのソート アルゴリズムはすべてバケットの概念を使用しますが、バケットの使用方法には明らかな違いがあります。

  • 基数ソート: キー値の各桁に応じてバケットが割り当てられます。
  • カウントソート: 各バケットには 1 つのキー値のみが格納されます。
  • バケットソート: 各バケットには特定の範囲の値が格納されます。

2. LSD 基数ソートのアニメーションデモンストレーション

3. Javaコードの実装

  1. /**
  2.  * 基数ソート
  3.  * 負の数については、https://code.i-harness.com/zh-CN/q/e98fa9 を参照してください。
  4.  */
  5. パブリッククラスRadixSortはIArraySortを実装します{ 
  6.  
  7.     @オーバーライド
  8. 公共  int [] sort( int [] sourceArray) 例外をスローします {
  9.         //パラメータの内容を変更せずにarrをコピーする
  10. int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
  11.  
  12. 最大桁数を取得します。
  13.  radixSort(arr, maxDigit)を返します。
  14.     } 
  15.  
  16.     /**
  17.      * 最大桁数を取得する
  18.      */
  19.     プライベートint getMaxDigit( int [] arr) {
  20. 戻り値:
  21.  getNumLenght(maxValue)を返します。
  22.     } 
  23.  
  24.     プライベートint getMaxValue( int [] arr) {
  25. 整数最大値 = arr[0];
  26.  for ( int値: arr ) {
  27.             （最大値<値）の場合{
  28.                 最大値 = 値;
  29.             }
  30.         }
  31.  maxValueを返します。
  32.     } 
  33.  
  34.     保護されたint getNumLength(long num) {
  35.         数値 == 0 の場合
  36. 1 を返します。
  37.         }
  38. 整数長さ = 0;
  39.  (long temp = num; temp != 0; temp /= 10) {
  40.             長さ++;
  41.         }
  42. 長さを返します。
  43.     } 
  44.  
  45.     プライベートint [] radixSort( int [] arr, int maxDigit) {
  46. 整数mod = 10;
  47. 整数dev = 1; 
  48.  
  49.  ( int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  50.             // 負の数の場合を考えてみましょう。ここではキューの数を2倍にします。[0-9]は負の数に対応し、[10-19]は正の数（バケット+ 10）に対応します。
  51.  int [][] カウンター = 新しいint [mod * 2][0]; 
  52.  
  53.  ( int j = 0; j < arr.length; j++)の場合{
  54.  intバケット = ((arr[j] % mod) / dev) + mod;
  55.                 counter[bucket] = arrayAppend(counter[bucket], arr[j]);
  56.             } 
  57.  
  58. 整数位置 = 0;
  59.  for ( int [] バケット : カウンター) {
  60.  for ( int値 : バケット) {
  61.                     arr[pos++] = 値;
  62.                 }
  63.             }
  64.         } 
  65.  
  66.  arrを返します。
  67.     } 
  68.  
  69.     /**
  70.      * 自動的に容量を拡張し、データを節約
  71.      *
  72.      * @param arr
  73.      * @パラメータ値
  74.      */
  75.     プライベートint [] arrayAppend( int [] arr, int値) {
  76.         arr = Arrays.copyOf(arr, arr.length + 1);
  77.         arr[arr.length - 1] = 値;
  78.  arrを返します。
  79.     }
  80.  }

<<:  GoogleのオープンソースAIは92%の精度で音を区別できる

>>:  モノのインターネット業界は一時的な流行に過ぎないのでしょうか、それとも産業史上の重要な節目となるのでしょうか?

ブログ    

推薦する

「ディープラーニング」市場の動向を多面的に分析

[[192373]]業界分析2016 年、世界のディープラーニング市場規模は 2 億 2,700 万...

サーバーが過負荷状態です! GANで生成された肖像油絵は人気があり、一瞬でルネッサンス時代に戻ることができます

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載...

2019年のディープラーニングツールの概要

ディープラーニングツールディープラーニングの進歩は、ソフトウェア インフラストラクチャの進歩にも大き...

CMU 中国チームは、スタンフォード大学のエビ揚げロボットに勝る高エネルギーロボットを開発するために 18 万ドルを費やしました。完全自律操作、1時間で12種類のドアを開ける方法を学習

スタンフォード大学のエビ揚げロボットよりも強力なロボットが登場！最近、CMU の研究者たちは、オープ...

将来、人工知能に置き換えられない仕事が最も収益性が高くなるでしょう。それがどれか見てみましょう。

誰もが知っているように、昔は銀行に行って業務を処理するには長い列に並ばなければなりませんでした。業務...

Programiz: 多くの人がChatGPTを使ってプログラミングを学んでおり、Web開発分野はAIの影響を最も受けやすい

プログラマー育成ウェブサイトProgramizは10月18日、ChatGPTがプログラミング教育分野...

0コードの微調整大型モデルが人気で、わずか5ステップで、コストは150元と低い

0 コードの大規模モデルを20 ドル未満で微調整できますか?プロセスも非常に簡単で、必要なステップは...

ハンドルとペダルがない？アップルは2025年までに自動運転車を発売する予定

スペインの新聞「ヴァングアルディア」によると、アップルは2025年にハンドルもペダルもない自動車を発...

...

機械学習/ディープラーニング プロジェクトを始める 8 つの方法

[[392342]] [51CTO.com クイック翻訳]探索的データ分析から自動機械学習 (Aut...

...

技術的負債の高利クレジットカード: 最もよく知られているエンドツーエンドの機械学習プラットフォームを詳しく調べる

この記事は、公開アカウント「Reading the Core」（ID: AI_Discovery）か...

GPT-4を粉砕せよ！ Google DeepMind CEOが明かす：次世代の大規模モデルはAlphaGoと統合される

Googleは本当に全力を尽くしています。 AlphaGoとGPT-4に似た大規模モデルを組み合わせ...

ソフトウェア開発者の生産性を測定する価値はあるでしょうか?

ほとんどの企業はデジタル戦略に取り組んでおり、従業員の生産性を向上させる方法を模索していますが、同時...

...