冒泡算法-C语言

什么是冒泡排序呢？冒泡排序的英语名是Bubble Sort，是一种最基础的交换排序。
大家一定都喝过汽水吧，汽水中常常有许多小小的气泡，往上飘，这是因为组成小气泡的二氧化碳比水要轻，所以小气泡才会一点一点的向上浮。而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以向小气泡一样，根据自身大小，一点一点向着数组的一侧移动。具体如何移动呢？我们来看一下例子， 有8个数组成一个无序数列：5,8,6,3,9,2,1,7，希望从大到小排序。按照冒泡排序的思想，我们要把相邻的元素两两进行比较，根据大小交换元素的位置，
利用双重for循环语句可以达到冒泡排序的方法 ，过程如下：
第一轮排序：

1、首先让5和8进行交换，发现5比8小，因此元素位置不变。

2、接下来让8和6比较，发现8比6大，所以要交换8和6的位置。

image.png

![8和6交换位子]

3、继续让8和3比较，发现8比3要大，所以8和3 交换位置。

4、继续让8和9进行比较，发现8比9小，不用交换

5、9和2进行比较，发现9比2大，进行交换

6、继续让9和1进行比较，发现9比1大，所以交换9和1的位置。

7、最后，让9和7交换位置，这样一来，元素9作为数列的最大元素，就已经排序好了。

下面我们来进行第二轮排序：

1、首先让5和6比较，发现5比6小，位置不变

2、接下来让6和3比较，发现6比3大，交换位置

3、接下来让6和8比较，6比8小，位置不变

4、8和2比较。8比2大，交换位置

5、接下来让8和1比较，8比1大，因此交换位置

6、继续让8和7比较，发现8比7大，交换位置

接着第三轮——>第八轮

到此为止，所有的元素都是有序的了，这就是冒泡排序的整体思路。

原始的冒泡排序是稳定的，由于该排序算法的每一轮都要遍历一遍所有的元素，轮转的次数和元素数量相当，所以时间复杂度为O(N^2)。
下面用C语言描述：

#include<stdio.h>
#include<stdlib.h>
 
void BubbleSort(int a[], int len)
{
    int i, j, temp;
    for (j = 0; j < len - 1; j++)
    {
        for (i = 0; i < len - 1 - j; i++)
        if (a[i] > a[i + 1])
        {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
        }
    }
}
 
int main()
{
    int arr[] = { 5, 8, 6, 3, 9, 2, 1, 7 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int i = 0;
    printf("排序前：");
    for (i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    BubbleSort(arr, len);
    printf("排序后：");
    for (i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    system("pause");
    return 0;
}

这个代码很简单，使用双循环的方式进行排序。外部的循环控制所有回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。那么这个代码该怎么进行优化呢？？我们现在来回顾一下之前的描述细节，仍然以 5,8,6,3,9,2,1,7 为例，当排序伏安法分别执行到第六、第七、第八轮的时候，数列的状态其实已经变为有序的了。