ソートアルゴリズムのまとめ:バブルソート

基本思想.
バブルソートは非常に容易に理解され、実装され、例えば配列長をNとする.1.隣接する前後の2つのデータを比較し、前のデータが後のデータより大きい場合、2つのデータを交換する.2.このように配列の0番目のデータをN-1番目のデータに1回遍歴すると、最大のデータは配列のN-1番目の位置に「沈」する.3.N=N-1で、Nが0でない場合は前の2つのステップを繰り返し、そうでない場合はソートが完了します.
これにより,以下のコードを容易に書き出すことができる.

void BubbleSort(int a[], int n)
{
    int i, j;
    for (i = 0; i < n - 1; i++)
    { //  n-1 
        for (j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j+1])
            { //  
                int tmp;
                tmp = a[j+1];
                a[j+1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

最適化
バブルソートを簡単に改良し,フラグビットflagを設定することができ,これが交換された場合true,そうでなければfalseとなる.交換が発生しなかった場合、ソートが完了したことを示す場合は、ループを終了して余分な比較を避けることができます.

void BubbleSort(int a[], int n)
{
    int i, pass, tmp;
    for (pass = 0; pass < n - 1; pass++)
    {//  n-1 
        int flag = 0;
        for (i = 0; i < n - 1 - pass; i++)
        {//         
            if (a[i] > a[i + 1])
            {//       
                tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                flag = 1;
            }
        }
        if (flag == 0) //      ，     
            break; //    
    }
}

さらに最適化
さらに最適化します.100個の数の配列があって、前の10個だけが無秩序で、後ろの90個はすでに順序が整い、前の10個より大きい場合、最初の遍歴後、最後に交換が発生した位置は必ず10未満であり、この位置の後のデータは必ず秩序が整っているので、この位置を記録して、2回目は配列の頭からこの位置まで遍歴すればよい.

void BubbleSort(int a[], int n)
{
    int m = n - 1;
    int LastChange;
    int j, tmp;
    while (m > 0)
    {
        //LastChange      ，        ， LastChange=0
        LastChange = 0;
        for (j = 0; j < m; j++)
        {
            if (a[j] > a[j + 1])
            {//        
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                LastChange = j; //         
            }
        }
        m = LastChange; //           
    }
}