Bubble Sort

1. Algorithm description

Bubble sorting: Compare adjacent data in turn, put small data in front and big data in the back; that is, compare the 1st and 2nd numbers in the first pass, and put the big numbers in the back , with the decimal first, then compare the second number with the third number, with the larger number at the end and the decimal first, and so on, the largest number will be "rolled" to the last position; in the second pass, the next largest number will be "rolled" Scroll to the second to last position... The sorting can be completed in the n-1 (n is the number of unordered data) times.

Take the following 5 unordered data as an example:

40 8 15 18 12 (The article only details the comparison process of the first pass)

First pass: 8 15 18 12 40

No. 2nd trip: 8 15 12 18 40

3rd trip: 8 12 15 18 40

4th trip: 8 12 15 18 40

2. Algorithm analysis

average time complexity: O(n2)

space Complexity: O(1) (for exchange)

Stability: Stable

3. Algorithm implementation

//交换data1和data2所指向的整形  
void DataSwap(int* data1, int* data2)  
{  
    int temp = *data1;  
    *data1 = *data2;  
    *data2 = temp;  
}  
  
/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    Bubble Sort 
*********************************************************/  
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. Algorithm optimization

You can also simply optimize the bubble sort algorithm and record it with a mark Whether there is exchange during a comparison process, if there is no exchange, the entire array has exited the sorting process in order, otherwise, the next comparison will continue.

/******************************************************** 
*函数名称：BubbleSort 
*参数说明：pDataArray 无序数组； 
*          iDataNum为无序数据个数 
*说明：    Bubble Sort 
*********************************************************/  
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;  
    }  
}

For more bubble sort related articles, please pay attention to the PHP Chinese website!