バブルソート

1. アルゴリズムの説明

バブルソート: 隣接するデータを順番に比較し、小さなデータを前に置き、大きなデータを後ろに置きます。つまり、最初のパスで 1 番目と 2 番目の数値を比較し、大きな数値を後ろに置きます。 、小数点を先頭にして 2 番目の数値を 3 番目の数値と比較し、大きな数値を最後に、小数点を前に置くというように、最大​​の数値が 2 番目のパスの最後の位置に「ロール」されます。次に大きい数値を「ロール」します。最後から 2 番目の位置までスクロールします。ソートは n-1 (n は順序付けされていないデータの数) 回で完了します。

次の 5 つの順序なしデータを例に挙げます:

40 8 15 18 12 (この記事では、最初のパスの比較プロセスのみが詳しく説明されています)

最初のパス: 8 15 18 12 40

2 番目のパストリップ: 8 15 12 18 40

3 回目のトリップ: 8 12 15 18 40

4 回目のトリップ: 8 12 15 18 40

2. アルゴリズム分析

平均時間計算量: O(n2)

space Complexity: O( 1) (交換用)

安定性: 安定しています

3. アルゴリズムの実装

//交换data1和data2所指向的整形  
void DataSwap(int* data1, int* data2)  
{  
    int temp = *data1;  
    *data1 = *data2;  
    *data2 = temp;  
}  
  
/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    バブルソート 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    for (int i = 0; i < iDataNum - 1; i++)   //走iDataNum-1趟  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
}

4. アルゴリズムの最適化

単純にバブルソートアルゴリズムを最適化し、比較プロセス中に交換があるかどうかを記録することもできます。交換がない場合は、配列全体が順番に並べ替えプロセスを終了しています。そうでない場合は、次の比較が続行されます。

/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    バブルソート 
*********************************************************/  
void BubbleSort(int* pDataArray, int iDataNum)  
{  
    BOOL flag = FALSE;    //记录是否存在交换  
    for (int i = 0; i < iDataNum - 1; i++)    //走iDataNum-1趟  
    {  
        flag = FALSE;  
        for (int j = 0; j < iDataNum - i - 1; j++)      
            if (pDataArray[j] > pDataArray[j + 1])  
            {  
                flag = TRUE;  
                DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
            }  
          
        if (!flag)    //上一趟比较中不存在交换，则退出排序  
            break;  
    }  
}

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