链式存储结构上冒泡排序算法的研究与实现

胡新海

(陇南师范高等专科学校计算机系，甘肃成县742500)

链式存储结构上冒泡排序算法的研究与实现

胡新海

(陇南师范高等专科学校计算机系，甘肃成县742500)

线性表上进行的冒泡排序法是一种较简单的内部排序算法，计算机工作者经常研究和讨论顺序表中冒泡排序算法的实现及其改进，很少研究冒泡排序法在链表上的实现.文中讨论了冒泡排序在单链表上和静态链表上的算法及实现过程.最后分析了算法时间复杂度和空间复杂度.

冒泡排序;存储结构;单链表;静态链表;算法分析

冒泡排序是一种较简单的交换类排序算法.在相关文献中讨论了其在顺序表上的实现过程［1－4］.它通过对相邻元素的交换，逐步将待排序列变成有序序列.其算法的主要思想是:反复扫描待排序记录序列，在扫描过程中顺次比较相邻的两个元素的大小，若逆序就交换位置.

在排序的研究上近几年来也有一些新的方法，在排序时与链表结构结合，得出一些新的排序思路［5］.在顺序表上冒泡排序的实现较简单，在链表上的排序思想基本和顺序表上的相似.本文讨论了冒泡排序在单链表上和静态链表上的算法及实现过程.最后分析了算法时间复杂度和空间复杂度.与顺序表上实现的不同之处是需要标记链尾结点的地址.

1 冒泡排序算法在单链表上的实现

对于链表每一个结点看成竖着排列的“气泡”，然后分别从头结点向尾节点扫描.在扫描的过程中时刻注意两个相邻元素的顺序，保证前一结点元素的数据域小于后一节点元素的数据，这样经过一趟扫描后就使较大的元素沉到链尾，然后记住链尾结点的位置.下次又从头结点向后扫描，由于在前一趟扫描过程中最大的元素已经沉到链尾并记住了该元素的地址，所以这次扫描最大的元素不再参加排序，将剩下的元素进行排序，排序的过程中保证使得后一结点元素的数据域大于前一结点元素的数据域.这样反复的扫描，并不断缩小排序空间，直到整个序列有序位置为止.这样看来，在排序中，只需记住最后排好序的元素的位置即可.定义的链式结构和具体算法设计如下:

2 冒泡排序算法也能在静态链表上的实现

在静态单链表中，也可以进行冒泡排序操作，对于静态链表每一个结点同样看成竖着排列的“气泡”，然后分别从静态链表的头结点开始向尾节点扫描.在扫描的过程中时刻注意两个相邻元素的顺序，保证前一结点元素的数据域小于后一节点元素的数据，这样经过一趟扫描后就使较大的元素沉到链尾，然后记住链尾结点的位置.下次又从头结点向后扫描，由于在前一趟扫描过程中最大的元素已经沉到链尾并记住了该元素的地址，所以这次扫描最大的元素不再参加排序，将剩下的元素进行排序，排序的过程中保证使得后一结点元素的数据域大于前一结点元素的数据域.这样反复的扫描，并不断缩小排序空间，直到整个序列有序位置为止.这样看来，在排序中，只需记住最后排好序的元素的位置即可.对于静态链表进行定义和具体算法设计如下:

3 总结

在线性表上的冒泡排序，最好情况下的时间复杂度是O(n)，最差和平均情况下的时间复杂度是O(n2)，辅助空间为O(1)，算法比较稳定.在单链表和静态链表上的冒泡排序的时间复杂度、稳定性与在顺序表上完全相同.所以从实现过程和算法的分析，可以很明显的发现两种算法的设计思想和实现过程相似.只是在单链表上和静态链表上需记住最后排好序的元素的位置(即尾指针).链式结构上每个数据元素占用一个结点，而不会有多余的结点存在，所以数据元素所占存储空间不会浪费.

［1］严蔚敏，吴伟民.数据结构［M］.北京:清华大学出版社，1997.

［2］耿国华.数据结构(C语言版)［M］.西安:西安电子科技大学出版社，2002.

［3］Robert L.Kruse，Alexander J.Ryba.Data Structures and Program Design in C++［M］.USA:Pearson Education，2001.

［4］傅清祥，王晓东.算法与数据结构［M］.北京:电子工业出版社，1998.

［5］任志国，等.插入排序算法的双链表模拟［J］.电脑编程与维护，2010(6).

Research and Realization of Bubble Sort Algorithm on Link Storage Structure

HU Xin－hai
(Department of Computer Science，Longnan Teachers College，Chengxian，Gansu 742500，China)

Bubble sort which proceed on linear list is a kind of inner sort algorithms.Computer workers always research and discuss the realization as well as improvement on linear list instead of link list.In this article we discuss the algorithm and realization proceeded on single－link list and static－link list.Finally we analyze the complexity of time and space of the two methods.

Bubble sort;storage structure;single－link list;static－link list;algorithm analysis

TP312

A

1008－7974(2011)10－0026－02

2011－05－08

胡新海(1977－)，男，甘肃西和人，在读硕士，陇南师范高等专科学校讲师.

(责任编辑:翟胜)