1.概念:
将待排序的数据看作是竖着排列的“气泡”,关键字较小的记录比较轻,从而要往上浮。对这个“气泡”序列进行n-1趟处理。所谓一趟处理,就是自上而下检查一遍这个序列,依次比较相邻两个记录的关键字,如果发生逆序,即 “轻”的记录在下面,就交换它们的位置。
第一趟排序之后,关键字最大的记录就被交换到最后一个位置;
第二趟排序之后,关键字次大的记录就被交换到最后第二个位置;
…
关键字小的记录不断上浮(起泡),关键字大的记录不断下沉。
在作第二趟排序时,由于最后一个位置上的记录已是最大的,所以不必检查;
因此第i趟起泡排序一般是从1到n-i+1。
2.算法性能:
3.C++程序示例:
1 | #include<iostream> |
运行结果: