アルゴリズム2-バブルソート

アルゴリズムの説明
前の文章では、私たちがソートする必要がある数字を保存するのに十分な空間を申請することを基本としています.この方法には、スペースを非常に浪費する弊害があります.例えば、ソートする必要がある数字の範囲は0-1000000の間で、私たちはa[1000001]の空間を申請する必要がありますが、あなたはいくつかの数字をソートするだけかもしれません.この問題を解決するために, という新しいソート方法があった.
バブルソートの基本的な考え方は、隣接する2つの要素を比較するたびに、順序が間違っていれば交換することです.
アルゴリズムコード
私たちはまずコードをつけてから説明します.

void bubble_sort() {
    int a[100],i,j,t,n;
    scanf("%d",&n); //       ，      n  
    for (i = 1; i <= n; i++) {
        scanf("%d",&a[i]); //           
    }
    //          
    for (i = 1; i <= n-1; i++) { //   n   ，     n-1 
        for (j = 1; j <= n-i; j++) {    //                      
            if (a[j] < a[j+1]) {
                t       = a[j];
                a[j]    = a[j+1];
                a[j+1]  = t;
            }
        }
    }
    
    for (i = 1; i <= n; i++) {
        printf("%d ",a[i]);
    }
}

アルゴリズムの説明
たとえば、12,35,99,18,76という数字を大きくから小さく並べ替える必要があります.つまり、私たちの核心思想は です.

の第1ステップは第1ビットと第2ビットを比較し、12は35よりも小さく、この2つの数の位置を交換し、交換後のソート35,12,99,18,76であることが分かった.次に2位と3位の比較を続けたところ,12は99より小さく,交換位置を継続し,交換後のソート35，99，12，18，76であった.3位と4位の比較を続けると,12は18より小さく,交換位置は35，99，18，12，76の順であった.再び4位と5位を比較すると,12は76より小さく,交換位置,交換後の順序は35，99，18，76，12であった.5-1回を経て、最後の数字が最小であることがわかりました.ここでは5の数字の中で最も小さいものを帰位しただけです.

2 2 2回目は5位のうち上位4位を比較するだけです.並べ替え後の順序は99，35，76，18，12

である.

の3回目は、上位3位をソートするだけです.ソート後の順序は99，76，35，18，12です.

第4回目は、上位2位をソートする必要があります.ソート後の順序は99，76，35，18，12です.ここで,我々が並べ替え完了したバブル並べ替えのコアアルゴリズムは二重引き出しサイクルであり,バブル並べ替えの時間的複雑さはO(N 2)

であることが容易にわかる.