起泡排序算法（Bubble Sort）的原理和实现

原理：

起泡排序算法 (Bubble Sort) 的基本思想是将相邻位置的元素进行比较,如果它们的相对顺序是反的(逆序)，那么就交换这两个元素。假设要实现升序排序，那就依次比较相邻的两个元素，将大的元素放在小的元素后面，也就是每次交换都会让两个元素中的较大者向后移动。在对数组的一次遍历操作执行交换后，数组中最大的元素被交换到了数组的尾部。这个过程就像是一个气泡 (每次向后交换的元素) 从水底 (数组头部) 向上不断上浮，这个气泡只会不断地变大，直到水面 (数组尾部) 。

在第 1 趟遍历中，数组中最大的元素已经到达了数组最后的位置，也就是到达了它合适的位置了。那么在第 2 趟遍历中需要遍历的是数组前品 n - 1 个元素，会将这 n - 1 个元素的最大元素放到数组的倒数第二个位置。重复这个过程，每越遍历就能至少将 1 个元素换到它正确的位置上，那遍历 n 趟就一定能将整个数组排序好。

但是存在一种情况：如果在某趟遍历中没有元素进行位置的交换，那说明数组已经有序的，就可以不继续遍历下去，提前终止排序。

下面给出一个起泡排序的过程示例：

以下是起泡排序算法的实现代码：

#include <stdio.h>

int main() {
    int a[10];
    int n = 0, i, j, swap_flag, t;
    while (scanf("%d", &a[n])) {//输入任意个数字，遇到0时结束输入，记录个数n
        if (a[n] == 0) break;
        n++;
    }
    for (i = 0; i < n; i++) {
        swap_flag = 0; // 重新设置交换指示变量
        // 在内层循环中n-i为前面无序区域的元素个数
        // 而再减1是因为对于n个元素依次两两比较只需要比较n-1次
        for (j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {// 当前一个元素比后一个元素大时，是一个逆序，需要交换
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swap_flag = 1; // 发生了交换，设置指示变量
            }
        }
        if (swap_flag == 0) break; // 在某趟遍历中没有发生元素交换，直接结束排序过程
    }
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

由程序可以看出，起泡排序不如选择排序直观，但是起泡排序可以通过有无发生元素交换来知道数组是否已经为有序状态，这个特性可以在数据已经基本有序的情况下快速地完成排序操作。