学步园

算法描述：
存在序列array[0. . n-1], 在第 i 趟排序时(i = 1, 2, 3, . . . n-1), 先将第1个元素和第2个元素比较大小，如果 array[0] > array[1]， 则交换 array[0] 和array[1]，否则不交换，然后再将array[1]和array[2]比较大小，如果array[1] > array[2]，则交换array[1]和array[2], 否则不交换，如此重复比较和交换动作，直到最后一次比较array[n-i-1] 和 array[n-i]，这样每一趟排序结束后都会有前面的未排序序列中最大的元素排在下标为
n-i 的array序列中，直到某一趟排序过程中不出现元素的交换动作，排序结束。
由于需要检测在每一趟排序过程中是否有交换动作，我们需要设置一个标志位flag
flag = 0：表示某一趟排序过程中没有交换动作
flag = 1：表示某一趟排序过程中有交换动作
每一趟排序之前，先将flag置为0，如果在排序过程中只要出现元素交换的动作，就及时置flag为1，如果在某一趟排序过程中只有比较而没有交换动作，说明序列已经按有序排列。插入排序和选择排序都需要执行n-1趟排序，而冒泡排序最多执行n-1趟排序。
best case：初始序列已经按升序，则只需要进行一趟n-1次元素之间的比较，并且不移动元素，算法时间复杂度为O(n);
worst case: 初始序列逆序排列，或者最小元素在序列的最后，需要进行n-1趟排序，总共进行 1 + 2 + 3 + 4 + . . . + n-1 = n(n-1) /2, 时间复杂度为O(n^2);

冒泡排序是稳定性排序方法。

冒泡排序比较适合参加排序序列的数据量较小的情况，尤其是当序列的初始状态为基本有序的情况，而对于一般的情况，这种方法是排序时间效率最低的一种。

看代码：

#include <stdlib.h>
#include <stdio.h>

void bubbleSort(int array[], int n)
{
    int i, j, temp;
    int flag = 1;
            
    i = n - 1;
    while( i > 0 && flag == 1 )
    {
        flag = 0;    //每一趟排序之前先置标志flag = 0
        for( j = 0 ; j < i ; ++j )
        {
            if( array[j] > array[j+1] )
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;

                flag = 1;  //有交换动作，置flag = 1
            }
        }
        --i;
    }
}

int main()
{
    int array[] = {5, 3, 54, 31, 11, 78, 1};
    int size = sizeof(array) / sizeof(int);
    bubbleSort(array, size);
    for(int i = 0; i < size; ++i)
        printf("%d ", array[i]);
    printf("\n");

    return 0;
}