在教学中对冒泡排序算法的改进

施祖平

(南通纺织职业技术学院，江苏 南通226007)

1 引言

在数据结构教学过程中，排序是一个很重要的教学内容.排序作为数据处理中的一种重要运算，其本质是将一组数据元素的无序序列按一定的规律进行重新排列，最终成为有序序列.在计算机处理排序时，花费的时间较多，通过改进排序算法来提高系统的工作效率是非常有效的.排序的方法有很多，本文就冒泡排序法的算法提出一个改进的探讨.

2 普通冒泡法

冒泡法排序：通过比较在待排数组中相邻元素的值来进行，如果这些元素的第一个值比第二个值大就交换两个值，然后比较下一组相邻元素的值，在包括N个数据项的待排序的数据中，这个比较过程从下标1和下标2开始直到下标N-1和N元素为止，这就是一趟比较，其结果使最大的数据被安置到最后一个记录的位置上.一趟结束后，重新进行第二趟对N-1个数据进行同样的操作，其结果使次大的数据被安置到第N-1位置上.一般地讲，第i趟冒泡排序是从a[1]到a[n-i]依次将其与其后相邻的数据进行比较，并在“逆序”时交换相邻元素，结果使这n-i+1个数据中的最大元素被交换到第n-i+1的位置上，如此进行m(1≤m≤n-1)趟比较，直到在某一趟比较中没有任何一队数组元素发生交换为止，在每一趟的比较交换过程中，总是使较大的元素向下沉，而较小的元素向上浮，这就好比水中的“气泡”沉浮一样，因此称为冒泡排序法.

3 两头冒泡法

改进原因：在普通冒泡法中有一种不对称性无法解决，也就是说，如果最大的元素在首位置而其余的元素都已排好序，那么只进行一趟冒泡就可以完成排序.例如，{19，10，11，12，13，14，15，16，17，18}就仅需一趟冒泡.而当最小的元素位于末尾位置且其余元素都排好序时，则需要n-1趟冒泡才能完成排序.例如，待排序序列{11，12，13，14，15，16，17，18，19，10}就需要九趟冒泡.造成这种不对称的原因是，每趟冒泡过程都能使较大的元素下沉最大距离到它应到的最终位置，而较小的元素却只能向上浮一个位置.如果我们改变冒泡过程的扫描方向，每趟从尾部向前扫描，那么情况正好相反.例如，待排序序列{19，10，11，12，13，14，15，16，17，18}就需要扫描九趟，而序列{11，12，13，14，15，16，17，18，19，10}就只需要扫描一趟.为改变上述两种情况的不对称性，我们可以改变扫描方向来实现.

改进方法：在排序过程中交替改变扫描方向，实行双向排序，从而减少比较的次数.通过减少关键字的比较次数，提高排序算法的执行效率，达到优化目的.也就是说，分别从两头交替扫描进行冒泡排序，所以可以称这种改进的冒泡排序法为“两头冒泡法”.采用这种改进的方法进行排序时，以上两个待排序序列最多就只需要扫描两次就能完成排序了.

改进程序：

/*两头冒泡法程序*/

#include

#define N 10

main()

{int i，j，t，f，m，a[N+1];

printf(“Enter data:/n”); /*输入待排序数据*/

for (i=0;i

{printf(“a[%d]=”，i);

scanf(“%d”，&a[i]);

}

printf(“ The original numbers: ”); /*输出排序前原始数据*/

for(i=1;i

printf(“%5d”，a[i]);

printf(“ ”);

m=0; /*m用来统计冒泡的趟数和计算下一冒泡位置*/

f=1;

i=1;

while (f) /*改进处：进行两头冒泡排序*/

{ f=0;

m++;

for (j=i;j

if(a[j]>a[j+1])

{t=a[j];

a[j]=a[j+1];

a[j+1]=t;

f=1;

}

for (j=N-1;j>=i+1;j--) /*逆向冒泡排序*/

if (a[j]

{t=a[j];

a[j]=a[j-1];

a[j-1]=t;

f=1;

}

i++;

}

printf (“The scaning is made %d times ”，m); /*输出冒泡的趟数*/

printf (“ The sorted numbers: ”);

for (i=1;i

printf (“%5d”，a[i]);

}

4 结束语

冒泡排序法作为一种简单而又实用的排序方法，受到大家的普遍喜欢和广泛应用，通过算法的改进，能进一步提高排序的效率.学生在学习过程中，对这种改进的方法很感兴趣，很多学生通过阅读大量的程序，对其它的排序算法也进行改进的尝试，学习主动性增强了.当然，冒泡法作为一种常用的排序算法，同样值得我们进一步的研究和学习，以便在实际应用过程中进一步改进和完善.

参考文献：

[1]陈明.数据结构实用教程[M].北京：清华大学出版社，2007.

[2]徐士良.计算机常用.[M].北京：清华大学出版社，1995.

[3]Anany Levitin. 算法设计与分析基础(影印版) [M]. 北京: 清华大学出版社，2003.