鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上冒泡排序算法的研究與實(shí)現(xiàn)

胡新海

(隴南師范高等?？茖W(xué)校計(jì)算機(jī)系，甘肅成縣742500)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上冒泡排序算法的研究與實(shí)現(xiàn)

胡新海

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

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

［2］耿國華.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.西安:西安電子科技大學(xué)出版社，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］.電腦編程與維護(hù)，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－)，男，甘肅西和人，在讀碩士，隴南師范高等?？茖W(xué)校講師.

(責(zé)任編輯:翟勝)