數(shù)據(jù)結(jié)構(gòu)chapter3 simple sorting課件

DataStructuresandAlgorithmswithJavaChapter3SimpleSortingSimpleSorting一旦建立了一個(gè)重要數(shù)據(jù)庫(kù)后，就可能根據(jù)某些需要對(duì)數(shù)據(jù)進(jìn)行不同方式的排序。

e.g.

姓名按照字母序?qū)W生按照年級(jí)/學(xué)號(hào)/成績(jī) 顧客按照郵政編碼 消費(fèi)品價(jià)格國(guó)民生產(chǎn)總值對(duì)數(shù)據(jù)進(jìn)行排序是數(shù)據(jù)檢索的一個(gè)初始步驟

查找---直接查找vs二分查找（效率問(wèn)題）排序---冒泡、選擇、插入排序等存在效率問(wèn)題本章學(xué)習(xí)重點(diǎn)掌握各種排序算法的原理及Java實(shí)現(xiàn)掌握冒泡、選擇、插入排序算法的優(yōu)缺點(diǎn)Overview①HowWouldYouDoIt?②BubbleSort③SelectionSort④InsertionSort⑤SortingObjects⑥ComparingtheSimpleSorts①HowWouldYouDoIt?Imaginethatyourkids-leaguebaseballteamislineduponthefield.Theregulationnineplayers,plusanextra,haveshownupforpractice.Youwanttoarrangetheplayersinorderofincreasingheight(withtheshortestplayerontheleft),fortheteampicture.在排序問(wèn)題上，人比計(jì)算機(jī)靈活，可以同時(shí)看到所有隊(duì)員，并且可以立刻找到最高的一個(gè)。而計(jì)算機(jī)程序不能讓人這樣通覽所有數(shù)據(jù)，需要借助“比較”操作原理，在同一時(shí)間內(nèi)對(duì)兩個(gè)隊(duì)員進(jìn)行比較本章中的三個(gè)算法都包括如下兩個(gè)步驟，這兩步循環(huán)執(zhí)行，直到全部數(shù)據(jù)有序?yàn)橹梗?/p>

1.Comparetwoitems. 2.Swaptwoitemsorcopyoneitem.②BubbleSort冒泡排序算法運(yùn)行起來(lái)非常慢，但原理最簡(jiǎn)單遵循以下規(guī)則:1.Comparetwoplayers.2.Iftheoneontheleftistaller,swapthem.3.Moveonepositionright.4.Whenyoureachthefirstsortedplayer,startoverattheleftendoftheline.看一下applet程序算法演示每次比較兩個(gè)數(shù)據(jù)(隊(duì)員)的時(shí)候，只要遇到最高的球員就交換他的位置，直到最后他到達(dá)隊(duì)列的最右邊。冒泡排序，即在算法執(zhí)行的時(shí)候，最大的數(shù)據(jù)項(xiàng)總是“冒泡”到數(shù)組的頂端。APPLETJavacodeforabubblesort算法思路：將最小的數(shù)據(jù)項(xiàng)放在數(shù)組的開(kāi)頭，最大的數(shù)據(jù)項(xiàng)放在結(jié)尾。外層循環(huán)的計(jì)數(shù)器out從數(shù)組的最后開(kāi)始，即out等于nElems-1,每經(jīng)過(guò)一次循環(huán)out減一。下標(biāo)大于out的數(shù)據(jù)項(xiàng)已經(jīng)排好序。變量out每完成一次內(nèi)部循環(huán)就左移一位。內(nèi)層for循環(huán)計(jì)數(shù)器in從數(shù)組最開(kāi)始算起，即in=0，每完成一次內(nèi)部循環(huán)體加一，當(dāng)它等于out時(shí)，結(jié)束一次循環(huán)。內(nèi)層for循環(huán)體中，數(shù)組下標(biāo)為in和in+1的兩個(gè)數(shù)據(jù)項(xiàng)進(jìn)行比較，滿足條件則交換數(shù)據(jù)項(xiàng)不變性在許多算法中，有些條件在算法執(zhí)行過(guò)程中是不變的，這些條件被稱為不變性invariants.InthebubbleSort.javaprogram,theinvariantisthatthedataitemstotherightofouteraresorted.Thisremainstruethroughouttherunningofthealgorithm.EFFICIENCYOFTHEBUBBLESORTtherewillbeaboutN2/2comparisonstherewillbeaboutN2/4swapsthebubblesortrunsinO(N2)time.Wheneveryouseenestedloopssuchasthoseinthebubblesortandtheothersortingalgorithmsinthischapter,youcansuspectthatanalgorithmrunsinO(N2)time.10個(gè)數(shù)據(jù)項(xiàng)：N個(gè)數(shù)據(jù)項(xiàng)：③SelectionSort選擇排序改進(jìn)了冒泡排序，將比較的交換次數(shù)從O(N2)減少到O(N).不幸的是，比較次數(shù)仍然為O(N2).

---TheselectionsortimprovesonthebubblesortbyreducingthenumberofswapsnecessaryfromO(N2)toO(N).Unfortunately,thenumberofcomparisonsremainsO(N2).ABriefDescription掃描所有隊(duì)員，從中挑出最小者交換最小者與站在最左端的隊(duì)員，即0號(hào)位置再次從1號(hào)開(kāi)始掃描球隊(duì)隊(duì)列，還是尋找最矮的，然后和1交換。這個(gè)過(guò)程一直持續(xù)到所有隊(duì)員都排定。APPLETJAVACODEFORSELECTIONSORT選擇排序的基本思想

n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果：

①初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空。

②第1趟排序

在無(wú)序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。

……

③第i趟排序

第i趟排序開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[i]交換，使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。

這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。

INVARIANT在selectSort.java程序中，下標(biāo)小于或等于out位置的數(shù)據(jù)項(xiàng)總是有序的。EFFICIENCYOFTHESELECTIONSORTTheselectionsortperformsthesamenumberofcomparisonsasthebubblesort:N*(N–1)/2.ForlargevaluesofN,thecomparisontimeswilldominate,sowewouldhavetosaythattheselectionsortrunsinO(N2)time,justasthebubblesortdid.However,itisunquestionablyfasterbecausetherearesofewswaps.ForsmallervaluesofN,itmayinfactbeconsiderablyfaster,especiallyiftheswaptimesaremuchlargerthanthecomparisontimes.④InsertionSort在大多數(shù)情況下，插入排序是基本排序算法中最好的。雖然插入排序算法仍然需要O(N2)的時(shí)間.一般情況下，其效率比冒泡排序快一倍，比選擇排序還要快一點(diǎn)。

---Inmostcasestheinsertionsortisthebestoftheelementarysortsdescribedinthischapter.ItstillexecutesinO(N2)time,butit’sabouttwiceasfastasthebubblesortandsomewhatfasterthantheselectionsortinnormalsituations.Abriefdescription假定：隊(duì)列排好了一半(局部有序)在隊(duì)伍中間有一個(gè)作為標(biāo)記的隊(duì)員，其左邊所有元素按照順序排列，右邊元素等待插入到合適位置標(biāo)記隊(duì)員出列依次比較標(biāo)記隊(duì)員與有序隊(duì)列中隊(duì)員身高，如比標(biāo)記隊(duì)員高，則移動(dòng)至空位，直至沒(méi)有比當(dāng)前標(biāo)記隊(duì)員高的。標(biāo)記隊(duì)員初始位置后移，循環(huán)執(zhí)行，直至整個(gè)隊(duì)列有序APPLETJAVACODEFORINSERTIONSORT算法思想：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含有n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表，重復(fù)n-1次可完成排序過(guò)程。

把a(bǔ)[i]插入到a[0]，a[1]，...,a[i-1]之中的具體實(shí)施過(guò)程為:先把a(bǔ)[i]賦值給變量t,然后將t依次與a[i-1],a[i-2],...進(jìn)行比較,將比t大的元素右移一個(gè)位置,直到發(fā)現(xiàn)某個(gè)j(0<=j<=i-1),使得a[j]<=t或j為(-1),把t賦值給a[j+1].

INVARIANTSINTHEINSERTIONSORT

在每趟排序結(jié)束時(shí)，在將temp位置的項(xiàng)插入后，比outer變量下標(biāo)小的數(shù)據(jù)項(xiàng)都是局部有序的。EFFICIENCYOFTHEINSERTIONSORTHowmanycomparisonsandcopiesdoesthisalgorithmrequire?在第一趟排序中，它最多比較一次，第二趟2次，依次類推，最后一趟N-1次。

復(fù)制的次數(shù)大致等于比較的次數(shù)。然而，依次復(fù)制與一次交換的時(shí)間消耗不同，所以相對(duì)于隨機(jī)數(shù)據(jù)，這個(gè)算法比冒泡排序快一倍，比選擇排序略快。Comparisons:bubblesort:N*(N–1)/2selectionsort:N*(N–1)/2平均只有全體數(shù)據(jù)項(xiàng)的一半進(jìn)行比較補(bǔ)充說(shuō)明：Inanycase,liketheothersortroutinesinthischapter,theinsertionsortrunsinO(N2)timeforrandomdata.Fordatathatisalreadysortedoralmostsorted,theinsertionsortdoesmuchbetter.InthiscasethealgorithmrunsinO(N)time.However,fordataarrangedin

inversesortedorder,everypossiblecomparisonandshiftiscarriedout,sotheinsertionsortrunsnofasterthanthebubblesort.⑤SortingObjects為簡(jiǎn)單起見(jiàn)，大家注意到，前面排序的例程，研究對(duì)象都是基本數(shù)據(jù)類型:long長(zhǎng)整型，而非基本數(shù)據(jù)類型。但通常排序的例程更多地應(yīng)用于對(duì)象。見(jiàn)課本Person對(duì)象排序?qū)嵗齪66穩(wěn)定性有些時(shí)候，排序需要考慮數(shù)據(jù)項(xiàng)擁有相同關(guān)鍵字的情況。如，雇員數(shù)據(jù)按雇員的姓的字典序排序(以姓為關(guān)鍵字)，現(xiàn)在又想按郵政編碼排序，并希望具有相同郵編的數(shù)據(jù)仍然按姓排序。這種情況下，則只需要算法對(duì)需要排序的數(shù)據(jù)及進(jìn)行排序，讓不需要排序的數(shù)據(jù)保持原來(lái)的順序。某些算法滿足這樣的要求，它們就可以稱之為穩(wěn)定的算法。⑥ComparingtheSimpleSorts冒泡排序算法一般不太使用

---butit’spracticalonlyiftheamountofdataissmall.選擇排序雖然把交換次數(shù)降到了最低，但比較的次數(shù)仍然很大。當(dāng)數(shù)據(jù)量很小時(shí)，交換數(shù)據(jù)相對(duì)于比較數(shù)據(jù)更加耗時(shí)時(shí)，可以應(yīng)用選擇排序。

---Theselectionsortminimizesthenumberofswaps,butthenumberofcomparisonsisstillhigh.Itmight

beusefulwhentheamountofdataissmallandswappingdataitemsisverytime-consumingcomparedwithcomparingthem.大多數(shù)情況下，數(shù)據(jù)量小或基本有序時(shí)，插入排序最快。對(duì)于大的數(shù)據(jù)量排序，快速排序最快，第七章介紹。

---Theinsertionsortisthemostversatileofthethreeandisthebestbetinmostsituations,assumingtheamountofdataissmallorthedataisalmostsorted.Forlargeramountsofdata,quicksortisgenerallyconsideredthefastestapproach;時(shí)間和空間要求上的比較除了在速度方面比較排序算法外，另外還需要考慮算法實(shí)現(xiàn)過(guò)程中需要的內(nèi)存空間有多大。本章三種算法都可以”就地”完成排序。即除了初始的數(shù)組外，幾乎不需要其他內(nèi)存空間。所有排序算法都需要一個(gè)額外的變量來(lái)暫存交換時(shí)的數(shù)據(jù)項(xiàng)。小結(jié)Thesortingalgorithmsinthischapterallassumeanarrayasadatastoragestructure.Sortinginvolvescomparingthekeysofdataitemsinthearrayandmovingtheitems(actuallyreferencestotheitems)arounduntilthey’reinsortedorder.AllthealgorithmsinthischapterexecuteinO(N2)time.Nevertheless,somecanbesubstantiallyfasterthanothers.Aninvariantisaconditionthatremainsunchangedwhileanalgorithmruns.Thebubblesortistheleastefficient,butthesimplestsort.TheinsertionsortisthemostcommonlyusedoftheO(N2)sortsdescribedinthischapter.Asortisstableiftheorderofelementswiththesamekeyisretained.Noneofthesortsinthischapterrequiremorethanasingletemporaryvariableinadditiontotheoriginalarray課堂練習(xí)1計(jì)算機(jī)排序算法與人類排序相比較，它的局限性是：A人類擅長(zhǎng)發(fā)明新算法。B計(jì)算機(jī)只能處理數(shù)量固定的數(shù)據(jù)。C人類知道什么需要排序，而計(jì)算機(jī)不知道D計(jì)算機(jī)一次只能比較兩件東西。2冒泡排序算法在哪兩者之間交替進(jìn)行：A比較和交換B移動(dòng)和復(fù)制C移動(dòng)和比較D復(fù)制和比較3選擇排序中A最大的關(guān)鍵字聚集到左邊(較小的下標(biāo))。B最小的關(guān)鍵字被重復(fù)的發(fā)現(xiàn)。C為了將每個(gè)數(shù)據(jù)項(xiàng)插入到正確排序的位置，很多數(shù)據(jù)項(xiàng)將被移動(dòng)D有序的數(shù)據(jù)項(xiàng)聚集到右邊。4插入排序中，文中描述的“被標(biāo)記的隊(duì)員”對(duì)應(yīng)于insertSort.ava中的哪個(gè)變量AinBoutCtempDa[out]5.在插入排序中，“局部有序”是指：A一些數(shù)據(jù)項(xiàng)已經(jīng)排好序了,但它們可能需要被移動(dòng)。B大部分?jǐn)?shù)據(jù)項(xiàng)已在它們最終排序的位置了，但仍有一些需要排序C只有一些數(shù)據(jù)項(xiàng)有序。D組內(nèi)的數(shù)據(jù)項(xiàng)已經(jīng)排好序，而組外面的數(shù)據(jù)項(xiàng)需要插入到組中來(lái)6．在插入排序中，一個(gè)數(shù)據(jù)項(xiàng)被插入到局部有序的組合后，它將A永遠(yuǎn)不會(huì)再移動(dòng)。B永遠(yuǎn)不會(huì)向左邊移動(dòng)。C經(jīng)常被移出這個(gè)組。D發(fā)現(xiàn)這組的數(shù)據(jù)項(xiàng)不斷減少。7穩(wěn)定性是指：A在排序中排除有次關(guān)鍵字的項(xiàng)。