冒泡排序算法（起泡排序）及其C代码实现

起泡排序，别名“冒泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。

例如，对无序表进行升序排序的具体实现过程如图 1 所示：

                           图 1 第一轮起泡

如图 1 所示是对无序表的第一轮起泡排序，最终将无序表中的最大值 97 找到并存储在表的最后一个位置。具体实现过程为：

首先 49 和 38 比较，由于 38

然后继续下标为 1 的同下标为 2 的进行比较，由于 49

直至（4），97 同 76 进行比较，76

同样 97>13（5）、97>27（6）、97>49（7），所以经过一轮冒泡排序，最终在无序表中找到一个最大值 97，第一次冒泡结束。

由于 97 已经判断为最大值，所以第二轮冒泡排序时就需要找出除 97 之外的无序表中的最大值，比较过程和第一轮完全相同。

经过第二轮冒泡，最终找到了除 97 之外的又一个最大值 76，比较过程完全一样，这里不再描述。

通过前两轮冒泡，我们可以得到结论：i个元素冒泡排序需要进行(i-1)轮冒泡，且每一轮冒泡排序数据比较次数要比之前的一轮少1。

通过一趟趟的比较，一个个的“最大值”被找到并移动到相应位置，直到检测到表中数据已经有序，排序结束，这就是起泡排序。

起泡排序的具体实现代码为：

运行结果为：

13 27 38 49 49 65 76 97

总结

使用起泡排序算法，其时间复杂度同实际表中数据的无序程度有关。若表中记录本身为正序存放，则整个排序过程只需进行 n-1（n 为表中记录的个数）次比较，且不需要移动记录；若表中记录为逆序存放（最坏的情况），则需要 n-1趟排序，进行 n(n-1)/2 次比较和数据的移动。所以该算法的时间复杂度为。