データ構造シリーズを簡単に読み取る:早操列図解バブルソート

一、前に言う
いつも分かりやすい文章を书きたいと思っています.普段読んでいる本や文章の多くは见るのがつらいので、もちろん、书くのが悪いというわけではありませんが、あまり基础がないとか、基础がよくないとか、相対的に理解しにくいということです.
このシリーズは主に分かりやすいデータ構造とアルゴリズムの文章を書くと同時に、この方面の知識を再理解するのに役立ちます.
データ構造とアルゴリズムの冒頭として、やはりソートアルゴリズムを第一部とする内容として、この一連の文章は多くの理論的性質の知識にかかわるものではないことに注意しなければならない.理論的性質の知識を学ぶ必要がある場合は、関連するデータ構造とアルゴリズムの本を見ることができます.
二、バブルソートアルゴリズム
この一連の第1部として,主にソートアルゴリズムについて説明する.小さい頃から、私たちは少なくとも20年前に学校で過ごしました.キャンパス生活は私から見ればとても素晴らしいので、今でもキャンパスで生活しています.私たちが本を読む段階で、よく並んでいるときに出会うのではないでしょうか.みんながこのシーンをよく知っているので、並んでソートアルゴリズムを説明します.
バブルアルゴリズムは私たちが最もよく知っているアルゴリズムであり、私たちが最もよく知っている列でもあるはずです.よく知っている以上、今日はバブルソートの列を作りましょう.
今朝、先生は私たちに運動場に行って朝の体操をするように言った.朝の体操をする前に、列に並ぶ必要がある.列に並ぶには列があるのではないでしょうか.では、先生は今日私たちに身長の低い順に並ぶように要求しました.
そこで、私达は朝すぐにいっしょに运动场に着いて、全部で5人が运动场に着いて、さっき行った时、列はきっと散ったでしょう、この时の列は次のようです:0番目の位置の駅の明ちゃん、1番目の位置の駅の海、2番目の位置の駅の刘さん、3番目の位置の駅の李さん、5番目の位置の駅の爱ちゃん.
そこで先生(先生がプログラマーだと仮定して、皮一)は私たちに泡の順番に並ぶ方法に従って列を作るように要求しました.一人一人の身長を比較して、次の位置の同級生より高いなら、位置を変えてください.
さあ、学生たちは先生の指示を聞いてから、学生たちは出発し始めました.
0番目の位置の明ちゃんと1番目の位置の海ちゃんが身長を比べてみると、1番目の位置の海ちゃん(1.80 m)が0番目の位置の海ちゃん(1.60 m)より高いことに気づき、動かなかったので、初めて並んだ後も行列は変わらなかった.
それから、第1の位置の上の小海の学友はまた第2の位置の上の小劉の学友と身長を比べたいと思って、第1の位置の上の小海の学友が第2の位置の上の小劉の学友より高いことを発見して、だから、彼らは位置を交換します.
すると、行列が次のようになり、小海と劉さんは位置を変えた.
それから、2番目の位置の小海さんは、3番目の位置の李さんと身長を比べてみると、2番目の位置の小海さんは3番目の位置の李さんより高いので、位置を交換する必要があります.
この时、列は次のようになって、海と李さんが入れ替わりました.
次に3番目の位置の小海さんと4番目の位置の小愛さんを身長比較したところ、3番目の位置の小海さんは4番目の位置の小愛さんより高いことがわかりました.
交換後、こうなりました.
その結果,この並べ替え法により,最高の小海が2番目の位置から最後の位置に走ったことが分かった.
はい、今最も高い海の位置はすでに確定して、私达は彼を放っておいて、私达はまた0番目の位置の上の学友から始めて、0番目の位置の小明の学友と1番目の位置の小劉の学友は身長を比較して、小明の身長が小劉より低いことを発見して、だから列は維持していません.
次に、1番目の位置の劉さんと2番目の位置の李さんを比較すると、劉さんは李さんより高いので、位置を交換する必要があります.
交換後、次の列になりました
そして、2番目の位置の劉ちゃんと隣の3番目の位置の愛ちゃんが身長を比べていると、愛ちゃんが劉ちゃんより高いことがわかったので、位置を交換しない
最後の位置の小海は第1ラウンドが彼が一番高いことを知っているので、彼と比較しないので、このラウンドが終わった後、私たちはシーケンス全体が秩序正しくなっていることを発見しました.列の変化を見てみましょう.
この列に並んでいるうちに、泡のソートの考えを見つけたのではないでしょうか.
第1回目、第1の位置の上の学友は始めて、个々の比较の身长、もし第0の位置の学友は第1の位置の学友より高いならば、位置を交换して、さもなくば、位置を交换しないで、それから、第1の位置は第2の位置の学友と比较して身长、もし第1の位置の学友は第2の位置の学友より高いならば、位置を交换して、さもなくば交换しないで、このように押して、最高の同級生は最後の位置に着くだろう.
第2回目、やはり第1の位置の上の学友から始めて、第1の学友と第2の学友は比较して、もし第1の学友が第2の学友より高いならば、位置を交换して、さもなくば不変で、それから、第2の位置の上の学友と第3の位置の学友は比较して、もし第2の位置の上の学友が高いならば、位置を交换して、さもなくば交换しません.今回は、一番高い同級生が最後の位置にいるのを初めて見つけたので、最後の位置を比較する必要はありません.
列が全部並ぶまで.
ここまで来たら、泡立ちソートの考えが分かったと思います.
次に、コードの実装を見てみましょう(ここではJavaコード実装を使用します).

public static void bubbleSort(int[] arr) {
        //      ，     1，    。
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int e = 0; e < arr.length - 1; e++) {//            " "      
            for (int i = 0; i < n-1-e; i++) {//n-1-e:-1      0    ，-e                 ，        。
                if (arr[i] > arr[i + 1]) {//         
                    swap(arr, i, i + 1);//    
                }
            }
        }
    }

    /**
     *       
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

パフォーマンス分析
最悪時間複雑度:O(n^2)最適時間複雑度:すでに秩序化されている場合、最適時間複雑度をO(n)平均時間複雑度:O(n^2)に必要な補助空間:O(1)安定性:安定性説明:ソートが安定しているかどうかは、ソートのたびにシーケンス全体の位置が変化するかどうかを見ることです.
文章には不適切な点があります.指摘を歓迎します.微信が好きなら、私のことにも注目してください.
微信公衆番号: java、良質な学習資源を獲得する.