一种冒泡排序的改进算法
2014-07-28廖志文
廖志文
摘要：传统的冒泡排序几乎都是基于基本数据类型，通过比较相邻的两个元素的大小，如果发生逆序，则交换两个元素的值。当待排序元素是构造类型时，通过交换两个元素的值，时间复杂度必然会增加；另一方面，基本数据类型变量与构造类型变量的赋值方式有很大的区别，因此传统的冒泡排序算法复用性低。针对传统冒泡排序的不足，该文提出了一种冒泡排序的改进算法。改进后的冒泡排序对于元素是结构体等构造类型时时间复杂度明显降低，且函数复用性提高。
关键词：冒泡排序；改进算法；时间复杂度；函数复用性
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）18-4258-04
An Improved Algorithm of Bubble Sort
LIAO Zhi-wen
（Computer Science and Technology Department， Zhuhai College of Jilin University， Zhuhai 519041，China）
Abstract： The traditional bubble sort is almost based on basic data types. By comparing the size of two adjacent elements， if the reverse occurs， the values of the two elements are exchanged. When the elements to be sorted are of constructed type， through the exchange value of the two elements， the time complexity surely bounds to increase； On the other hand， because the assigned way of basic data type is different from that of constructed types， therefore， it will lower reusability of the traditional bubble sort algorithm. For the Shortcoming of the traditional bubble sort， this paper presents an improved bubble sort algorithm. The improved bubble sort algorithm significantly reduces the time complexity and improved reusability when the elements are of constructed data types.
Key words： bubble sort；improved algorithm；time complexity；function reusability
一个算法的复杂性的高低体现在运行该算法所需要的时间和空间资源。设计出复杂性尽可能低的算法是在设计算法时追求的一个重要目标[1]。算法是解决问题的一种方法或一个过程。在C语言中，算法都是通过函数实现的。函数是C语言源程序的基本构成模块，是一段可以重复调用的、功能相对独立完整的程序段[2]。函数的复用性是判断一个函数设计优良的重要特征。
冒泡排序（Bubble Sort），是一种计算机科学领域的常用的较简单的排序算法。如何设计出复杂度尽可能低且函数复用性高的算法是算法效率和通用性的关键内容。
1 传统的冒泡排序
1.1 排序思想
假设数组有n个数组元素，将这n个元素按升序进行排序。从下标为0的元素开始，比较相邻的两个元素的大小，如果前面的元素大于后面的元素，在交换这两个元素的值。
第一趟，从下标为0的元素到下标为n-1的元素，依次比较相邻的元素大小，如果前面元素比后面元素大，则交换元素值。一趟下来，最大的元素“沉底”。
第二趟，从下标为0的元素到下标为n-2的元素，依次比较相邻的元素大小，如果前面元素比后面元素大，则交换元素值。一趟下来，第二大的元素“沉底”。
依此类推，有n个元素，每趟排序将当前待排序元素（除了已经“沉底”的元素）最大值“沉底”，则需要n-1趟排序。
1.2 算法实现
void bubble_sort（int b[]，int n）
{int i，j，t；
for （i = 1； i < 8； i++）
{for （j = 0； j < 8 - i； j++）
{if （b[j] > b[j+1]）
{t=b[j]；
b[j]=b[j+1]；
b[j+1]=t；
}}//for
}//for
}
1.3 时间复杂度
若待排序数组的元素初始状态是正序的，一趟扫描即可完成排序。所需的关键词比较次数C和记录移动次数M均达到最小值：Cmin=n1， Mmin=0。因此，冒泡排序最好情况下的时间复杂度为O（n）。
若待排序数组的元素初始状态是正序的，需要n-1趟排序。每趟需要进n-i次关键词的比较（i为已“沉底”的元素个数），若发生逆序，必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Cmax=n（n-1）/2 ，Mmax=3n（n-1）/2=O（n2）。冒泡排序的最坏时间复杂度为O（n2）。综上，因此冒泡排序总的平均时间复杂度为O（n2） 。endprint
2 冒泡排序存在的问题
2.1 问题提出
制作一份按学生成绩排名次的表格。假如待排序的学生人数为30个，每个学生包括学号，姓名，性别，年龄，所属班级及成绩信息。现在要求将10个学生记录按成绩的降序排序。
用传统的冒泡排序算法实现按成绩降序排序的思想是，定义一个学生的结构体数据类型，定义一个学生结构体类型的数组，用来存放学生信息。比较相邻的两个学生的成绩，如果前一个学生的成绩小于后面的成绩，则交换两个学生记录。2.2 算法实现
#define NUM XXX // NUM表示学生人数
typedef struct
{char sno[8]；
char sname[20]；
char sex[3]；
unsigned int age；
unsigned int classno；
float grade；
}STU；
void bubble_sort（STU b[]，int c[]）
{int i，j，t；
STU temp；
for （i = 1； i < NUM； i++）
{flag=0；
for （j = 0； j < NUM - i； j++）
{if （b[j].grade > b[j+1].grade）
{//以下是结构体内部变量交换值
strcpy（temp.sno，b[j].sno）；
strcpy（b[j].sno，b[j+1].sno）；
strcpy（b[j+1].sno，temp.sno）；
strcpy（temp.sname，b[j].sname）；
strcpy（b[j].sname，b[j+1].sname）；
strcpy（b[j+1].sname，temp.sname）；
strcpy（temp.sex，b[j].sex）；
strcpy（b[j].sex，b[j+1].sex）；
strcpy（b[j+1].sex，temp.sex）；
temp.age=b[j].age；
b[j].age=b[j+1].age；
b[j+1].age=temp.age；
temp.classno=b[j].classno；
b[j].classno=b[j+1].classno；
b[j+1].classno=temp.classno；
temp.grade=b[j].grade；
b[j].grade=b[j+1].grade；
b[j+1].grade=temp.grade；
flag=1；
}}//for
}//for
}
2.3 时间复杂度增加
若待排序数组的元素初始状态是正序，则构造数据类型的数组元素比较次数和交换次数和基本数据类型相同。即，Cmin=n-1， Mmin=0。
若待排序数组元素初始状态时逆序，则构造数据类型的数组元素比较次数和基本数据类型相同，但交换次数和基本数据类型不同。
比如上述的实例，按成绩的降序对学生记录重新排序。由于学生的信息是结构体类型的，结构体可以有多种不同数据类型的变量组合定义。在相邻的两个学生成绩发生逆序时，交换的不仅仅是成绩，而是整个学生记录。学生记录结构体定义了学号，姓名，性别，年龄，所在班级和成绩6个不同类型的内部变量。则在学生记录发生交换时，同时要交换这6个变量的值。交换一对变量的值用三个赋值语句，因此，交换两个学生记录的顺序要发生18个赋值运算。而且不同的数据类型赋值方式是不同的，比如对于字符数组型变量，它的赋值语句用strcpy函数实现交换，它的交换效率比数值交换要低，即时间复杂度增加。
通常地，设结构体由r个内部变量组合定义而成，则对于初始状态是逆序的数组元素，需要交换的次数Mmax=3rn（n-1）/2。构造数据类型的交换次数至少是基本数据类型的r倍。
2.4 算法复用性低
由于传统的冒泡排序发生逆序时，交换的是两个元素的值。数值数据交换值，直接用赋值语句；字符串元素交换值，调用库函数strcpy；如果是结构体等构造数据类型，则交换每个结构体内部变量。因此，在算法实现交换功能时不同的数据类型元素实现方法不一致。这显示了冒泡排序算法的函数复用程度低。
3 一种改进的冒泡排序算法
3.1 冒泡排序算法的改进思想
基于传统的冒泡排序，针对不同的数据类型，会出现时间复杂度增加、算法复用性低的不足，提出了一种冒泡排序的改进算法。
传统冒泡排序之所以出现复杂度增加、算法复用性低的特点，是因为相邻的两个数组元素而发生逆序时，交换的是两个元素的值，而不同的数据类型的数组交换值的方法不同。
因此，改进的冒泡排序当相邻的两个元素发生逆序时，不是交换两个元素的值，而是交换这两个元素在当前数组中的下标。其实，只需要记录每个元素在当前数组中的下标，即根据元素大小确定其在数组中的位置。改进的算法增加了一个和待排序数组长度一样的辅助数组，，初始值为待排序各元素在数组中的下标。当相邻的两个元素发生逆序时，交换元素的下标。最终，根据每个元素在数组中的下标，打印排序后的元素序列。由于交换的是下标，因此，不同的数据类型的元素交换方式不会发生改变，算法的复用性高。而且，交换下标只需要常数级时间，时间复杂度不会因为数据类型的复杂而增加。endprint
3.2 改进的冒泡排序算法的实现
typedef struct
{char sno[8]；
char sname[20]；
char sex[3]；
unsigned int age；
unsigned int classno；
float grade；
}STU；
//c[]保存每个数组元素在正序序列中的下标
void bubble_sort（STU b[]，int c[]）
{int flag；
int i，j，t；
for （i = 1； i < NUM； i++）
{flag=0；
for （j = 0； j < NUM - i； j++）
{if （b[c[j]].grade > b[c[j+1]].grade）
{//交换下标的方式对于
//不同的数据类型是完全可复用的
t=c[j]；
c[j]=c[j+1]；
c[j+1]=t；
flag=1；
}}//for
if （flag==0）
{break；
}}//for
}
3.3 测试程序
void main（）
{// NUM为学生人数符号常量
STU students[NUM]；
// index为数据a中元素依次在数组中的下标
int index[NUM]；
int i；
for （i=0；i {index[i]=i； } for （i=0；i {printf（"please input the %4d student information"，i）； printf（"＼nsno："）； scanf（"%s"，students[i].sno）； printf（"＼nsname："）； scanf（"%s"，students[i].sname）； fflush（stdin）； printf（"＼nsex："）； scanf（"%s"，students[i].sex）； printf（"＼nage："）； scanf（"%d"，&（students[i].age））； printf（"＼nclassno："）； scanf（"%d"，&（students[i].classno））； printf（"＼ngrade："）； scanf（"%f"，&（students[i].grade））； } bubble_sort（students，index）； printf（"the sorted students order by grade：＼n"）； printf（"sno， sname， sex， age， classno， grade＼n"）； for （i=0；i { // 根据元素在正序序列中的下标打印出排序后的序列。 printf（"%s， "，students[index[i]].sno）； printf（"%s， "，students[index[i]].sname）； printf（"%s， "，students[index[i]].sex）； printf（"%d， "，students[index[i]].age）； printf（"%d， "，students[index[i]].classno）； printf（"%4.1f＼n"，students[index[i]].grade）； }} 4 结束语 本文提出的冒泡排序的改进算法是对传统的冒泡排序在算法通用性即基本数据类型向构造类型上的扩展，然后发现传统冒泡排序在时间复杂度上会随着待排序元素的数据类型不同而增加、算法的函数复用性低的不足。通过增加一个辅助数组，初始值为待排序各元素在数组中的下标。当相邻的两个元素发生逆序时，交换元素的下标。排序完成后，辅助数组中各元素值即初始数组在有序序列中的位置。这种通过增加空间资源有效地提高了时间复杂度和算法的复用性。 参考文献： [1] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2001. [2] 王敬华，林萍，张清国.C语言程序设计教程[M].北京：清华大学出版社，2009.
