バブルソートの 3 つの実装-PHP开发-php.cn

バブルソートの 3 つの実装

高洛峰

リリース： 2016-12-19 13:15:36

オリジナル

1342 人が閲覧しました

バブルソートは理解と実装が非常に簡単で、例として小さいものから大きいものへのソートを取り上げます:

配列の長さが N であると仮定します。

1.前後の隣接する 2 つのデータを比較し、前者のデータが後者のデータより大きい場合、2 つのデータを交換します。

2.このようにして、配列の 0 番目のデータから N-1 番目のデータまで移動した後、最大のデータは配列の N-1 番目の位置に「沈みます」。

3. N=N-1。N が 0 でない場合は、前の 2 つの手順を繰り返します。そうでない場合は、並べ替えが完了します。

定義上、コードを書くのは簡単です:

//冒泡排序1  
void BubbleSort1(int a[], int n)  
{  
       int i, j;  
       for (i = 0; i < n; i++)  
              for (j = 1; j < n - i; j++)  
                     if (a[j - 1] > a[j])  
                            Swap(a[j - 1], a[j]);  
}

ログイン後にコピー

これを最適化してフラグを設定しましょう。この旅行で交換が発生した場合は true、それ以外の場合は false です。もちろん、1回の旅行で交換がなければ、仕分けは完了したことになります。

//冒泡排序2  
void BubbleSort2(int a[], int n)  
{  
       int j, k;  
       bool flag;  
  
       k = n;  
       flag = true;  
       while (flag)  
       {  
              flag = false;  
              for (j = 1; j < k; j++)  
                     if (a[j - 1] > a[j])  
                     {  
                            Swap(a[j - 1], a[j]);  
                            flag = true;  
                     }  
              k--;  
       }  
}

ログイン後にコピー

さらに最適化してみましょう。 100 個の数値の配列があり、最初の 10 個だけが順序付けされておらず、次の 90 個が並べ替えられており、すべてが最初の 10 個の数値より大きい場合、最初の走査の後、交換が行われる最後の位置は 10 未満でなければなりません。、この位置の後のデータは順序どおりである必要があります。2 回目は配列の先頭からこの位置まで移動するだけです。

//冒泡排序3  
void BubbleSort3(int a[], int n)  
{  
    int j, k;  
    int flag;  
      
    flag = n;  
    while (flag > 0)  
    {  
        k = flag;  
        flag = 0;  
        for (j = 1; j < k; j++)  
            if (a[j - 1] > a[j])  
            {  
                Swap(a[j - 1], a[j]);  
                flag = j;  
            }  
    }  
}

ログイン後にコピー

結局のところ、バブルソートは非効率なソート方法であり、データサイズが小さい場合に使用できます。データサイズが比較的大きい場合は、他の並べ替え方法を使用することをお勧めします。

バブルソートの 3 つの実装に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。