上位 10 の古典的なソートアルゴリズムの概要 (Java コード実装を含む)

最近、ソートアルゴリズムを勉強していて、多くのブログを読んでいます。インターネット上のいくつかの記事ではソートアルゴリズムが十分に説明されておらず、多くのコードが間違っていることがわかりました。たとえば、いくつかの記事では、「バケットソート」アルゴリズムで各バケットをソートするために、Collection.sort()関数を直接使用しています。これは望ましい効果を達成できますが、アルゴリズムの研究には受け入れられません。

そこで、ここ数日で読んだ記事に基づいて、ソートアルゴリズムの比較的完全な概要をまとめました。この記事のすべてのアルゴリズムは JAVA で実装されており、正しくデバッグした後にのみ公開されています。誤りがある場合は、ご指摘ください。

0. ソートアルゴリズムの説明

0.1 ソートの定義

キーに従ってオブジェクトのシーケンスをソートします。

0.2 用語

安定: a が元々 b の前にあり、a=b の場合、ソート後も a は b の前にあります。
不安定: a が元々 b の前にあり、a=b の場合、ソート後に a が b の後に表示されることがあります。
内部ソート: すべてのソート操作はメモリ内で実行されます。
外部ソート: データが大きすぎるため、データはディスク上に配置され、ディスクとメモリ間のデータ転送を通じてソートが実行されます。
時間の複雑さ: アルゴリズムの実行にかかる時間。
空間計算量: プログラムを実行するために必要なメモリの量。

参考: 安定ソートと不安定ソート

0.3 アルゴリズムの概要

画像用語集:

n: データサイズ
k: 「バケット」の数
インプレース: 一定のメモリを占有し、追加のメモリを占有しない
アウトプレース: 追加のメモリを占有します

0.4 アルゴリズムの分類

0.5 比較と非比較の違い

一般的なクイックソート、マージソート、ヒープソート、バブルソートなどは比較ソートに属します。最終的なソート結果の要素の順序は、要素間の比較によって決まります。各数字の位置を決定するには、他の数字と比較する必要があります。

バブルソートなどのソートアルゴリズムでは、問題のサイズは n であり、n 回の比較が必要なので、平均時間計算量は O(n²) です。マージソートやクイックソートなどのソートでは、分割統治法によって問題のサイズが logN 倍に縮小されるため、平均して時間計算量は O(nlogn) になります。

比較ソートの利点は、さまざまなサイズのデータに適用でき、データの分布に関係なくソートできることです。比較ソートは、ソートが必要なあらゆる状況に適用できると言えます。

カウンティングソート、基数ソート、バケットソートは非比較ソートです。非比較ソートは、各要素の前にいくつの要素が来るかを決定することによって行われます。配列 arr の場合、arr[i] の前にある要素の数を計算し、ソートされた配列内での arr[i] の位置を一意に決定します。

非比較ソートでは、各要素の前に存在する要素の数を決定するだけでよいため、1 回の走査で解決できます。アルゴリズムの時間計算量は O(n) です。

非比較ソートは時間の複雑さは低いですが、一意の位置を決定するためのスペースが必要です。したがって、データの規模とデータの配布には一定の要件があります。

1. バブルソート

バブルソートは単純なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。

このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。バブルソート入門: バブルソート

1.1 アルゴリズムの説明

隣接する要素を比較します。最初の値が 2 番目の値より大きい場合は、2 つを交換します。

隣接する要素の各ペアに対して同じ操作を実行します。最初のペアを先頭にして、最後のペアを末尾にして、最後の要素が最大の数値になるようにします。

最後の要素を除くすべての要素に対して上記の手順を繰り返します。

並べ替えが完了するまで、手順 1 ～ 3 を繰り返します。

1.2 アニメーションデモ

1.3 コードの実装

/**
 * バブルソート
 *
 * @param 配列
 * @戻る 
 */
公共 静的  int [] bubbleSort( int [] 配列) {
 （配列の長さ == 0）の場合
配列を返します。
 ( int i = 0; i < 配列の長さ; i++)の場合
( int j = 0; j < 配列の長さ - 1 - i; j++)の場合
 （配列[j + 1] < 配列[j]）の場合{
整数  temp = 配列[j + 1];
 配列[j + 1] = 配列[j];
 配列[j] = temp ;
 }
配列を返します。
 }

1.4 アルゴリズム分析

最良の場合: T(n) = O(n) 最悪の場合: T(n) = O(n2) 平均的な場合: T(n) = O(n2)

2. 選択ソート

最も安定したソートアルゴリズムの 1 つです。どのようなデータを入力しても、時間計算量は O(n2) なので、使用する場合はデータサイズが小さいほど効果的です。唯一の利点は、余分なメモリスペースを占有しないことです。理論的に言えば、選択ソートはおそらくほとんどの人が思い浮かべる最も一般的なソート方法です。

選択ソートはシンプルで直感的なソートアルゴリズムです。仕組み: まず、ソートされていないシーケンス内の最小 (最大) の要素を見つけて、ソートされたシーケンスの先頭に格納します。次に、残りのソートされていない要素から最小 (最大) の要素を探し、ソートされたシーケンスの最後に配置します。すべての要素がソートされるまでこれを繰り返します。選択ソートの紹介: 選択ソート

2.1 アルゴリズムの説明

n レコードの直接選択ソートは、n-1 ラウンドの直接選択ソートによって実行され、順序付けられた結果が得られます。具体的なアルゴリズムは次のように説明されます。

初期状態: 順序付けされていない領域はR[1..n]で、順序付けされた領域は空です。

i番目のソート（i=1,2,3…n-1）が開始されると、現在の順序付けされた領域と順序付けされていない領域はそれぞれR[1..i-1]とR(i..n)になります。このソートパスは、現在の順序付けられていない領域から最小のキーワードを持つレコード R[k] を選択し、それを順序付けられていない領域の最初のレコード R と交換します。これにより、R[1..i] と R[i+1..n) は、それぞれレコードが 1 つ多い新しい順序付けられた領域と、レコードが 1 つ少ない新しい順序付けられていない領域になります。

n-1 ラウンド後、配列はソートされます。

2.2 アニメーションデモ

2.3 コードの実装

/**
 * 選択ソート
 * @param 配列
 * @戻る 
 */
公共 静的  int [] 選択ソート( int [] 配列) {
 （配列の長さ == 0）の場合
配列を返します。
 ( int i = 0; i < 配列の長さ; i++) {
最小インデックス = i;
 ( int j = i; j < 配列の長さ; j++) {
 if (array[j] < array[minIndex]) //最小の数値を見つける
 minIndex = j; //最小数のインデックスを保存する
 }
整数  temp = 配列[最小インデックス];
 配列[最小インデックス] = 配列[i];
 配列[i] = temp ;
 }
配列を返します。
 }

2.4 アルゴリズム分析

最良の場合: T(n) = O(n2) 最悪の場合: T(n) = O(n2) 平均的な場合: T(n) = O(n2)

3. 挿入ソート

挿入ソートのアルゴリズムの説明は、シンプルで直感的なソートアルゴリズムです。これは、順序付けられたシーケンスを構築することによって機能します。ソートされていないデータの場合は、ソートされたシーケンス内で後ろから前へスキャンし、対応する位置を見つけて挿入します。挿入ソートは通常、インプレースソート（つまり、O(1)の追加スペースのみを必要とするソート）によって実装されます。したがって、後ろから前へスキャンするプロセスでは、最新の要素を挿入するためのスペースを確保するために、ソートされた要素を繰り返し後方に移動する必要があります。挿入ソート: 直接挿入ソート

3.1 アルゴリズムの説明

一般的に、挿入ソートは配列上でインプレースで実装されます。具体的なアルゴリズムは次のように説明されます。
最初の要素から始めて、要素はソートされているとみなすことができます。
次の要素を取り出し、ソートされた要素の順序で後ろから前へスキャンします。
要素（すでにソートされている）が新しい要素より大きい場合は、要素を次の位置に移動します。
ソートされた要素が新しい要素以下になる位置が見つかるまで、手順 3 を繰り返します。
その位置に新しい要素を挿入した後;
手順2～5を繰り返します。

3.2 アニメーションによるデモンストレーション

3.2 コードの実装

/**
 * 挿入ソート
 * @param 配列
 * @戻る 
 */
公共 静的  int [] 挿入ソート( int [] 配列) {
 （配列の長さ == 0）の場合
配列を返します。
整数 現在;
 ( int i = 0; i < 配列の長さ - 1; i++) {
現在の配列[i + 1];
プレインデックス = i;
 (preIndex >= 0 &&現在の配列< [preIndex]) {
 配列[preIndex + 1] = 配列[preIndex];
 プレインデックス--;  
 }
 配列[preIndex + 1] =現在の;
 }
配列を返します。
 }

3.4 アルゴリズム分析

最良の場合: T(n) = O(n) 最悪の場合: T(n) = O(n2) 平均的な場合: T(n) = O(n2)

4. シェルソート

シェルソートは、1959 年にドナルドシェルによって提案されたソートアルゴリズムです。ヒルソートも挿入ソートの一種です。これは、縮小増分ソートとも呼ばれる単純な挿入ソートのより効率的なバージョンです。同時に、このアルゴリズムは O(n2) を突破した最初のアルゴリズムの 1 つです。挿入ソートとは異なり、より遠い要素を優先します。シェルソートは、縮小増分ソートとも呼ばれます。シェルソート: シェルソート

シェルソートは、以下の表の一定の増分に従ってレコードをグループ化し、直接挿入ソートアルゴリズムを使用して各グループをソートします。増分が徐々に減少するにつれて、各グループに含まれるキーワードが増えていきます。増分が 1 に減少すると、ファイル全体が 1 つのグループに分割され、アルゴリズムが終了します。

4.1 アルゴリズムの説明

シェルソートの基本的な手順を見てみましょう。ここでは、増分ギャップ = 長さ/2 を選択し、増分を減らしてギャップ = ギャップ/2 を継続します。この増分選択は、増分シーケンスと呼ばれるシーケンス {n/2、(n/2)/2…1} で表すことができます。シェルソートの増分シーケンスの選択と証明は難しい数学的問題です。私たちが選択した増分シーケンスは比較的一般的であり、ヒル増分と呼ばれるヒルによって推奨された増分でもありますが、実際にはこの増分シーケンスは最適ではありません。ここではヒル増分を例として使用します。

まず、ソートするレコードシーケンス全体をいくつかのサブシーケンスに分割し、直接挿入してソートします。具体的なアルゴリズムの説明は次のとおりです。

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

4.2 プロセスのデモンストレーション

4.3 コードの実装

/**
 * シェルソート
 *
 * @param 配列
 * @戻る 
 */
公共 静的  int [] ShellSort( int [] 配列) {
 int len = 配列.長さ;
整数 温度、ギャップ = 長さ / 2;
 ギャップ > 0 の場合
( int i = ギャップ; i < len; i++) {
 temp = 配列[i];
 int preIndex = i - ギャップ;
 (preIndex >= 0 && array[preIndex] > temp ) の間 {
 配列[preIndex + ギャップ] = 配列[preIndex];
 preIndex -= ギャップ;
 }
 配列[preIndex + ギャップ] = temp ;
 }
 ギャップ /= 2;
 }
配列を返します。
 }

4.4 アルゴリズム分析

最良の場合: T(n) = O(nlog2 n) 最悪の場合: T(n) = O(nlog2 n) 平均的な場合: T(n) = O(nlog2n)

5. マージソート

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

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。マージソートは安定したソート方法です。順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けます。 2 つの順序付きリストが 1 つの順序付きリストに結合される場合は、2 方向の結合と呼ばれます。

5.1 アルゴリズムの説明

長さ n の入力シーケンスを長さ n/2 の 2 つのサブシーケンスに分割します。

これら 2 つのサブシーケンスにそれぞれマージソートが適用されます。

2 つのソートされたサブシーケンスを最終的なソートされたシーケンスにマージします。

5.2 アニメーションによるデモンストレーション

5.3 コードの実装

/**
 * マージソート
 *
 * @param 配列
 * @戻る 
 */
公共 静的  int []MergeSort( int [] 配列) {
 array.length < 2 の場合、配列を返します。
 int mid = 配列の長さ / 2;
 int [] left = Arrays.copyOfRange(配列、0、mid);
 int [] right = Arrays.copyOfRange(array, mid, array.length);
 merge(MergeSort(左), MergeSort(右) )を返します。
 }
 /**
 * マージソート - 2つのソートされた配列を1つのソートされた配列に結合する
 *
 * @param左 
 * @param右 
 * @戻る 
 */
公共 静的  int [] マージ ( int []左、 int []右) {
 int [] 結果 = 新しいint [左.length +右.length];
 （ int  インデックス= 0、i = 0、j = 0;インデックス< result.length;インデックス++) {
 (i >=左.長さ)の場合
 結果[インデックス] =右[j++];
そうでない場合 (j >=右.length)
 結果[インデックス] =左[i++];
そうでない場合 (左[i] >右[j])
 結果[インデックス] =右[j++];
それ以外 
 結果[インデックス] =左[i++];
 }
結果を返します。
 }

5.4 アルゴリズム分析

最良の場合: T(n) = O(n) 最悪の場合: T(n) = O(nlogn) 平均的な場合: T(n) = O(nlogn)

6. クイックソート

クイックソートの基本的な考え方は、ソートプロセスを通じて、ソートするレコードを 2 つの独立した部分に分けることです。レコードの 1 つの部分のキーワードが他の部分のキーワードよりも小さい場合、レコードの 2 つの部分を個別にソートして、シーケンス全体の順序を実現できます。クイックソート: クイックソート

6.1 アルゴリズムの説明

クイックソートは、分割統治アルゴリズムを使用してリストを 2 つのサブリストに分割します。具体的なアルゴリズムは次のように説明されます。

シーケンスから要素を選択することを「ピボット」と呼びます。

基本値より小さいすべての要素が基本値の前に配置され、基本値より大きいすべての要素が基本値の後に配置されるようにシーケンスを並べ替えます (同じ数字をどちらの側にも配置できます)。このパーティションを抜けると、ベンチマークはシリーズの途中になります。これはパーティション操作と呼ばれます。

基本値より小さい要素の部分シーケンスと基本値より大きい要素の部分シーケンスを再帰的にソートします。

6.2 アニメーションによるデモンストレーション

6.3 コードの実装

/**
 * クイックソート法
 * @param 配列
 * @param 開始
 * @param終了 
 * @戻る 
 */
公共 静的  int [] クイックソート( int [] 配列, int開始, int  終わり） {
 （array.length < 1 || start < 0 || end >= array.length || start > end ）の場合、戻り値 ヌル;
 int smallIndex = パーティション(配列、開始、終了);
 (smallIndex > 開始)の場合
 クイックソート(配列、開始、小さいインデックス - 1);
 (smallIndex <終了)の場合
 クイックソート(配列、smallIndex + 1、終了);
配列を返します。
 }
 /**
 * クイックソートアルゴリズム - パーティション
 * @param 配列
 * @param 開始
 * @param終了 
 * @戻る 
 */
公共 静的  intパーティション( int [] 配列、 int開始、 int  終わり） {
 intピボット = ( int ) (開始 + Math.random() * (終了- 開始 + 1));
 int smallIndex = 開始 - 1;
 swap(配列、ピボット、終了);
 ( int i = 開始; i <=終了; i++)の場合
 if (配列[i] <= 配列[終了]) {
 小さいインデックス++;
 (i > 小さいインデックス)
 swap(配列、i、smallIndex);
 }
 smallIndexを返します。
 }
 /**
 * 配列内の2つの要素を交換する
 * @param 配列
 * @パラメータ i
 * @param j
 */
公共 静的void swap( int [] 配列、 int i、 int j) {
整数  temp = 配列[i];
 配列[i] = 配列[j];
 配列[j] = temp ;
 }

6.4 アルゴリズム分析

最良の場合: T(n) = O(nlogn) 最悪の場合: T(n) = O(n2) 平均的な場合: T(n) = O(nlogn)

7. ヒープソート

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

7.1 アルゴリズムの説明

ソートされるキーワードの初期シーケンス (R1、R2…Rn) は、初期の順序付けられていない領域である大きなヒープ内に構築されます。

一番上の要素R[1]を最後の要素R[n]と入れ替えると、新しい順序なし領域（R1、R2、... Rn-1）と新しい順序付き領域（Rn）が得られ、R[1、2、... n-1] <= R[n]となります。

交換後の新しいヒープ最上部R[1]はヒープの特性に違反する可能性があるため、現在の順序付けされていない領域（R1、R2、…Rn-1）を新しいヒープに合わせて調整し、R[1]を順序付けされていない領域の最後の要素と再度交換して、新しい順序付けされていない領域（R1、R2、…Rn-2）と新しい順序付けされた領域（Rn-1、Rn）を取得する必要があります。順序付けられた領域内の要素の数が n-1 になるまでこのプロセスを繰り返し、ソートプロセス全体が完了します。

7.2 アニメーションによるデモンストレーション

7.3 コードの実装

注: ここでは完全な二分木のいくつかのプロパティが使用されています。

http://www.cnblogs.com/guoyaohua/p/8595289.html

 //配列の長さを記録するグローバル変数を宣言します。
静的 長さ;
 /**
 * ヒープソートアルゴリズム
 *
 * @param 配列
 * @戻る 
 */
公共 静的  int [] ヒープソート( int [] 配列) {
 len = 配列の長さ;
 if (len < 1)配列を返します。
 //1. 最大ヒープを構築する
 最大ヒープを構築(配列)。
 //2. ループしてヒープの最初（最大）の位置と最後の位置を入れ替え、最大ヒープを再調整します。
 （長さ＞0）の間{
 swap(配列、0、長さ - 1);
 長さ--;  
 ヒープを調整します(配列、0);
 }
配列を返します。
 }
 /**
 * 最大ヒープを作成する
 *
 * @param 配列
 */
公共 静的void buildMaxHeap( int []配列) {
 //最後の非リーフノードから上に向かって最大ヒープを構築します
for ( int i = (len/2 - 1); i >= 0; i --) { // @让发会呆 さん、リマインダーをありがとう。これは i = (len/2 - 1) であるべきです 
 ヒープを調整します(配列、i);
 }
 }
 /**
 * 最大ヒープになるように調整する
 *
 * @param 配列
 * @パラメータ i
 */
公共 静的void調整ヒープ( int []配列、 inti ){
最大インデックス= i;
 //左サブツリーがあり、左サブツリーが親ノードよりも大きい場合は、最大ポインタを左サブツリーに向けます
 if (i * 2 < len && array[i * 2] > array[maxIndex])
 最大インデックス = i * 2;
 //右サブツリーがあり、右サブツリーが親ノードよりも大きい場合は、最大ポインタを右サブツリーに向けます
 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
 最大インデックス = i * 2 + 1;
 //親ノードが最大値でない場合は、親ノードを最大値と交換し、親ノードと交換したノードの位置を再帰的に調整します。
 （最大インデックス!= i）の場合{
 swap(配列、最大インデックス、i);
 ヒープを調整します(配列、最大インデックス);
 }
 }

7.4 アルゴリズム分析

最良の場合: T(n) = O(nlogn) 最悪の場合: T(n) = O(nlogn) 平均的な場合: T(n) = O(nlogn)

8. カウントソート

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

カウンティングソートは安定したソートアルゴリズムです。カウントソートでは追加の配列 C が使用されます。ここで、i 番目の要素は、ソートする配列 A 内で値が i に等しい要素の数です。次に、配列 C を使用して、配列 A 内の要素を正しい位置に配置します。整数のみをソートできます。

8.1 アルゴリズムの説明

ソートする配列内の最大要素と最小要素を検索します。
配列内の値 i を持つ各要素の出現回数を数え、それを配列 C の i 番目の項目に格納します。
すべてのカウントを合計します (C の最初の要素から始めて、各項目を前の項目に追加します)。
ターゲット配列を逆順に入力します。つまり、各要素 i を新しい配列の C(i) 番目の項目に配置し、要素が配置されるたびに C(i) から 1 を減算します。

8.2 アニメーションデモンストレーション

8.3 コードの実装

/**
 * カウントソート
 *
 * @param 配列
 * @戻る 
 */
公共 静的  int [] CountingSort( int [] 配列) {
 if (array.length == 0)配列を返します。
 intバイアス、最小値= 配列[0]、最大値= 配列[0];
 ( int i = 1; i < 配列の長さ; i++) {
 （配列[i] >最大値）の場合
最大値= 配列[i];
 （配列[i] < min ）の場合
min = 配列[i];
 }
 バイアス = 0 -最小;
 int [] バケット = 新しいint [最大値-最小値+ 1];
 配列.fill(バケット、0);
 ( int i = 0; i < 配列の長さ; i++) {
 バケット[配列[i] + バイアス]++;
 }
整数 インデックス= 0、i = 0;
 while (インデックス< 配列の長さ ) {
 バケット[i]が0の場合
 配列[インデックス] = i - バイアス;
 バケット[i] --;  
インデックス++;
 }それ以外 
 私は++;
 }
配列を返します。
 }

8.4 アルゴリズム分析

入力要素が 0 から k までの n 個の整数の場合、実行時間は O(n + k) です。カウンティングソートは比較ソートではなく、そのソート速度はどの比較ソートアルゴリズムよりも高速です。カウントに使用する配列 C の長さは、ソートする配列内のデータの範囲（ソートする配列の最大値と最小値の差に 1 を加えた値）に依存するため、データ範囲が大きい配列の場合、カウントソートには多くの時間とメモリが必要になります。

最良の場合: T(n) = O(n+k) 最悪の場合: T(n) = O(n+k) 平均的な場合: T(n) = O(n+k)

9. バケットソート

バケットソートは、カウントソートのアップグレード版です。これは関数のマッピング関係を利用しますが、その効率の鍵はこのマッピング関数の決定にあります。

バケットソートは、入力データが均一に分散されていると想定し、データを有限数のバケットに分割し、各バケットを個別にソートすることによって機能します (別のソートアルゴリズムを使用するか、バケットソートを再帰的に使用し続ける可能性があります)。

9.1 アルゴリズムの説明

各バケットに配置できる異なる値の数を表す BucketSize を人為的に設定します (たとえば、BucketSize==5 の場合、バケットには数字 {1、2、3、4、5} を格納できますが、容量は無制限、つまり 3 を 100 個格納できます)。
入力データを走査し、データを対応するバケットに 1 つずつ格納します。
空でない各バケットをソートします。他のソート方法を使用することも、バケットソートを再帰的に使用することもできます。
空ではないバケットからのソートされたデータを結合します。

バケットソートを再帰的に使用して各バケットをソートする場合、バケット数が 1 のときは、次のサイクルでバケット数を増やすために BucketSize を手動で減らす必要があることに注意してください。そうしないと、無限ループに陥り、メモリオーバーフローが発生します。

9.2 画像デモンストレーション

9.3 コードの実装

/**
 * バケットソート
 *
 * @param 配列
 * @param バケットサイズ
 * @戻る 
 */
公共 静的ArrayList< Integer > BucketSort(ArrayList< Integer > array, int bucketSize) {
 配列 == null || 配列サイズ( ) < 2 の場合
配列を返します。
整数 最大値= array.get(0),最小値= array.get(0);
 // 最大値と最小値を見つける
( int i = 0; i < array.size ( ) ); i++) {
 （配列.get(i) >最大値）の場合
最大値= 配列.get(i);
 （配列.get(i) < min ）の場合
min = 配列.get(i);
 }
 intバケット数 = (最大-最小) / バケットサイズ + 1;
 ArrayList<ArrayList< Integer >> bucketArr = new ArrayList<>(bucketCount);
 ArrayList<整数> resultArr = new ArrayList<>();
 ( int i = 0; i < バケットカウント; i++) {
 bucketArr.add (新しいArrayList<Integer> ( ));
 }
 ( int i = 0; i < array.size ( ) ); i++) {
 バケットArr.get((array.get(i) - min ) / バケットサイズ) .add (array.get(i));
 }
 ( int i = 0; i < バケットカウント; i++) {
 if (bucketSize == 1) { // ソートされた配列に重複した数字がある場合、エラーを指摘してくれた@见风任然是风に感謝します
( int j = 0; j < bucketArr.get(i) .size (); j++)の場合
 結果Arr.add (bucketArr.get(i).get(j));
 }それ以外{
 （バケット数 == 1）の場合
 バケットサイズ--;  
 ArrayList< Integer > temp = BucketSort(bucketArr.get(i), bucketSize);
 ( int j = 0; j < temp . size (); j++)の場合
 結果Arr.add ( temp.get (j));
 }
 }
結果Arrを返します。
 }

9.4 アルゴリズム分析

バケットソートでは、最良の場合でも線形時間 O(n) が使用されます。バケットソートの時間計算量は、各バケット間のデータのソートの時間計算量に依存します。これは、他の部分の時間計算量が O(n) であるためです。当然ですが、バケットが小さいほど、バケット間のデータが少なくなり、ソートにかかる時間も短くなります。ただし、それに応じてスペースの消費量も増加します。

最良の場合: T(n) = O(n+k) 最悪の場合: T(n) = O(n+k) 平均的な場合: T(n) = O(n2)

10. 基数ソート

基数ソートも非比較ソートアルゴリズムであり、最下位ビットから始めて各ビットを O(kn) の複雑度でソートします。ここで、k は配列の最大桁数です。

基数ソートでは、まず下位の順序でソートし、次に集計し、次に上位の順序でソートし、次に集計し、これを最高順位まで繰り返します。一部の属性には優先順位があり、最初に低い優先順位で並べ替え、次に高い優先順位で並べ替える場合があります。最終的な順序は、優先度の高いものが最初になり、優先度が同じ場合は優先度の低いものが最初になります。基数ソートは、個別のソートと個別のコレクションに基づいているため、安定しています。基数ソート: 基数ソート

10.1 アルゴリズムの説明

配列内の最大数を取得し、桁数を取得します。

arr は元の配列であり、最下位ビットから始まり、各ビットが取得されて基数配列が形成されます。

カウントによって基数をソートします (カウントソートは狭い範囲の数値に適しているという事実を利用します)。

10.2 アニメーションデモンストレーション

10.3 コードの実装

/**
 * 基数ソート
 * @param 配列
 * @戻る 
 */
公共 静的  int [] RadixSort( int [] 配列) {
 （配列 == null || 配列の長さ < 2）の場合
配列を返します。
 // 1. 最初に最大数の桁数を計算します。
整数 最大値= 配列[0];
 ( int i = 1; i < 配列の長さ; i++) {
 max = Math.max ( max 、配列[i]);
 }
整数最大桁数 = 0;
 （最大!= 0）の間{
最大/= 10;
 最大桁数++;
 }
整数mod = 10、div = 1;
 ArrayList<ArrayList< Integer >> bucketList = new ArrayList<ArrayList< Integer >>();
 ( int i = 0; i < 10; i++)の場合
 bucketList.add (新しいArrayList<Integer> ( ));
 ( int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
 ( int j = 0; j < 配列の長さ; j++) {
 int num = (配列[j] % mod) / div;
 bucketList.get(num) .add (配列[j]);
 }
整数 インデックス= 0;
 ( int j = 0; j < bucketList.size ( ) ; j++) {
 ( int k = 0; k < bucketList.get(j) .size (); k++)の場合
 配列[インデックス++] = bucketList.get(j).get(k);
 バケットリストを取得します。
 }
 }
配列を返します。
 }