冒泡 排序

一. 演算法描述

    冒泡 排序：依序比較鄰近的數據，將小數據放在前，大數據放在後；即第一趟先比較第1個和第2個數，大數在後，小數在前，再比較第2個數與第3個數，大數在後，小數在前，以此類推則將最大的數"滾動"到最後一個位置；第二趟則將次大的數字滾動到倒數第二個位置......第n-1(n為無序資料的個數)趟即能完成排序。

以下面5個無序的數據為例：

40 8 15 18 12 （文中僅細化了第一趟的比較過程）

第1趟: 8 15 18 12 40

第1趟: 8 15 18 12 40

第1趟2趟: 8 15 12 18 40

第3趟: 8 12 15 18 40

第4趟: 8 12 15 18 40

二. 行程分析

複雜度：O(1)  (用於交換)

穩定性：穩定

三.演算法實作

//交换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]);  
}

四. 演算法最佳化

還可以對冒泡 排序演算法進行簡單的最佳化，用一個標記來記錄演算法最佳化

還可以對冒泡 排序演算法進行簡單的最佳化，用一個標記來記錄在一趟的比較過程中是否存在交換，如果不存在交換則整個數組已經有序退出排序過程，反之則繼續進行下一趟的比較。

/******************************************************** 
*函数名称：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中文網！