李湘，陳勝祥（江蘇南通工貿(mào)技師學(xué)院，南通 510663）

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

李湘，陳勝祥
（江蘇南通工貿(mào)技師學(xué)院，南通 510663）

0　引言

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

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

（1）排序原理

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

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

（2）模擬排序過程

假設(shè)有5個數(shù)（升序排序，最差情況）：

經(jīng)過兩趟排序，5個數(shù)已經(jīng)完全有序。

（3）排序?qū)崿F(xiàn)：C語言源代碼（以5個數(shù)為例）

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

2　結(jié)果及分析

（1）程序運行結(jié)果

圖1　

（2）性能分析

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

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

［2］Clifford A Shaffer著.數(shù)據(jù)結(jié)構(gòu)與算法分析.張銘等譯.電子工業(yè)出版社，2010.

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

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

［4］譚浩強著.C程序設(shè)計（第四版）.清華大學(xué)出版社，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-），女，江蘇通州人，碩士，講師，軟件設(shè)計師，研究方向為算法、計算機應(yīng)用技術(shù)

2015-09-17

2015-09-30

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

一趟雙泡；冒泡；排序

中國職協(xié)2014年課題立項（No.201440）

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

"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.