鏈式存儲結(jié)構(gòu)上冒泡排序算法的研究與實現(xiàn)

胡新海

(隴南師范高等專科學校計算機系，甘肅成縣742500)

鏈式存儲結(jié)構(gòu)上冒泡排序算法的研究與實現(xiàn)

胡新海

(隴南師范高等專科學校計算機系，甘肅成縣742500)

線性表上進行的冒泡排序法是一種較簡單的內(nèi)部排序算法，計算機工作者經(jīng)常研究和討論順序表中冒泡排序算法的實現(xiàn)及其改進，很少研究冒泡排序法在鏈表上的實現(xiàn).文中討論了冒泡排序在單鏈表上和靜態(tài)鏈表上的算法及實現(xiàn)過程.最后分析了算法時間復雜度和空間復雜度.

冒泡排序;存儲結(jié)構(gòu);單鏈表;靜態(tài)鏈表;算法分析

冒泡排序是一種較簡單的交換類排序算法.在相關(guān)文獻中討論了其在順序表上的實現(xiàn)過程［1－4］.它通過對相鄰元素的交換，逐步將待排序列變成有序序列.其算法的主要思想是:反復掃描待排序記錄序列，在掃描過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置.

在排序的研究上近幾年來也有一些新的方法，在排序時與鏈表結(jié)構(gòu)結(jié)合，得出一些新的排序思路［5］.在順序表上冒泡排序的實現(xiàn)較簡單，在鏈表上的排序思想基本和順序表上的相似.本文討論了冒泡排序在單鏈表上和靜態(tài)鏈表上的算法及實現(xiàn)過程.最后分析了算法時間復雜度和空間復雜度.與順序表上實現(xiàn)的不同之處是需要標記鏈尾結(jié)點的地址.

1 冒泡排序算法在單鏈表上的實現(xiàn)

對于鏈表每一個結(jié)點看成豎著排列的“氣泡”，然后分別從頭結(jié)點向尾節(jié)點掃描.在掃描的過程中時刻注意兩個相鄰元素的順序，保證前一結(jié)點元素的數(shù)據(jù)域小于后一節(jié)點元素的數(shù)據(jù)，這樣經(jīng)過一趟掃描后就使較大的元素沉到鏈尾，然后記住鏈尾結(jié)點的位置.下次又從頭結(jié)點向后掃描，由于在前一趟掃描過程中最大的元素已經(jīng)沉到鏈尾并記住了該元素的地址，所以這次掃描最大的元素不再參加排序，將剩下的元素進行排序，排序的過程中保證使得后一結(jié)點元素的數(shù)據(jù)域大于前一結(jié)點元素的數(shù)據(jù)域.這樣反復的掃描，并不斷縮小排序空間，直到整個序列有序位置為止.這樣看來，在排序中，只需記住最后排好序的元素的位置即可.定義的鏈式結(jié)構(gòu)和具體算法設(shè)計如下:

2 冒泡排序算法也能在靜態(tài)鏈表上的實現(xiàn)

在靜態(tài)單鏈表中，也可以進行冒泡排序操作，對于靜態(tài)鏈表每一個結(jié)點同樣看成豎著排列的“氣泡”，然后分別從靜態(tài)鏈表的頭結(jié)點開始向尾節(jié)點掃描.在掃描的過程中時刻注意兩個相鄰元素的順序，保證前一結(jié)點元素的數(shù)據(jù)域小于后一節(jié)點元素的數(shù)據(jù)，這樣經(jīng)過一趟掃描后就使較大的元素沉到鏈尾，然后記住鏈尾結(jié)點的位置.下次又從頭結(jié)點向后掃描，由于在前一趟掃描過程中最大的元素已經(jīng)沉到鏈尾并記住了該元素的地址，所以這次掃描最大的元素不再參加排序，將剩下的元素進行排序，排序的過程中保證使得后一結(jié)點元素的數(shù)據(jù)域大于前一結(jié)點元素的數(shù)據(jù)域.這樣反復的掃描，并不斷縮小排序空間，直到整個序列有序位置為止.這樣看來，在排序中，只需記住最后排好序的元素的位置即可.對于靜態(tài)鏈表進行定義和具體算法設(shè)計如下:

3 總結(jié)

在線性表上的冒泡排序，最好情況下的時間復雜度是O(n)，最差和平均情況下的時間復雜度是O(n2)，輔助空間為O(1)，算法比較穩(wěn)定.在單鏈表和靜態(tài)鏈表上的冒泡排序的時間復雜度、穩(wěn)定性與在順序表上完全相同.所以從實現(xiàn)過程和算法的分析，可以很明顯的發(fā)現(xiàn)兩種算法的設(shè)計思想和實現(xiàn)過程相似.只是在單鏈表上和靜態(tài)鏈表上需記住最后排好序的元素的位置(即尾指針).鏈式結(jié)構(gòu)上每個數(shù)據(jù)元素占用一個結(jié)點，而不會有多余的結(jié)點存在，所以數(shù)據(jù)元素所占存儲空間不會浪費.

［1］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學出版社，1997.

［2］耿國華.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.西安:西安電子科技大學出版社，2002.

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

［4］傅清祥，王曉東.算法與數(shù)據(jù)結(jié)構(gòu)［M］.北京:電子工業(yè)出版社，1998.

［5］任志國，等.插入排序算法的雙鏈表模擬［J］.電腦編程與維護，2010(6).

Research and Realization of Bubble Sort Algorithm on Link Storage Structure

HU Xin－h(huán)ai
(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－)，男，甘肅西和人，在讀碩士，隴南師范高等專科學校講師.

(責任編輯:翟勝)