検索
ホームページJava&#&チュートリアルバブル ソート アルゴリズムを理解する (Java の例付き)

バブルソートの詳細説明: 簡単な並べ替えアルゴリズム

バブル ソートは、最も単純な並べ替えアルゴリズムの 1 つです。これは、隣接する要素を繰り返し比較し、順序が間違っている場合は交換することで機能します。たとえば、並べ替え順序が昇順の場合、隣接する要素が比較され、大きい要素が右側に配置されます。各反復では、ソートされていない要素のみを比較し、最大の要素を配列内のソートされていない要素の最後の位置に配置します。

このアルゴリズムは、水面に上昇する泡のように、反復ごとに要素が配列の右側に向かって移動するため、バブル ソートという名前が適切に付けられています。

バブルソートの仕組み

この配列を昇順に並べ替えたいとします:

Understanding Bubble Sort Algorithm (with Examples in Java)

最初の反復

最初の反復では、最大の要素を配列の末尾に移動しようとします。したがって、隣接する要素を繰り返し比較し、順序が間違っている場合は交換します。

Understanding Bubble Sort Algorithm (with Examples in Java)

正しい位置に移動された要素は並べ替えられたとみなされます。

次の反復

配列がソートされるまで、このプロセスがすべての反復で繰り返されます。ソートされた要素はすでに正しい順序になっているため、各反復ではソートされていない要素のみを比較します。

Understanding Bubble Sort Algorithm (with Examples in Java)

配列を n-1 回繰り返します。ここで、n は配列の長さです。つまり、配列には 6 つの要素があるため、配列を 5 回繰り返すだけです。これは、5 回目の反復の後、5 つの要素が正しい位置に配置され、ソートされていない最後の要素がソートされているとみなされるためです。すべての反復が完了すると、ソートされた配列が得られます。

バブルソートの実装

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

このコードを実行すると、コンソールに次の出力が表示されます:

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

バブル ソートのこの実装では、配列がすでにソートされている場合でも、毎回配列を反復処理します。コードをさらに最適化して、配列がソートされた後にソートを停止することができます。

バブルソートの最適化

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; 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;
    }
}

この実装では、既にソートされている配列をソートしようとすると、反復処理は 1 回だけ行われ、ソートが行われなくなると停止します。

バブルソートの複雑さ

時間計算量:

最良のケース (O(n)):

最良のシナリオは、入力配列がすでにソートされていることです。このアルゴリズムは配列を 1 回反復して並べ替えられているかどうかを確認するだけで、交換は実行しません。

平均ケース (O(n²)):

入力配列要素がランダムな順序である場合。アルゴリズムは複数回反復し、スワップを実行して配列を並べ替える必要があります。

最悪の場合 (O(n²)):

最悪のシナリオは、入力配列が逆順にソートされることです。このアルゴリズムは n-1 回の反復を経て、最大数のスワップを実行します。

空間複雑度 O(1):

バブル ソートはインプレース ソート アルゴリズムです。つまり、入力配列のサイズに比例する追加のメモリは必要ありません。

結論

バブル ソートは、理解と実装が簡単なアルゴリズムです。ただし、時間の複雑さが高いため、大規模なデータセットの処理には適していません。バブル ソートは、小さなデータ セットを扱う場合、または複雑さを気にしない場合に使用できます。

以上がバブル ソート アルゴリズムを理解する (Java の例付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、Svelte2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、SvelteMar 07, 2025 pm 06:09 PM

この記事では、2025年の上位4つのJavaScriptフレームワーク(React、Angular、Vue、Svelte)を分析し、パフォーマンス、スケーラビリティ、将来の見通しを比較します。 強力なコミュニティと生態系のためにすべてが支配的なままですが、彼らの相対的なポップ

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?Mar 17, 2025 pm 05:44 PM

この記事では、カフェインとグアバキャッシュを使用してJavaでマルチレベルキャッシュを実装してアプリケーションのパフォーマンスを向上させています。セットアップ、統合、パフォーマンスの利点をカバーし、構成と立ち退きポリシー管理Best Pra

node.js 20:キーパフォーマンスが向上し、新機能node.js 20:キーパフォーマンスが向上し、新機能Mar 07, 2025 pm 06:12 PM

node.js 20は、V8エンジンの改善、特により速いガベージコレクションとI/Oを介してパフォーマンスを大幅に向上させます。 新機能には、より良いWebセンブリのサポートと洗練されたデバッグツール、開発者の生産性とアプリケーション速度の向上が含まれます。

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Mar 17, 2025 pm 05:35 PM

Javaのクラスロードには、ブートストラップ、拡張機能、およびアプリケーションクラスローダーを備えた階層システムを使用して、クラスの読み込み、リンク、および初期化が含まれます。親の委任モデルは、コアクラスが最初にロードされ、カスタムクラスのLOAに影響を与えることを保証します

Spring Boot Snakeyaml 2.0 CVE-2022-1471問題修正Spring Boot Snakeyaml 2.0 CVE-2022-1471問題修正Mar 07, 2025 pm 05:52 PM

この記事では、リモートコードの実行を可能にする重大な欠陥であるSnakeyamlのCVE-2022-1471の脆弱性について説明します。 Snakeyaml 1.33以降のSpring Bootアプリケーションをアップグレードする方法は、このリスクを軽減する方法を詳述し、その依存関係のアップデートを強調しています

Iceberg:データレイクテーブルの未来Iceberg:データレイクテーブルの未来Mar 07, 2025 pm 06:31 PM

大規模な分析データセットのオープンテーブル形式であるIcebergは、データの湖のパフォーマンスとスケーラビリティを向上させます。 内部メタデータ管理を通じて、寄木細工/ORCの制限に対処し、効率的なスキーマの進化、タイムトラベル、同時wを可能にします

Javaで機能的なプログラミング技術を実装するにはどうすればよいですか?Javaで機能的なプログラミング技術を実装するにはどうすればよいですか?Mar 11, 2025 pm 05:51 PM

この記事では、Lambda式、Streams API、メソッド参照、およびオプションを使用して、機能プログラミングをJavaに統合することを調べます。 それは、簡潔さと不変性を通じてコードの読みやすさと保守性の改善などの利点を強調しています

キュウリのステップ間でデータを共有する方法キュウリのステップ間でデータを共有する方法Mar 07, 2025 pm 05:55 PM

この記事では、キュウリの手順間でデータを共有する方法、シナリオコンテキスト、グローバル変数、引数の合格、およびデータ構造を比較する方法を調べます。 簡潔なコンテキストの使用、記述など、保守性のためのベストプラクティスを強調しています

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

PhpStorm Mac バージョン

PhpStorm Mac バージョン

最新(2018.2.1)のプロフェッショナル向けPHP統合開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。