浅议冒泡排序及其优化方法
浅议冒泡排序及其优化方法冒泡排序法是一种简单的排序方法，不仅代码简短，排序思路也简单易懂，是一种容易被初学者接受的基本排序方法。但正因为冒泡排序代码简短，很多同学在学习该排序方法时只是很快记住了教科书中的例程，并没有吃透代码中两层循环的作用；而且一般教科书中给出的是最基本的编码，算法时间复杂度高，排序效率低。本文旨在分析冒泡排序法的基本思想，并分析如何对算法进行优化。
冒泡法模拟水中气泡网上冒的物理过程，对一个待排序序列，通过比较相邻的两个元素，依次将较大的元素往上顶，或将较小的数往下沉（本文主要分析前一种方法，有兴趣的读者可以自己分析第二种方法，相关代码在附录中）。每趟冒泡下来，可以确保当前最大值处在序列的顶端。对一个有n个元素的序列，需要冒泡(n-1)趟，才能完成排序。排序过程中，每冒泡一趟，待排序列的长度就减1，直到待排序列的长度为1，排序完成。
一， 基础冒泡排序代码
void BubbleSort_1(int lib[], int n) //冒泡法基础程序：将较大数向上移动
{
int high; //待排序部分数组的上边界，即lib[0..high]为待排序部分，lib[high+1..n-1]为已排序部分
int temp; //用来交换数组元素值的临时变量
int i;
for (high=n-1; high>0; high--) //外层循环控制待排序部分数组的上边界，每完成一趟冒泡，上边界下移一个位置
{
for (i=0; i<high; i++)//内层循环扫描待排序部分数组，比较相邻元素，并通过交换元素值的方式将最大值顶到最上方
{
if (lib[i] > lib[i+1])
{
temp = lib[i];
lib[i] = lib[i+1];
lib[i+1] = temp;
}
}
}
}
二， 冒泡排序第一步优化
在基础冒泡法中，外层循环控制待排序部分数组的上边界，每完成一趟冒泡，上边界下移一个位置，使得待排序列的长度减1，直到待排序列的长度为1，排序完成。内层循环扫描待排序部分数组，比较相邻元素，并通过交换元素值的方式将最大值顶到最上方。
对一个有n个元素的序列，基础冒泡法比较次数为 ，这是最坏的时间复杂度。
实际上，如果待排序列本身是增序的，冒泡过程中根本不需要交换元素，一趟扫描即可完成排序，时间复杂度应该为 ，这是最好的时间复杂度。我们可以增加一个交换标志，判断在内层循环中是否进行了交换操作，若未进行交换操作，说明排序已经完成。这样可以减少不必要的重复扫描。改进版代码如下：
void BubbleSort_2(int lib[], int n) //改进版1：设置交换标志，以便提前结束扫描
{
int high; //待排序部分数组的上边界，即lib[0..high]为待排序部分，lib[high+1..n-1]为已排序部分
int temp; //用来交换数组元素值的临时变量
int SwapFlag; //交换标志
int i;
for (high=n-1; high>0; high--) //外层循环控制待排序部分数组的上边界，每完成一趟冒泡，上边界下移一个位置
{
SwapFlag = 0; //设置交换标志
for (i=0; i<high; i++)
{
if (lib[i] > lib[i+1])
{
temp = lib[i];
lib[i] = lib[i+1];
lib[i+1] = temp;
SwapFlag = 1; //该处发生了交换操作
}
}
if (SwapFlag == 0) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
break;
}
}
三， 冒泡排序第二步优化
我们通过一个实例来分析“/改进版1”中排序的过程。
待排序数组：lib[8] = {3,2,1,4,5,6,7,8}。high=7。
第一趟冒泡后：lib[8] = {2,1,3,4,5, 6,7,8}。high=6。最后一次交换的元素是lib[1] 和lib[2]。
第二趟冒泡后：lib[8] = {1,2,3,4,5, 6,7,8}。high=5。最后一次交换的元素是lib[0] 和lib[1]。
第三趟冒泡后：lib[8] = {1,2,3,4,5, 6,7,8}。没有交换元素，排序完成。
仔细观察冒泡的过程，我们发现在第一趟冒泡过程中，lib[3..7]序列中的元素未发生交换，即这段序列的元素已经是有序的了，在第二趟冒泡时，程序扫描的待排序列为lib[0..6]，而实际上我们只需扫描序列lib[0..2]即可。也就是说，若靠近已排序部分的数组成员未做交换操作，则说明该部分的成员也是有序的，则可将待排序列的上界缩小到最后一次发生交换的成员处，这样可以缩小内层循环的扫描范围。改进版代码如下：
void BubbleSort_3(int lib[], int n) //改进版2：将较大数向上移动
{
int high; //待排序部分数组的上边界，即lib[0..high]为待排序部分，lib[high+1..n-1]为已排序部分
int temp; //用来交换数组元素值的临时变量
int lastSwapPos = n - 1;//初始化最后一次发生交换操作的位置为（n - 1)
int i;
while (lastSwapPos > 0)
{
high = lastSwapPos; //待排序部分数组的上边界即上一趟冒泡过程中，最后一次发生交换操作的位置
for (i=0; i<high; i++)//内层循环扫描待排序部分数组，lib[0..high]为待排序部分
{
if (lib[i] > lib[i+1])
{
temp = lib[i];
lib[i] = lib[i+1];
lib[i+1] = temp;
lastSwapPos = i; //记录发生了交换操作的位置
}
}
if (high == lastSwapPos) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
break;
}
}
四， 冒泡排序第三步优化
在第二步优化中，我们采用了将较大的元素往上顶的冒泡方法，通过记录发生交换操作的位置，将最后一次发生交换操作的位置作为待排序列的上边界，缩小了下一趟扫描的范围，提高了排序效率。
在实际编码时，我们还可以采用将较小的数往下沉的方法实现冒泡排序。如果能够双向逼近，同时从两端缩小待排序列的范围，就可以最大限度的减少扫描次数。
改进版代码如下：
void BubbleSort_4(int lib[], int n)//改进版3：双向冒泡
{
int low, high; //待排序部分数组的边界，即lib[low..high]为待排序部分，lib[0..low-1]和lib[high+1..n-1]为已排序部分
int lastSwapPos;//最后一次发生交换操作的位置
int temp; //用来交换数组元素值的临时变量
int i;
low = 0;
high = n - 1;
while (low < high)
{
lastSwapPos = high; //设置需要排序的成员范围（大于此下标的成员已经排好序）
for (i=low; i<lastSwapPos; i++)
{
count++;
if (lib[i] > lib[i+1])
{
temp = lib[i];
lib[i] = lib[i+1];
lib[i+1] = temp;
high = i;//该处发生了交换操作，更新需要排序的成员范围
}
}
if (lastSwapPos == high) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
break;
lastSwapPos = low; //设置需要排序的成员范围（小于此下标的成员已经排好序）
for (i=high; i>lastSwapPos; i--)
{
count++;
if (lib[i] < lib[i-1])
{
temp = lib[i];
lib[i] = lib[i-1];
lib[i-1] = temp;
low = i;//该处发生了交换操作，更新需要排序的成员范围
}
}
if (lastSwapPos == low) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
break;
}
}
附录：
void BubbleSort_5(int lib[], int n) //冒泡法基础程序：将较小数向下移动
{
int low; //待排序部分数组的下边界，即lib[low..n-1]为待排序部分，lib[0..low-1]为已排序部分
int temp; //用来交换数组元素值的临时变量
int i;
for (low=1; low<n; low++) //外层循环控制待排序部分数组的下边界，每完成一趟冒泡，下边界上移一个位置
{
for (i=n-1; i>=low; i--)//内层循环扫描待排序部分数组，比较相邻元素，并通过交换元素值的方式将最小值顶到最下方
{
if (lib[i] < lib[i-1])
{
temp = lib[i];
lib[i] = lib[i-1];
lib[i-1] = temp;
}
}
}
}
void BubbleSort_6(int lib[], int n) //改进版2：将较小数向下移动
{
int low; //待排序部分数组的下边界，即lib[low..n-1]为待排序部分，lib[0..low-1]为已排序部分
int temp; //用来交换数组元素值的临时变量
int lastSwapPos = 0;//初始化最后一次发生交换操作的位置为0
int i;
while (lastSwapPos < n)
{
low = lastSwapPos; //待排序部分数组的下边界即上一趟冒泡过程中，最后一次发生交换操作的位置
for (i=n-1; i>low; i--)//内层循环扫描待排序部分数组，lib[low..n-1]为待排序部分
{
if (lib[i] < lib[i-1])
{
temp = lib[i];
lib[i] = lib[i-1];
lib[i-1] = temp;
lastSwapPos = i; //记录发生了交换操作的位置
}
}
if (low == lastSwapPos) //若未进行交换操作，说明排序已经完成，提前结束扫描工作
break;
}
}
