並べ替えアルゴリズムの概要: バブル ソート

開発では、一連のデータを整然と配置する必要があることが多いため、複数またはそれ以上の並べ替えアルゴリズムを習得することが絶対に必要です

この記事では、より単純な並べ替えアルゴリズムの 1 つであるバブル ソートを紹介します

。

まず、バブル ソートを比較して学習するために、最も単純なアイデアを使用してソートを実装してみます。

問題: 配列内に要素 10 個のサイズの配列 (int str[10]) があります。データは順序付けされていません。次に、この順序なし配列を、小さいものから大きいものへ (添え字 0 から開始して) ソートされた配列にプログラムする必要があります。

アイデア: 質問の要件によれば、正しい結果は次のようになることは間違いありません: 1 2 3 4 5 6 7 8 9 10 これを行うには、比較して交換することを考えるのが最も単純で直接的な方法です。

まず、添字0の位置(str[0])に10個の数字のうち最小の数字を置きます

添字0の数字(str[0])と残りを組み合わせて、残りを比較し交換します9 個の数字 (下付き文字 0 の位置に小さい方を置きます)、最も小さい 10 個の数字を取得できます

最も小さい 10 個の数字が決定したら、次のステップは残りの 9 個を見つけることです。最小の数字で。

最小の数値が決まっているので、str[0]を動かさず、str[1]から直接開始し、残りの8つの数値と比較して交換し、9つの数値の中から小さいものを見つけて、添字が 1 になる位置 (str[1])

引き続きこのアイデアに従い、これら 10 個の数値を順序付けされた (小さい値から大きい値へ) 配列に変換します

コード:

#include <stdio.h>  
  
void swap(int *a, int *b); //交换两个数  
  
int main()  
{  
    int     str[10];  
    int     i, j;  
    //初始化数组为10 9 8 7 6 5 4 3 2 1  
    for (i = 0; i < 10; i++)  
    {  
        str[i] = 10 - i;  
    }  
    //排序，从a[0]开始排，从小到大  
    for (i = 0; i < 10; i++)  
    {  
        for (j = i + 1; j < 10; j++)  
        {  
            if (str[i] > str[j])  
            {  
                swap(&str[i], &str[j]);  
            }  
        }  
    }  
        //将十个数输出  
    for (i = 0; i < 10; i++)  
        printf("%d\n", str[i]);  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int     c;  
     c = *a;  
    *a = *b;  
    *b =  c;  
}

この方法は比較的簡単ですそれを実装します。しかし、欠点があります。元々前にあった小さい数字が後ろに置き換えられます

デモ:

開始: 9 4 5 6 8 3 2 7 10 1 (下付き文字は左から 0 ～ 9 です)右）上記の手順で比較・交換を行ってください

1回目：4 9 5 6 8 3 2 7 10 1

2回目：4 9 5 6 8 3 2 7 10 1

。 。 。 ：（交換不可）

5回目：3 9 5 6 8 4 2 7 10 1

6回目：2 9 5 6 8 3 4 7 10 1

。 。 。 : (交換なし)

10回目: 1 9 5 6 8 3 4 7 10 2

元の小さい数字が前にあり、一巡交換した後、後ろに配置されていることがわかります。

では、この欠点を解決するにはどうすればよいでしょうか?バブルソートが使えます

バブルソートとは何ですか？

次のように理解できます: (小さいものから大きいものに並べ替える) 異なるサイズの 10 個のバブルがあり、小さいバブルは下から上に向かって徐々に上昇し、1 回の横断の後、最小のバブルが最上位まで上昇します。一番上（下付き文字は 0）、次にこのように下から上に上昇し、バブルが 10 個揃うまで繰り返します。

バブルソートで最も重要な考え方は、2 つを比較し、2 つのうち小さい方を促進することです。

バブルソートの最悪の場合の時間計算量は O(n²)

コード:

#include <stdio.h>  
void swap(int *a, int *b);  
int main()  
{  
    int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};  
    int    i, j;  
    for (i = 0; i < 10; i++)  
    {  
        //每一次由底至上地上升  
        for (j = 9; j > i; j--)  
        {  
            if (array[j] < array[j-1])  
            {  
                    swap(&array[j], &array[j-1]);  
            }  
        }  
    }  
    for (i = 0; i < 10; i++)  
    {  
        printf("%d\n", array[i]);  
    }  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int    temp;  
    temp = *a;  
      *a = *b;  
      *b = temp;  
}

リスクソート アルゴリズムは小さいものを徐々に押し上げるだけであり、この記事で前述した欠点は発生しないため、ここでは説明しません。

ソートアルゴリズムの入門に関連するその他の記事: バブルソートについては、PHP 中国語 Web サイトに注目してください。