冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字的位置”这一操作的算法。在这个过程中,数字会像泡泡一样,慢慢从右往左“浮”到序列的顶端(每趟比较找出该趟最大的数),所以这个算法才被称为“冒泡排序”。

Example:

排序前:3 1 4 5 2
第1趟:1 3 4 2 5
第2趟:1 3 2 4 5
第3趟:1 2 3 4 5
第4趟:1 2 3 4 5

每一趟要比较n – i – 1次,一共要比较n – 1趟,总的比较次数为 (n -1) +(n -2) +…+1 ≈ n^2/2。冒泡排序的时间复杂度为O(n^2),是一种稳定排序算法。

通过c语言代码实现:

void bubble(int num[], int n)
{
    int temp;
    for (int i = 0; i < n - 1; i++) //开始冒泡排序
        //遍历数组找出最大
        for (int j = 0; j < n - i - 1; j++)
            if (num[j] > num[j + 1]) //两两比较
            {
                //两两交换
                temp = num[j];
                num[j] = num[j + 1];
                num[j + 1] = temp;
            }
}
参考书籍:1.《算法图解》作者:[美] Aditya Bhargava;译者:袁国忠;ISBN:978-7-115-44763-0
2.《我的第一本算法书》 作者:(日)石田保辉,(日)宫崎修;译者:张贝;ISBN:978-7-115-49524-2