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

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

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

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

0　引言

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

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

（1）排序原理

冒泡排序是一種交換排序法，重復(fù)的在待排序數(shù)列中進(jìn)行走訪，依次比較相鄰的兩個(gè)數(shù)，與排序要求（升序或降序）不對(duì)就交換，直至數(shù)列有序?yàn)橹埂?/p>

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

（2）模擬排序過程

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

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

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

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

2　結(jié)果及分析

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

圖1　

（2）性能分析

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

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

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

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

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

［4］譚浩強(qiáng)著.C程序設(shè)計(jì)（第四版）.清華大學(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è)計(jì)師，研究方向?yàn)樗惴?、?jì)算機(jī)應(yīng)用技術(shù)

2015-09-17

2015-09-30

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

一趟雙泡；冒泡；排序

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

陳勝祥（1997-），男，江蘇南通人，13級(jí)計(jì)算機(jī)對(duì)口單招學(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.