冒泡排序

    冒泡排序：
    两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
具体实现请参考代码。

#include <stdio.h>

void bubbleSort(int *a, int n);
void bubbleSort2(int *a, int n);

int
main(int argc, char **argv)
{
    int a[10] = {1, 3, 5, 7, 9, 0, 2, 4, 6, 8};
    int n = sizeof(a) / sizeof(a[0]);

//    bubbleSort(a, n);
    bubbleSort2(a, n);

    int i;
    printf("Result: ");
    for (i = 0; i < 10; i++) {
        printf("%d,", a[i]);
    }
    printf("\n");

    return 0;
}

void
bubbleSort(int *a, int n)
{
    int i, j, tmp;

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

void
bubbleSort2(int *a, int n)
{
    int i, j, tmp;
    int flag;

    for (i = 0; i < n-1; i++) {
        flag = 0;
        for (j = n-1; j > i; j--) {
            if (a[j-1] > a[j]) {
                tmp = a[j-1];
                a[j-1] = a[j];
                a[j] = tmp;
                flag = 1;
            }
        }
        if (!flag) {
            return ;
        }
    }

}

注：平均时间复杂度为：O(n2)，就地、稳定。注意n的求法。