基于趣味的改進冒泡排序算法的探討

摘 要：本文對傳統(tǒng)的冒泡排序算法進行深入分析，綜合趣味和性能兩方面，提出了改進算法，提高了算法的效率和實用性。

關(guān)鍵詞：冒泡排序；趣味；改進；交換次數(shù)；有序表

中圖分類號：TP301.6

在眾多的排序方法中，冒泡排序算法由于其簡潔的思想及其穩(wěn)定性而得到廣泛的應(yīng)用。本文主要對傳統(tǒng)的冒泡排序算法的基本原理進行了介紹和分析，綜合趣味和性能兩方面提出了改進算法，提高了算法的效率和實用性。

1 傳統(tǒng)的冒泡排序算法

以升序排序為例，傳統(tǒng)冒泡排序算法的基本思想是，依次比較待排序數(shù)據(jù)中的兩個相鄰的數(shù)，如逆序，則進行交換，將小的調(diào)到前頭，直到最后兩個數(shù)進行過比較為止。上述過程稱為第一趟排序，其結(jié)果是讓最大的數(shù)“沉淀”到最后的位置。然后再進行下一趟排序，直至整個數(shù)據(jù)序列有序為止。由于整個排序過程，總是將較大的數(shù)據(jù)向下“沉”，而較小的數(shù)據(jù)向上“浮”，如同水中的氣泡逐步冒出水面一樣，“冒泡排序”因此得名[1]。如果待排序數(shù)據(jù)序列中包含n個數(shù)據(jù)，最終使整個序列有序需要經(jīng)過n-1趟排序來完成。

2 冒泡排序算法的分析與改進

2.1 從趣味上改進冒泡排序算法

傳統(tǒng)的冒泡排序算法很生硬地將一些數(shù)據(jù)的兩兩比較提出來，沒有給數(shù)據(jù)賦予具體的情景和角色，人們只能靠反復(fù)加強記憶來想象兩兩比較的過程和數(shù)據(jù)交換的過程，這樣使得冒泡排序很枯燥抽象。目前許多改進的冒泡排序算法都是從算法的性能上進行優(yōu)化，沒有在趣味上進行探索的，這不利于算法的普及和擴展。為了解決這個問題，下面我們針對趣味性方面對傳統(tǒng)的冒泡排序算法進行改進。趣味冒泡排序算法的思想是：以升序排序為例，把等待排序的數(shù)據(jù)列表看成用隔離墻分成有序和無序的兩個子表；從遠離有序表的一端開始，對無序表中的數(shù)據(jù)進行兩兩比較，如逆序，就交換，等所有元素比較完畢，最小的元素就移到了無序表靠隔離墻的那端，然后隔離墻向無序表方向移動一個位置；這樣就完成了一趟冒泡排序過程。給定含n個元素的一個表，需要進行n-1趟冒泡排序的過程[2]。圖2顯示了趣味冒泡排序的原理。圖3顯示了含5個元素的數(shù)組趣味冒泡排序的過程。

2.2 從性能上改進冒泡排序算法

以升序排序為例，傳統(tǒng)的冒泡排序算法中，一般是以大數(shù)往后沉的方式來實現(xiàn)，很多情況下都有幾趟排序是不會有任何的操作，這種做法會出現(xiàn)大量的無效操作，造成資源的浪費。為了避免這種情況，可以使用一個標記變量來解決，即當排序不發(fā)生任何數(shù)據(jù)交換時，則終止排序。這樣的解決辦法既避免了無效的重復(fù)排序，又避免了有限資源的浪費。

在上面趣味冒泡排序算法中，k就是用來標記交換次數(shù)的標記變量。這樣在趣味冒泡排序算法基礎(chǔ)上從性能上改進冒泡排序算法，只需增加一條語句“if（k==0）break；”即可。用C語言描述基于趣味的改進的冒泡排序算法如圖5所示。

目前從性能上改進冒泡排序算法，除了增加標記交換次數(shù)的變量，還有雙向冒泡排序[3]、交替排序法[4]等。這些改進的冒泡排序算法都可以結(jié)合趣味性，形成更形象生動、性能更優(yōu)的算法。

2.3 改進前后冒泡排序算法有限性分析驗證

引入10個待排序的數(shù)據(jù)：1，20，100，-2，15，8，-100，56，43，12，使用傳統(tǒng)冒泡排序算法，需要9趟排序才能得到有序的列表，使用趣味冒泡排序算法，需要8趟就能得到有序列表，使用趣味改進的冒泡排序算法僅需要7趟就能得到有序列表?？梢姳疚奶岢龅母倪M的算法可以提高算法執(zhí)行效率，是有效的。

3 結(jié)束語

本文對傳統(tǒng)的冒泡排序算法進行了分析，發(fā)現(xiàn)傳統(tǒng)的冒泡排序方法可能會產(chǎn)生一些不必要的操作，而且在趣味性方面也欠缺。在此基礎(chǔ)上，本文提出了基于趣味的改進冒泡排序算法，提高了算法的執(zhí)行效率和實用性。

參考文獻：

[1]宋美英.基于C語言的冒泡排序算法探討[J].現(xiàn)代計算機，2011（12）：48-49.

[2]葛日波.C語言程序設(shè)計[M].北京：北京郵電大學(xué)出版社，2008：126-127.

[3]淦艷等.冒泡排序算法及其改進算法的實驗分析[J].重慶三峽學(xué)院學(xué)報，2011（03）：53-57.

[4]藍超.冒泡排序算法的優(yōu)化[J].兵工自動化，2006（25）：50-52.

作者簡介：李秋（1979-），女，講師，碩士，研究方向：計算機網(wǎng)絡(luò)編程。

作者單位：大連海洋大學(xué)應(yīng)用技術(shù)學(xué)院，遼寧大連 116300