一種“一趟雙泡”的新型冒泡排序

李湘，陳勝祥（江蘇南通工貿技師學院，南通 510663）

一種“一趟雙泡”的新型冒泡排序

李湘，陳勝祥
（江蘇南通工貿技師學院，南通 510663）

0　引言

排序是計算機處理數據的一項重要工作，其效率的高低直接影響著計算機的性能好壞，選擇一個優質的排序對一臺計算機的工作效率尤為重要，因此，排序算法的研究成為了計算機專業人士永恒的研究課題之一。所謂排序，即將一堆雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。在眾多排序算法中，冒泡排序是一種最簡單的排序算法。本文將在原有的冒泡排序算法基礎上進行改進、實現并分析。

1　“一趟雙泡”的新型冒泡排序

（1）排序原理

冒泡排序是一種交換排序法，重復的在待排序數列中進行走訪，依次比較相鄰的兩個數，與排序要求（升序或降序）不對就交換，直至數列有序為止。

“一趟雙泡”冒泡排序是在基本冒泡排序基礎上改進的，基本冒泡排序每趟排序只有一個符合要求的數（最大數或最小數）沉底；而“一趟雙泡”冒泡排序每趟排序有兩個符合要求的數沉底，兩個符合要求的數，以升序為例，即每趟排序將數列中最大或次大的數沉底，其排序基本算法描述為：對N個記錄進行升序排序，先將第1個與第2個記錄的鍵值進行比較，若a［0］.key>a ［1］.key，則將兩個記錄進行交換，同時設第0個記錄的位置設為第二大記錄位置max2，再從第2個記錄開始至第N-i-1（i為當前比較的趟數）個記錄從前往后進行兩兩比較，若a［j-1］.key>a［j］.key，則將兩個記錄進行交換，找出當前排序中的最大記錄，將其移到當前排序的最后一個位置，同時，在交換過程中還找出當趟排序中第二大記錄的位置，最后將第二大記錄放到當趟排序倒數第二個位置上。重復以上過程，直至沒有記錄交換為止，完成最終排序目標［1］。

（2）模擬排序過程

假設有5個數（升序排序，最差情況）：

經過兩趟排序，5個數已經完全有序。

（3）排序實現：C語言源代碼（以5個數為例）

if（a［0］>a［1］）//現在至少是2個數字我們可以先對最前面2個進行對比進行排序

2　結果及分析

（1）程序運行結果

圖1　

（2）性能分析

若有N個待排序記錄，若初始記錄是反序的，如同本程序，其算法時間復雜度為O（（N/2）2）；而基本冒泡排序算法的時間復雜度為O（N2）。具體來講，對于N個記錄，“一趟雙泡”冒泡排序僅需要進行N/2趟排序，而基本冒泡排序需要N－1趟排序。由此可見，“一趟雙泡”冒泡排序算法同基本冒泡排序算法相比，時間復雜度大大降低，整整縮小到1/4，說明該算法是可行的，它完全可以提高計算機的工作效率。

［1］（美）Michael T.Goodrich Roberto Tamassia.算法分析與設計.人民郵電出版社，2006.

［2］Clifford A Shaffer著.數據結構與算法分析.張銘等譯.電子工業出版社，2010.

［2］一類基于冒泡排序的改進算法的分析與比.渝西學院學報（自然科學版），2004-3，3（1）.

［3］胡金初.計算機算法.清華大學出版，2009-3.

［4］譚浩強著.C程序設計（第四版）.清華大學出版社，2012-10.

A Double Bubble；Bubble；Sort

A New Kind of"a Sort of Double Bubble"

LI Xiang，CHEN Sheng-xiang
（Nantong Jiangsu Industry and Trade Technician College，Nantong 226010）

1007-1423（2015）30-0057-03

10.3969/j.issn.1007-1423.2015.30.016

李湘（1983-），女，江蘇通州人，碩士，講師，軟件設計師，研究方向為算法、計算機應用技術

2015-09-17

2015-09-30

“一趟雙泡”是一種新型的冒泡排序思想，意思是從一趟排序中同時找出符合要求的兩個數。從排序原理、排序過程及實現進行闡述，對結果進行分析。

一趟雙泡；冒泡；排序

中國職協2014年課題立項（No.201440）

陳勝祥（1997-），男，江蘇南通人，13級計算機對口單招學生

"a trip to the double bubble"is a new type of bubble sort thought，meaning from the trip to sort out in line with the requirements of the two numbers.Analyzes the sorting principle，process and implementation.