C语言 排序算法 冒泡排序 笔记

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

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