一般的な Java バブルソートアルゴリズム: 昇順でソート-＆＃＆チュートリアル-php.cn

一般的な Java バブルソートアルゴリズム: 昇順でソート

Java バブルソート: 小規模なものから大規模なものまで、いくつかの一般的な記述方法、具体的なコード例が必要です

バブルソートは、隣接する 2 つの要素を繰り返し比較する単純なソートアルゴリズムです。シーケンス全体が順序付けされるまで、サイズ順序に従ってそれらを交換します。 Javaではバブルソートの一般的な記述方法や最適化方法がいくつかありますが、ここでは一般的な5つの記述方法と具体的なコード例を紹介します。

最初の書き方: 通常のバブルソート

通常のバブルソートは 2 レベルのループを直接ネストします。外側のループは比較のラウンド数を制御し、内側のループは特定の比較を実行します。そして交換します。

public static void bubbleSort1(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }

ログイン後にコピー

2 番目の書き方: 外側のループの最適化

1 番目の書き方に基づいて、1 回のソートで交換が行われない場合は、配列がすでに格納されていることを意味します。ご注文及び仕分けは早期に終了する場合がございます。この最適化を実現するには、スワップが発生したかどうかを記録するフラグビットを追加します。

public static void bubbleSort2(int[] arr) { int n = arr.length; boolean swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = true; } } if (!swapped) { break; } } }

ログイン後にコピー

3 番目の記述方法: 内部ループの最適化

2 番目の記述方法に基づくと、比較の各ラウンドで最大の要素が最後まで「バブル」されることがわかります。したがって、ラウンドあたりの内部ループの比較の数を徐々に減らすことができます。

public static void bubbleSort3(int[] arr) { int n = arr.length; int lastSwapIndex; for (int i = 0; i < n - 1; i++) { lastSwapIndex = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwapIndex = j + 1; } } i = n - lastSwapIndex - 2; } }

ログイン後にコピー

4 番目の記述方法: 内部ループと外部ループの最適化

3 番目の記述方法に基づいて、特定のラウンドの比較で配列が交換されない場合は、配列の背後にある要素はすでに順序が整っているため、ソートを早期に終了できます。

public static void bubbleSort4(int[] arr) { int n = arr.length; int lastSwapIndex, rightBoundary; rightBoundary = n - 1; for (int i = 0; i < n - 1; i++) { lastSwapIndex = 0; for (int j = 0; j < rightBoundary; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwapIndex = j + 1; } } rightBoundary = lastSwapIndex; if (rightBoundary <= 1) { break; } } }

ログイン後にコピー

5 番目の書き方: 外側のループと内側のループの最適化

4 番目の書き方に基づくと、各ラウンドの比較で最大の要素が見つかることがわかります。現在のラウンドを正しい場所に置きます。したがって、比較の各ラウンドで最大値と最小値の両方を見つけて並べ替えることができます。

public static void bubbleSort5(int[] arr) { int n = arr.length; int lastSwapIndex, leftBoundary, rightBoundary; leftBoundary = 0; rightBoundary = n - 1; while (leftBoundary < rightBoundary) { lastSwapIndex = 0; for (int j = leftBoundary; j < rightBoundary; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwapIndex = j + 1; } } rightBoundary = lastSwapIndex; for (int j = rightBoundary; j > leftBoundary; j--) { if (arr[j] < arr[j-1]) { int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; lastSwapIndex = j - 1; } } leftBoundary = lastSwapIndex; } }

ログイン後にコピー

上記はバブルソートの一般的な記述方法を5つ挙げましたが、それぞれの記述方法で最適化方法が異なるため、実際に使用する場合は状況に応じて適切な記述方法を選択してください。これらの最適化により、バブルソーティングの効率が向上し、ソーティング時間を短縮できます。

バブルソートは単純ですが、大規模なデータをソートする場合はパフォーマンスが低下します。したがって、実際のアプリケーションでは、クイックソート、マージソートなどのより効率的なソートアルゴリズムがより一般的に使用されます。

以上が一般的な Java バブルソートアルゴリズム: 昇順でソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。