外文原文SIMPLESORTINGOVERVIEWASSOONASYOUCREATEASIGNIFICANTDATABASE,YOULLPROBABLYTHINKOFREASONSTOSORTITINVARIOUSWAYSYOUNEEDTOARRANGENAMESINALPHABETICALORDER,STUDENTSBYGRADE,CUSTOMERSBYZIPCODE,HOMESALESBYPRICE,CITIESINORDEROFINCREASINGPOPULATION,COUNTRIESBYGNP,STARSBYMAGNITUDE,ANDSOONSORTINGDATAMAYALSOBEAPRELIMINARYSTEPTOSEARCHINGITASABINARYSEARCH,WHICHCANBEAPPLIEDONLYTOSORTEDDATA,ISMUCHFASTERTHANALINEARSEARCHSORTINGISSOIMPORTANTANDPOTENTIALLYSOTIMECONSUMING,ITHASBEENTHESUBJECTOFEXTENSIVERESEARCHINCOMPUTERSCIENCE,ANDSOMEVERYSOPHISTICATEDMETHODSHAVEBEENDEVELOPEDINTHISCHAPTERWELLLOOKATTHREEOFTHESIMPLERALGORITHMSTHEBUBBLESORT,THESELECTIONSORT,ANDTHEINSERTIONSORTTHETECHNIQUESDESCRIBEDINTHISCHAPTER,WHILEUNSOPHISTICATEDANDCOMPARATIVELYSLOW,ARENEVERTHELESSWORTHEXAMININGBESIDESBEINGEASIERTOUNDERSTAND,THEYAREACTUALLYBETTERINSOMECIRCUMSTANCESTHANTHEMORESOPHISTICATEDALGORITHMSTHESORTINGALGORITHMSAREIMPLEMENTEDASMETHODSOFSIMILARARRAYCLASSESBESURETOTRYOUTTHEWORKSHOPAPPLETSINCLUDEDINTHISCHAPTERTHEYAREMOREEFFECTIVEINEXPLAININGHOWTHESORTINGALGORITHMSWORKTHANPROSEANDSTATICPICTURESCOULDEVERBEHOWWOULDYOUDOITIMAGINETHATYOURKIDSLEAGUEBASEBALLTEAMISLINEDUPONTHEFIELD,THEREGULATIONNINEPLAYERS,PLUSANEXTRA,HAVESHOWNUPFORPRACTICEYOUWANTTOARRANGETHEPLAYERSINORDEROFINCREASINGHEIGHTWITHTHESHORTESTPLAYERONTHELEFT,FORTHETEAMPICTUREHOWWOULDYOUGOABOUTTHISSORTINGPROCESSASAHUMANBEING,YOUHAVEADVANTAGESOVERACOMPUTERPROGRAMYOUCANSEEALLTHEKIDSATONCE,ANDYOUCANPICKOUTTHETALLESTKIDALMOSTINSTANTLYYOUDONTNEEDTOLABORIOUSLYMEASUREANDCOMPAREEVERYONEALSO,THEKIDSDONTNEEDTOOCCUPYPARTICULARPLACESTHEYCANJOSTLEEACHOTHER,PUSHEACHOTHERALITTLETOMAKEROOM,ANDSTANDBEHINDORINFRONTOFEACHOTHERAFTERSOMEADHOCREARRANGING,YOUWOULDHAVENOTROUBLEINLININGUPALLTHEKIDS,ACOMPUTERPROGRAMISNTABLETOGLANCEOVERTHEDATAINTHISWAYITCANONLYCOMPARETWOPLAYERSATONCE,BECAUSETHATSHOWTHECOMPARISONOPERATORSWORKTHISTUNNELVISIONONTHEPARTOFALGORITHMSWILLBEARECURRINGTHEMETHINGSMAYSEEMSIMPLETOUSHUMANS,BUTTHEALGORITHMCANTSEETHEBIGPICTUREANDMUST,THEREFORE,CONCENTRATEONTHEDETAILSANDFOLLOWSOMESIMPLERULESTHETHREEALGORITHMSINTHISCHAPTERALLINVOLVETWOSTEPS,EXECUTEDOVERANDOVERUNTILTHEDATAISSORTED1COMPARETWOITEMS2SWAPTWOITEMSORCOPYONEITEMHOWEVER,EACHALGORITHMHANDLESTHEDETAILSINADIFFERENTWAYBUBBLESORTTHEBUBBLESORTISNOTORIOUSLYSLOW,BUTITSCONCEPTUALLYTHESIMPLESTOFTHESORTINGALGORITHMS,ANDFORTHATREASONISAGOODBEGINNINGFOROUREXPLORATIONOFSORTINGTECHNIQUESBUBBLESORTINGTHEBASEBALLPLAYERSIMAGINETHATYOURENEARSIGHTEDLIKEACOMPUTERPROGRAMSOTHATYOUCANSEEONLYTWOOFTHEBASEBALLPLAYERSATTHESAMETIME,IFTHEYRENEXTTOEACHOTHERANDIFYOUSTANDVERYCLOSETOTHEMGIVENTHISIMPEDIMENT,HOWWOULDYOUSORTTHEMLETSASSUMETHEREARENPLAYERS,ANDTHEPOSITIONSTHEYRESTANDINGINARENUMBEREDFROM0ONTHELEFTTON1ONTHERIGHTTHEBUBBLESORTROUTINEWORKSLIKETHISYOUSTARTATTHELEFTENDOFTHELINEANDCOMPARETHETWOKIDSINPOSITIONS0AND1IFTHEONEONTHELEFTIN0ISTALLER,YOUSWAPTHEMIFTHEONEONTHERIGHTISTALLER,YOUDONTDOANYTHINGTHENYOUMOVEOVERONEPOSITIONANDCOMPARETHEKIDSINPOSITIONS1AND2AGAIN,IFTHEONEONTHELEFTISTALLER,YOUSWAPTHEMHEREARETHERULESYOUREFOLLOWING1COMPARETWOPLAYERS2IFTHEONEONTHELEFTISTALLER,SWAPTHEM3MOVEONEPOSITIONRIGHTYOUCONTINUEDOWNTHELINETHISWAYUNTILYOUREACHTHERIGHTENDYOUHAVEBYNOMEANSFINISHEDSORTINGTHEKIDS,BUTYOUDOKNOWTHATTHETALLESTKIDISONTHERIGHTTHISMUSTBETRUE,BECAUSEASSOONASYOUENCOUNTERTHETALLESTKID,YOULLENDUPSWAPPINGHIMEVERYTIMEYOUCOMPARETWOKIDS,UNTILEVENTUALLYHEORSHEWILLREACHTHERIGHTENDOFTHELINETHISISWHYITSCALLEDTHEBUBBLESORTASTHEALGORITHMPROGRESSES,THEBIGGESTITEMS“BUBBLEUP“TOTHETOPENDOFTHEARRAYAFTERTHISFIRSTPASSTHROUGHALLTHEDATA,YOUVEMADEN1COMPARISONSANDSOMEWHEREBETWEEN0ANDN1SWAPS,DEPENDINGONTHEINITIALARRANGEMENTOFTHEPLAYERSTHEITEMATTHEENDOFTHEARRAYISSORTEDANDWONTBEMOVEDAGAINNOWYOUGOBACKANDSTARTANOTHERPASSFROMTHELEFTENDOFTHELINEAGAINYOUGOTOWARDTHERIGHT,COMPARINGANDSWAPPINGWHENAPPROPRIATEHOWEVER,THISTIMEYOUCANSTOPONEPLAYERSHORTOFTHEENDOFTHELINE,ATPOSITIONN2,BECAUSEYOUKNOWTHELASTPOSITION,ATN1,ALREADYCONTAINSTHETALLESTPLAYERTHISRULECOULDBESTATEDASWHENYOUREACHTHEFIRSTSORTEDPLAYER,STARTOVERATTHELEFTENDOFTHELINEYOUCONTINUETHISPROCESSUNTILALLTHEPLAYERSAREINORDERTHISISALLMUCHHARDERTODESCRIBETHANITISTODEMONSTRATE,SOLETSWATCHTHEBUBBLESORTWORKSHOPAPPLETATWORKTHEBUBBLESORTWORKSHOPAPPLETSTARTTHEBUBBLESORTWORKSHOPAPPLETYOULLSEESOMETHINGTHATLOOKSLIKEABARGRAPH,WITHTHEBARHEIGHTSRANDOMLYARRANGED,THERUNBUTTONTHISISATWOSPEEDGRAPHYOUCANEITHERLETITRUNBYITSELFORYOUCANSINGLESTEPTHROUGHTHEPROCESSTOGETAQUICKIDEAOFWHATHAPPENS,CLICKTHERUNBUTTONTHEALGORITHMWILLBUBBLESORTTHEBARSWHENITFINISHES,IN10SECONDSORSO,THEBARSWILLBESORTED,THENEWBUTTONTODOANOTHERSORT,PRESSTHENEWBUTTONNEWCREATESANEWSETOFBARSANDINITIALIZESTHESORTINGROUTINEREPEATEDPRESSESOFNEWTOGGLEBETWEENTWOARRANGEMENTSOFBARSARANDOMORDERASSHOWNINFIGURE35,ANDANINVERSEORDERINGWHERETHEBARSARESORTEDBACKWARDTHISINVERSEORDERINGPROVIDESANEXTRACHALLENGEFORMANYSORTINGALGORITHMSTHESTEPBUTTONTHEREALPAYOFFFORUSINGTHEBUBBLESORTWORKSHOPAPPLETCOMESWHENYOUSINGLESTEPTHROUGHASORTYOULLBEABLETOSEEEXACTLYHOWTHEALGORITHMCARRIESOUTEACHSTEPSTARTBYCREATINGANEWRANDOMLYARRANGEDGRAPHWITHNEWYOULLSEETHREEARROWSPOINTINGATDIFFERENTBARSTWOARROWS,LABELEDINNERANDINNER1,ARESIDEBYSIDEONTHELEFTANOTHERARROW,OUTER,STARTSONTHEFARRIGHTTHENAMESARECHOSENTOCORRESPONDTOTHEINNERANDOUTERLOOPVARIABLESINTHENESTEDLOOPSUSEDINTHEALGORITHMCLICKONCEONTHESTEPBUTTONYOULLSEETHEINNERANDTHEINNER1ARROWSMOVETOGETHERONEPOSITIONTOTHERIGHT,SWAPPINGTHEBARSIFITSAPPROPRIATETHESEARROWSCORRESPONDTOTHETWOPLAYERSYOUCOMPARED,ANDPOSSIBLYSWAPPED,INTHEBASEBALLSCENARIOAMESSAGEUNDERTHEARROWSTELLSYOUWHETHERTHECONTENTSOFINNERANDINNER1WILLBESWAPPED,BUTYOUKNOWTHISJUSTFROMCOMPARINGTHEBARSIFTHETALLERONEISONTHELEFT,THEYLLBESWAPPEDMESSAGESATTHETOPOFTHEGRAPHTELLYOUHOWMANYSWAPSANDCOMPARISONSHAVEBEENCARRIEDOUTSOFARACOMPLETESORTOF10BARSREQUIRES45COMPARISONSAND,ONTHEAVERAGE,ABOUT22SWAPSCONTINUEPRESSINGSTEPEACHTIMEINNERANDINNER1FINISHGOINGALLTHEWAYFROM0TOOUTER,THEOUTERPOINTERMOVESONEPOSITIONTOTHELEFTATALLTIMESDURINGTHESORTINGPROCESS,ALLTHEBARSTOTHERIGHTOFOUTERARESORTEDTHOSETOTHELEFTOFANDATOUTERARENOTTHESIZEBUTTONTHESIZEBUTTONTOGGLESBETWEEN10BARSAND100BARSWHATTHE100RANDOMBARSLOOKLIKEYOUPROBABLYDONTWANTTOSINGLESTEPTHROUGHTHESORTINGPROCESSFOR100BARSUNLESSYOUREUNUSUALLYPATIENTPRESSRUNINSTEAD,ANDWATCHHOWTHEBLUEINNERANDINNER1POINTERSSEEMTOFINDTHETALLESTUNSORTEDBARANDCARRYITDOWNTHEROWTOTHERIGHT,INSERTINGITJUSTTOTHELEFTOFTHESORTEDBARSTHEBARSTOTHERIGHTOFTHEREDLONGESTARROWARESORTEDTHEBARSTOTHELEFTAREBEGINNINGTOLOOKSORTED,BUTMUCHWORKREMAINSTOBEDONEIFYOUSTARTEDASORTWITHRUNANDTHEARROWSAREWHIZZINGAROUND,YOUCANFREEZETHEPROCESSATANYPOINTBYPRESSINGTHESTEPBUTTONYOUCANTHENSINGLESTEPTOWATCHTHEDETAILSOFTHEOPERATION,ORPRESSRUNAGAINTORETURNTOHIGHSPEEDMODETHEDRAWBUTTONSOMETIMESWHILERUNNINGTHESORTINGALGORITHMATFULLSPEED,THECOMPUTERTAKESTIMEOFFTOPERFORMSOMEOTHERTASKTHISCANRESULTINSOMEBARSNOTBEINGDRAWNIFTHISHAPPENS,YOUCANPRESSTHEDRAWBUTTONTOREDRAWALLTHEBARSDOINGSOPAUSESTHERUN,SOYOULLNEEDTOPRESSTHERUNBUTTONAGAINTOCONTINUEYOUCANPRESSDRAWATANYTIMETHERESEEMSTOBEAGLITCHINTHEDISPLAYJAVACODEFORABUBBLESORTINTHEBUBBLESORTJAVAPROGRAM,SHOWNINLISTING31,ACLASSCALLEDARRAYBUBENCAPSULATESANARRAYA,WHICHHOLDSVARIABLESOFTYPEDOUBLEINAMORESERIOUSPROGRAM,THEDATAWOULDPROBABLYCONSISTOFOBJECTS,BUTWEUSEAPRIMITIVETYPEFORSIMPLICITYWELLSEEHOWOBJECTSARESORTEDINTHEOBJECTSORTJAVAPROGRAMINTHELASTSECTIONOFTHISCHAPTERALSO,TOREDUCETHESIZEOFTHELISTING,WEDONTSHOWFINDANDDELETEMETHODSWITHTHEARRAYBUBCLASS,ALTHOUGHTHEYWOULDNORMALLYBEPARTOFASUCHACLASSLISTING31THEBUBBLESORTJAVAPROGRAM/BUBBLESORTJAVA/DEMONSTRATESBUBBLESORT/TORUNTHISPROGRAMCJAVABUBBLESORTAPP/CLASSARRAYBUBPRIVATEDOUBLEA/REFTOARRAYAPRIVATEINTNELEMS/NUMBEROFDATAITEMS/PUBLICARRAYBUBINTMAX/CONSTRUCTORANEWDOUBLEMAX/CREATETHEARRAYNELEMS0/NOITEMSYET/PUBLICVOIDINSERTDOUBLEVALUE/PUTELEMENTINTOARRAYANELEMSVALUE/INSERTITNELEMS/INCREMENTSIZE/PUBLICVOIDDISPLAY/DISPLAYSARRAYCONTENTSFORINTJ0J1OUT/OUTERLOOPBACKWARDFORIN0INAIN1/OUTOFORDERSWAPIN,IN1/SWAPTHEM/ENDBUBBLESORT/PRIVATEVOIDSWAPINTONE,INTTWODOUBLETEMPAONEAONEATWOATWOTEMP/ENDCLASSARRAYBUB/CLASSBUBBLESORTAPPPUBLICSTATICVOIDMAINSTRINGARGSINTMAXSIZE100/ARRAYSIZEARRAYBUBARR/REFERENCETOARRAYARRNEWARRAYBUBMAXSIZE/CREATETHEARRAYARRINSERT77/INSERT10ITEMSARRINSERT99ARRINSERT44ARRINSERT55ARRINSERT22ARRINSERT88ARRINSERT11ARRINSERT00ARRINSERT66ARRINSERT33ARRDISPLAY/DISPLAYITEMSARRBUBBLESORT/BUBBLESORTTHEMARRDISPLAY/DISPLAYTHEMAGAIN/ENDMAIN/ENDCLASSBUBBLESORTAPPTHECONSTRUCTORANDTHEINSERTANDDISPLAYMETHODSOFTHISCLASSARESIMILARTOTHOSEWEVESEENBEFOREHOWEVER,THERESANEWMETHODBUBBLESORTWHENTHISMETHODISINVOKEDFROMMAIN,THECONTENTSOFTHEARRAYAREREARRANGEDINTOSORTEDORDERTHEMAINROUTINEINSERTS10ITEMSINTOTHEARRAYINRANDOMORDER,DISPLAYSTHEARRAY,CALLSBUBBLESORTTOSORTIT,ANDTHENDISPLAYSITAGAINHERESTHEOUTPUT77994455228811066330112233445566778899THEBUBBLESORTMETHODISONLYFOURLINESLONGHEREITIS,EXTRACTEDFROMTHELISTINGPUBLICVOIDBUBBLESORTINTOUT,INFOROUTNELEMS1OUT1OUT/OUTERLOOPBACKWARDFORIN0INAIN1/OUTOFORDERSWAPIN,IN1/SWAPTHEM/ENDBUBBLESORTTHEIDEAISTOPUTTHESMALLESTITEMATTHEBEGINNINGOFTHEARRAYINDEX0ANDTHELARGESTITEMATTHEENDINDEXNELEMS1THELOOPCOUNTEROUTINTHEOUTERFORLOOPSTARTSATTHEENDOFTHEARRAY,ATNELEMS1,ANDDECREMENTSITSELFEACHTIMETHROUGHTHELOOPTHEITEMSATINDICESGREATERTHANOUTAREALWAYSCOMPLETELYSORTEDTHEOUTVARIABLEMOVESLEFTAFTEREACHPASSBYINSOTHATITEMSTHATAREALREADYSORTEDARENOLONGERINVOLVEDINTHEALGORITHMTHEINNERLOOPCOUNTERINSTARTSATTHEBEGINNINGOFTHEARRAYANDINCREMENTSITSELFEACHCYCLEOFTHEINNERLOOP,EXITINGWHENITREACHESOUTWITHINTHEINNERLOOP,THETWOARRAYCELLSPOINTEDTOBYINANDIN1ARECOMPAREDANDSWAPPEDIFTHEONEININISLARGERTHANTHEONEININ1FORCLARITY,WEUSEASEPARATESWAPMETHODTOCARRYOUTTHESWAPITSIMPLYEXCHANGESTHETWOVALUESINTHETWOARRAYCELLS,USINGATEMPORARYVARIABLETOHOLDTHEVALUEOFTHEFIRSTCELLWHILETHEFIRSTCELLTAKESONTHEVALUEINTHESECOND,THENSETTINGTHESECONDCELLTOTHETEMPORARYVALUEACTUALLY,USINGASEPARATESWAPMETHODMAYNOTBEAGOODIDEAINPRACTICE,BECAUSETHEFUNCTIONCALLADDSASMALLAMOUNTOFOVERHEADIFYOUREWRITINGYOUROWNSORTINGROUTINE,YOUMAYPREFERTOPUTTHESWAPINSTRUCTIONSINLINETOGAINASLIGHTINCREASEINSPEEDINVARIANTSINMANYALGORITHMSTHEREARECONDITIONSTHATREMAINUNCHANGEDASTHEALGORITHMPROCEEDSTHESECONDITIONSARECALLEDINVARIANTSRECOGNIZINGINVARIANTSCANBEUSEFULINUNDERSTANDINGTHEALGORITHMINCERTAINSITUATIONSTHEYMAYALSOBEHELPFULINDEBUGGINGYOUCANREPEATEDLYCHECKTHATTHEINVARIANTISTRUE,ANDSIGNALANERRORIFITISNTINTHEBUBBLESORTJAVAPROGRAM,THEINVARIANTISTHATTHEDATAITEMSTOTHERIGHTOFOUTERARESORTEDTHISREMAINSTRUETHROUGHOUTTHERUNNINGOFTHEALGORITHMONTHEFIRSTPASS,NOTHINGHASBEENSORTEDYET,ANDTHEREARENOITEMSTOTHERIGHTOFOUTERBECAUSEITSTARTSONTHERIGHTMOSTELEMENTEFFICIENCYOFTHEBUBBLESORTASYOUCANSEEBYWATCHINGTHEWORKSHOPAPPLETWITH10BARS,THEINNERANDINNER1ARROWSMAKE9COMPARISONSONTHEFIRSTPASS,8ONTHESECOND,ANDSOON,DOWNTO1COMPARISONONTHELASTPASSFOR10ITEMSTHISIS98765432145INGENERAL,WHERENISTHENUMBEROFITEMSINTHEARRAY,THEREAREN1COMPARISONSONTHEFIRSTPASS,N2ONTHESECOND,ANDSOONTHEFORMULAFORTHESUMOFSUCHASERIESISN1N2N31NN1/2NN1/2IS45WHENNIS10THUSTHEALGORITHMMAKESABOUTN2/2COMPARISONSIGNORINGTHE1,WHICHDOESNTMAKEMUCHDIFFERENCE,ESPECIALLYIFNISLARGETHEREAREFEWERSWAPSTHANTHEREARECOMPARISONS,BECAUSETWOBARSARESWAPPEDONLYIFTHEYNEEDTOBEIFTHEDATAISRANDOM,ASWAPISNECESSARYABOUTHALFTHETIME,SOTHEREWILLBEABOUTN2/4SWAPSALTHOUGHINTHEWORSTCASE,WITHTHEINITIALDATAINVERSELYSORTED,ASWAPISNECESSARYWITHEVERYCOMPARISONBOTHSWAPSANDCOMPARISONSAREPROPORTIONALTON2BECAUSECONSTANTSDONTCOUNTINBIGONOTATION,WECANIGNORETHE2ANDTHE4ANDSAYTHATTHEBUBBLESORTRUNSINON2TIMETHISISSLOW,ASYOUCANVERIFYBYRUNNINGTHEWORKSHOPAPPLETWITH100BARSWHENEVERYOUSEENESTEDLOOPSSUCHASTHOSEINTHEBUBBLESORTANDTHEOTHERSORTINGALGORITHMSINTHISCHAPTER,YOUCANSUSPECTTHATANALGORITHMRUNSINON2TIMETHEOUTERLOOPEXECUTESNTIMES,ANDTHEINNERLOOPEXECUTESNORPERHAPSNDIVIDEDBYSOMECONSTANTTIMESFOREACHCYCLEOFTHEOUTERLOOPTHISMEANSYOUREDOINGSOMETHINGAPPROXIMATELYNNORN2TIMESSOURCEBSBROGLIATTITGSMITHDATASTRUCTURESANDALGORITHMS,2013C中文翻譯簡單分類總的看法當(dāng)你要創(chuàng)建一個巨大的數(shù)據(jù)庫時，你很容易就會想到各種各樣的數(shù)據(jù)排序方法。你可以用開頭字母順序來將姓名排序，依分?jǐn)?shù)高低將學(xué)生排序，郵編來給顧客排序，依工資水平來給家庭排序，也可以依人口增長的速度給城市排序，依GDP的大小來給國家排序，甚至依體積的大小來給行星排序，等等。數(shù)據(jù)排序是數(shù)據(jù)查詢的基礎(chǔ)與前提。例如二進(jìn)制計數(shù)查詢，這項技術(shù)也是應(yīng)用在數(shù)據(jù)排序的基礎(chǔ)上的，因為這樣做會提高排序和查詢的速度。排序問題十分重要并有著良好的發(fā)展?jié)摿ΑＤ壳皵?shù)據(jù)排序在電腦科學(xué)技術(shù)方面已經(jīng)形成了一個單獨的研究領(lǐng)域。截至今天，很多種高精尖端的方法已經(jīng)被開發(fā)出來。在這里我將說一下相對比較簡單的計算機(jī)排序程序冒泡式排序。冒泡式排序法、選擇式排序法、插入式排序法都是數(shù)據(jù)排序方面比較簡單的方法，之所以選擇冒泡式是因為它的簡單適用，更是目前數(shù)據(jù)排序技術(shù)的基礎(chǔ)開端?，F(xiàn)在要講的是冒泡式技術(shù)，雖然不是十分尖端先進(jìn)速的相對較慢，但它仍存在研究的價值。除此之外，它在某些情況下，甚至比尖端先進(jìn)技術(shù)更為實用。計算機(jī)排序程序是以一個電腦簡單程序為方法的工具，我確信通過這一部分的對排序程序的提煉，可以比單純文章或靜態(tài)圖片的講解更加生動易理解。我們應(yīng)該怎樣做想象一下，訓(xùn)練場上有一個兒童棒球隊，其中有九個正式隊員一個替補(bǔ)隊員，這十個人在準(zhǔn)備練習(xí)?，F(xiàn)在你想讓這些隊員從矮到高站成一排準(zhǔn)備拍照，你將如何進(jìn)行“排序操作”呢作為人類，你一定會比電腦更先進(jìn)。首先你可以用眼睛觀察，可以在一瞬間挑出最高的小隊員。這都免去了一一測量和相互比較。然后這些隊員可以相互推擠著自己進(jìn)行比較，騰出空間，自己站到某個人的前邊或者后邊。排好隊，同時省去占用訓(xùn)練場地的麻煩。就這樣在現(xiàn)實中，給隊員拍照進(jìn)行的排序是沒有任何阻礙的。但是，一個電腦程序不可能使用這個方法去整理數(shù)據(jù)，根據(jù)操作系統(tǒng)的工作原理，它只能馬上比較兩個隊員。這種事情對于人來說十分簡單，但是電腦不可能像人一樣抓住全景來看。因此將細(xì)節(jié)歸納可得出以下結(jié)論電腦程序包含兩個步驟，并反復(fù)執(zhí)行這兩個步驟，這直到排序完成。1比較其中兩項。2交換這兩項或保持原狀。當(dāng)然，有的不同的程序會使用別的方法去整理數(shù)據(jù)。冒泡式排序法冒泡式排序法常被冠以“慢”的罵名。但是，它是最簡單的排序概念。正因為如此，研究冒泡式排序?qū)俏覀兲剿麟娔X排序技術(shù)的最好起點。冒泡式排序法排序棒球隊員假設(shè)你是一個近視眼（電腦程序?qū)嶋H上就像一個近視眼的人），以至于你一次只能局限的看到兩個隊員，又或者隊員們離的相對比較遠(yuǎn)，你離他們又很近，也可導(dǎo)致你只能看到隊員中的一兩個。在這個困難下，你要怎么給他們排序?，F(xiàn)在假設(shè)讓這十個隊員一字排開，給他們從左到右進(jìn)行編號，1、2、3N1號，冒泡式排序法常規(guī)工作就是這么工作。下面你要從左開始向右移動，去比較0和1位置上的兩個隊員的身高。如果左邊的（0號）的隊員高你就要將兩個隊員交換位置。如果右邊（1號）的高一點，你就維持原狀，繼續(xù)向右移動，去比較1號和2號位置的隊員。同樣如果左邊隊員高，交換，否則，維持原狀。下面是要履行的規(guī)則1比較兩個隊員2如果左邊的較高，交換兩者的位置3向右移動一個位置，繼續(xù)你可以如此進(jìn)行下去直到你到達(dá)隊伍的最右端。這樣的排序除了讓你知道隊伍最右側(cè)站著的是最高的隊員外，沒有其他更多的意義。事實上也是如此，因為當(dāng)你看到最高的隊員時你也還是會讓他比較交換下去，直到他站到隊伍的最右邊為止。這就是它叫做“冒泡式排序”的原因它的宗旨就是最大的泡先向上升。作為一個電腦程序，就這樣一直“冒泡”直到程序結(jié)束。在第一次篩選整理了這些數(shù)據(jù)后，你一定做了N1次比較，同時進(jìn)行了0至N1次交換。一切都是以最開始的兩個隊員的交換為基礎(chǔ)。這一項在程序的最后已經(jīng)排序完成，不用再去比較、移動。現(xiàn)在你回到原點重新開始，再次從左到右移動，去比較、交換或保持原狀，但這次你會在N2號隊員位置上結(jié)束此次排序。因為前次比較知道第N1號的隊員現(xiàn)在一定時最高的隊員，不需要再進(jìn)行比較。這個規(guī)則就可以像下面所說的一樣當(dāng)你從最左邊開始時，一直比較到完成，你重復(fù)繼續(xù)這過程，一直到所有對員都按照要求的順序站好。這種描述比演示要復(fù)雜難以理解。所以，我要講一下冒泡排序工作站的程序的工作過程。冒泡排序工作站的程序打開冒泡排序工作站程序，你將看到一些很類似于數(shù)據(jù)曲線的東西，這些數(shù)據(jù)高度隨機(jī)的進(jìn)行排列。點擊運行按鈕有兩個選項，可以讓它自動運行也可以通過輸入程序一步一步進(jìn)行。若要快速地得到結(jié)果，單擊運行按鈕，計算機(jī)程序?qū)⒆詣舆M(jìn)行冒泡式排序，大約10秒左右這些記錄數(shù)據(jù)就會被排序完成，得到結(jié)果。新建按鈕同時想要去做另一個排序，就要使用新建按鈕?？梢孕骆I入一套新的記錄數(shù)據(jù)讓程序從頭開始自己運行常規(guī)的排序。若再單擊切換鍵就可以在兩個記錄地排序中進(jìn)行切換操作了。其中一個命令在前臺運行，另一個則在后臺運行排序。這兩個不同的命令程序的同時執(zhí)行給電腦排序系統(tǒng)帶來了新的技術(shù)挑戰(zhàn)。步進(jìn)按鈕使用冒泡式排序工作程序的真正價值表現(xiàn)在你排序中的單個步驟你可以精確的看到計算機(jī)程序是如何進(jìn)行每一步的，再使用新建按鈕創(chuàng)建一個新的隨機(jī)整理排序后，你將會看到三個指向不同數(shù)據(jù)記錄的指針，被標(biāo)記為INNER和INNER1的兩個指針并排在左邊，另一個標(biāo)記為OUTER的指針從最右邊開始運行。（名字的選擇在程序的重疊循環(huán)中要與內(nèi)部、外部變量保持一致）單擊一次“STEP”按鈕，你會看到INNER和INNER1指針向右移動一個位置。如果合適的話則交換數(shù)據(jù)這些指針始終與你比較的兩個參數(shù)數(shù)據(jù)保持一致并且交換，在上面所說的棒球隊員情況中也應(yīng)該是這樣解釋。指針下面的信息表明INNER和INNER的內(nèi)容將被交換，但實際上應(yīng)清楚這只是通過比較數(shù)據(jù)如果更高的隊員在左邊他們將被交換在程序曲線上方的信息告訴你至今有多少個比較，判斷和交換已經(jīng)執(zhí)行（10個數(shù)據(jù)的完全排序要求進(jìn)行45次比較判斷，平均有22次的交換）。再單擊STEP按鈕每一次INNER和INNER1完成從0到OUTER的整個路徑這個“OUTER”指針就向左移動一個位置，在排序過程中所有的在OUTER右側(cè)的數(shù)據(jù)將被排序，而在OUTER左側(cè)（或在OUTER上）的將維持不動。排列按鈕這個排列按鈕在10條至100條數(shù)據(jù)之間進(jìn)行切換除非你有不同尋常的耐心，否則你不可能想一步一步的去完成這100個數(shù)據(jù)的整理，排序。你可以單擊“運行”按鈕代替，仔細(xì)觀察藍(lán)色的INNER和INNER1指針是如何找到最高的未排序的數(shù)據(jù)，然后把這個數(shù)據(jù)從右邊取下，并把它插入左邊已排序好的數(shù)據(jù)中。如果你使用“運行”按鈕啟動分類排序，指針在周圍迅速移動，你可以在任意時間點擊“STEP”按鈕去釋放進(jìn)程。然后，你可以按單一鍵去查看詳細(xì)的操作或者再次點擊“運行”返回高速模式。拖拽按鈕有時當(dāng)排序系統(tǒng)全速運行時電腦同時去執(zhí)行其他任務(wù)，這就導(dǎo)致一部分?jǐn)?shù)據(jù)不被移動。如果這種情況發(fā)生你可以點擊“DRAW”鍵去刷新所有的數(shù)據(jù)。使用它會讓程序暫停運轉(zhuǎn)，若要繼續(xù)運轉(zhuǎn)只需單擊“RUN”鍵。在程序運行過程中，你可以隨時去按“DRAW”按鈕，就像處理一個微小的差錯一樣，對其它沒有影響。在冒泡排序中的JAVA代碼在JAVA的冒泡排序進(jìn)程中如表31所示的一個叫做ARRAYBUB的類在縮成了一個數(shù)列A它包含了一種DOUBLE變量，在一個更加細(xì)致、重要的的程序中，數(shù)據(jù)可能包含著對象。但為了簡便，我們只使用原始的形式（我們將看到對象如同在OBJECTSORTJAVA中排序，在本章最后章節(jié)）。同時，為了減小表的大小我們現(xiàn)在ARRYBUB類中不顯示FIND和DELETE路徑，盡管他們時這一類的正常部分。LISTING31THEBUBBLESORTJAVAPROGRAM/BUBBLESORTJAVA/DEMONSTRATESBUBBLESORT/TORUNTHISPROGRAMCJAVABUBBLESORTAPP/CLASSARRAYBUBPRIVATEDOUBLEA/REFTOARRAYAPRIVATEINTNELEMS/NUMBEROFDATAITEMS/PUBLICARRAYBUBINTMAX/CONSTRUCTORANEWDOUBLEMAX/CREATETHEARRAYNELEMS0/NOITEMSYET/PUBLICVOIDINSERTDOUBLEVALUE/PUTELEMENTINTOARRAYANELEMSVALUE/INSERTITNELEMS/INCREMENTSIZE/PUBLICVOIDDISPLAY/DISPLAYSARRAYCONTENTSFORINTJ0J1OUT/OUTERLOOPBACKWARDFORIN0INAIN1/OUTOFORDERSWAPIN,IN1/SWAPTHEM/ENDBUBBLESORT/PRIVATEVOIDSWAPINTONE,INTTWODOUBLETEMPAONEAONEATWOATWOTEMP/ENDCLASSARRAYBUB/CLASSBUBBLESORTAPPPUBLICSTATICVOIDMAINSTRINGARGSINTMAXSIZE100/ARRAYSIZEARRAYBUBARR/REFERENCETOARRAYARRNEWARRAYBUBMAXSIZE/CREATETHEARRAYARRINSERT77/INSERT10ITEMSARRINSERT99ARRINSERT44ARRINSERT55ARRINSERT22