从本文开始，作者将和大家一起学习数据结构与算法，本文将从最简单的排序算法开始，目标是一周更新一篇。

想象一个气泡从水底上升到水面的过程，就是冒泡排序的过程。随着气泡的移动，气泡里的数据会发生变化，总是取它经过的较大的值，这样，当气泡升至水面时，里面的数据一定是最大的那个。

第一个版本

考虑一个包含n个数的数组，需要n-1次冒泡完成所有排序。

main.c

#include "bubble_sort.h"int main(){    int a[10] = {50, 3, 47, 23, 9, 18, 34, 2, 16, 10};    print_array(a, sizeof(a)/sizeof(int));    bubble_sort(a, sizeof(a)/sizeof(int));    print_array(a, sizeof(a)/sizeof(int));    return 0;}

bubble_sort.h

#include <stdio.h>void bubble_sort(int a[], int num);void print_array(int a[], int num);

bubble_sort.c

#include "bubble_sort.h"/*why count is needed?*//*Because array is passed as a pointer through value parameter*/void bubble_sort(int a[], int count){    for (int i = 0; i < count-1; i++)    {        for (int j = 0; j < count-1-i; j++)        {            if (a[j] > a[j+1])            {                int tmp = a[j];                a[j] = a[j+1];                a[j+1] = tmp;            }        }        printf("round %d: ",i +1);        print_array(a, count);    }}void print_array(int a[], int count){    for (int i = 0; i < count; i++)    {        printf("%d ",a[i]);    }    printf("\n");}

编译运行

gcc main.c bubble_sort.c -o bubble_sort.exe$ ./bubble_sort.exe50 3 47 23 9 18 34 2 16 10after round 1: 3 47 23 9 18 34 2 16 10 50after round 2: 3 23 9 18 34 2 16 10 47 50after round 3: 3 9 18 23 2 16 10 34 47 50after round 4: 3 9 18 2 16 10 23 34 47 50after round 5: 3 9 2 16 10 18 23 34 47 50after round 6: 3 2 9 10 16 18 23 34 47 50after round 7: 2 3 9 10 16 18 23 34 47 50after round 8: 2 3 9 10 16 18 23 34 47 50after round 9: 2 3 9 10 16 18 23 34 47 502 3 9 10 16 18 23 34 47 50

反思

从输出结果看第8，9轮冒泡其实并没有意义，因为数据已经按升序排好了。是否可以使用一个flag来指示排序已经完成？

第二个版本

bubble_sort.c

void bubble_sort_improve(int a[], int count){    bool swapped;    int i = 1;    int num = count;    do    {        swapped = false;        for (int j = 0; j < num-1; j++)        {            if (a[j] > a[j+1])            {                int tmp = a[j];                a[j] = a[j+1];                a[j+1] = tmp;                swapped = true;//if swap happens, next round is needed.            }        }        num--;        printf("after round %d: ",i++);        print_array(a, count);    } while (swapped == true);}

运行结果

$ ./bubble_sort.exe50 3 47 23 9 18 34 2 16 10improved after round 1: 3 47 23 9 18 34 2 16 10 50improved after round 2: 3 23 9 18 34 2 16 10 47 50improved after round 3: 3 9 18 23 2 16 10 34 47 50improved after round 4: 3 9 18 2 16 10 23 34 47 50improved after round 5: 3 9 2 16 10 18 23 34 47 50improved after round 6: 3 2 9 10 16 18 23 34 47 50improved after round 7: 2 3 9 10 16 18 23 34 47 50improved after round 8: 2 3 9 10 16 18 23 34 47 502 3 9 10 16 18 23 34 47 50

反思

通过优化，我们减少了一轮冒泡。冒泡示意如下：

冒泡排序示意

时间复杂度

第一个版本的复杂度

i=0时需要n-1次比较和（可能的）交换i=1时需要n-2次比较和（可能的）交换i=n-2时需要1次比较和（可能的）交换i=n-1时需要0次比较和（可能的）交换

平均复杂度 (n-1)+(n-2)+...+1+0=n*(n-1)/2=O(n^2)

第二个版本的复杂度

最优复杂度 O(n)

数据已排序，n-1次比较后退出

平均复杂度 O(n^2)

参考链接数据结构和算法动态可视化：