数据结构chapter3 simple sorting课件

DataStructuresandAlgorithmswithJavaChapter3SimpleSortingSimpleSorting一旦建立了一个重要数据库后，就可能根据某些需要对数据进行不同方式的排序。

e.g.

姓名按照字母序学生按照年级/学号/成绩 顾客按照邮政编码 消费品价格国民生产总值对数据进行排序是数据检索的一个初始步骤

查找---直接查找vs二分查找（效率问题）排序---冒泡、选择、插入排序等存在效率问题本章学习重点掌握各种排序算法的原理及Java实现掌握冒泡、选择、插入排序算法的优缺点Overview①HowWouldYouDoIt?②BubbleSort③SelectionSort④InsertionSort⑤SortingObjects⑥ComparingtheSimpleSorts①HowWouldYouDoIt?Imaginethatyourkids-leaguebaseballteamislineduponthefield.Theregulationnineplayers,plusanextra,haveshownupforpractice.Youwanttoarrangetheplayersinorderofincreasingheight(withtheshortestplayerontheleft),fortheteampicture.在排序问题上，人比计算机灵活，可以同时看到所有队员，并且可以立刻找到最高的一个。而计算机程序不能让人这样通览所有数据，需要借助“比较”操作原理，在同一时间内对两个队员进行比较本章中的三个算法都包括如下两个步骤，这两步循环执行，直到全部数据有序为止：

1.Comparetwoitems. 2.Swaptwoitemsorcopyoneitem.②BubbleSort冒泡排序算法运行起来非常慢，但原理最简单遵循以下规则:1.Comparetwoplayers.2.Iftheoneontheleftistaller,swapthem.3.Moveonepositionright.4.Whenyoureachthefirstsortedplayer,startoverattheleftendoftheline.看一下applet程序算法演示每次比较两个数据(队员)的时候，只要遇到最高的球员就交换他的位置，直到最后他到达队列的最右边。冒泡排序，即在算法执行的时候，最大的数据项总是“冒泡”到数组的顶端。APPLETJavacodeforabubblesort算法思路：将最小的数据项放在数组的开头，最大的数据项放在结尾。外层循环的计数器out从数组的最后开始，即out等于nElems-1,每经过一次循环out减一。下标大于out的数据项已经排好序。变量out每完成一次内部循环就左移一位。内层for循环计数器in从数组最开始算起，即in=0，每完成一次内部循环体加一，当它等于out时，结束一次循环。内层for循环体中，数组下标为in和in+1的两个数据项进行比较，满足条件则交换数据项不变性在许多算法中，有些条件在算法执行过程中是不变的，这些条件被称为不变性invariants.InthebubbleSort.javaprogram,theinvariantisthatthedataitemstotherightofouteraresorted.Thisremainstruethroughouttherunningofthealgorithm.EFFICIENCYOFTHEBUBBLESORTtherewillbeaboutN2/2comparisonstherewillbeaboutN2/4swapsthebubblesortrunsinO(N2)time.Wheneveryouseenestedloopssuchasthoseinthebubblesortandtheothersortingalgorithmsinthischapter,youcansuspectthatanalgorithmrunsinO(N2)time.10个数据项：N个数据项：③SelectionSort选择排序改进了冒泡排序，将比较的交换次数从O(N2)减少到O(N).不幸的是，比较次数仍然为O(N2).

---TheselectionsortimprovesonthebubblesortbyreducingthenumberofswapsnecessaryfromO(N2)toO(N).Unfortunately,thenumberofcomparisonsremainsO(N2).ABriefDescription扫描所有队员，从中挑出最小者交换最小者与站在最左端的队员，即0号位置再次从1号开始扫描球队队列，还是寻找最矮的，然后和1交换。这个过程一直持续到所有队员都排定。APPLETJAVACODEFORSELECTIONSORT选择排序的基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

INVARIANT在selectSort.java程序中，下标小于或等于out位置的数据项总是有序的。EFFICIENCYOFTHESELECTIONSORTTheselectionsortperformsthesamenumberofcomparisonsasthebubblesort:N*(N–1)/2.ForlargevaluesofN,thecomparisontimeswilldominate,sowewouldhavetosaythattheselectionsortrunsinO(N2)time,justasthebubblesortdid.However,itisunquestionablyfasterbecausetherearesofewswaps.ForsmallervaluesofN,itmayinfactbeconsiderablyfaster,especiallyiftheswaptimesaremuchlargerthanthecomparisontimes.④InsertionSort在大多数情况下，插入排序是基本排序算法中最好的。虽然插入排序算法仍然需要O(N2)的时间.一般情况下，其效率比冒泡排序快一倍，比选择排序还要快一点。

---Inmostcasestheinsertionsortisthebestoftheelementarysortsdescribedinthischapter.ItstillexecutesinO(N2)time,butit’sabouttwiceasfastasthebubblesortandsomewhatfasterthantheselectionsortinnormalsituations.Abriefdescription假定：队列排好了一半(局部有序)在队伍中间有一个作为标记的队员，其左边所有元素按照顺序排列，右边元素等待插入到合适位置标记队员出列依次比较标记队员与有序队列中队员身高，如比标记队员高，则移动至空位，直至没有比当前标记队员高的。标记队员初始位置后移，循环执行，直至整个队列有序APPLETJAVACODEFORINSERTIONSORT算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].

INVARIANTSINTHEINSERTIONSORT

在每趟排序结束时，在将temp位置的项插入后，比outer变量下标小的数据项都是局部有序的。EFFICIENCYOFTHEINSERTIONSORTHowmanycomparisonsandcopiesdoesthisalgorithmrequire?在第一趟排序中，它最多比较一次，第二趟2次，依次类推，最后一趟N-1次。

复制的次数大致等于比较的次数。然而，依次复制与一次交换的时间消耗不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。Comparisons:bubblesort:N*(N–1)/2selectionsort:N*(N–1)/2平均只有全体数据项的一半进行比较补充说明：Inanycase,liketheothersortroutinesinthischapter,theinsertionsortrunsinO(N2)timeforrandomdata.Fordatathatisalreadysortedoralmostsorted,theinsertionsortdoesmuchbetter.InthiscasethealgorithmrunsinO(N)time.However,fordataarrangedin

inversesortedorder,everypossiblecomparisonandshiftiscarriedout,sotheinsertionsortrunsnofasterthanthebubblesort.⑤SortingObjects为简单起见，大家注意到，前面排序的例程，研究对象都是基本数据类型:long长整型，而非基本数据类型。但通常排序的例程更多地应用于对象。见课本Person对象排序实例p66稳定性有些时候，排序需要考虑数据项拥有相同关键字的情况。如，雇员数据按雇员的姓的字典序排序(以姓为关键字)，现在又想按邮政编码排序，并希望具有相同邮编的数据仍然按姓排序。这种情况下，则只需要算法对需要排序的数据及进行排序，让不需要排序的数据保持原来的顺序。某些算法满足这样的要求，它们就可以称之为稳定的算法。⑥ComparingtheSimpleSorts冒泡排序算法一般不太使用

---butit’spracticalonlyiftheamountofdataissmall.选择排序虽然把交换次数降到了最低，但比较的次数仍然很大。当数据量很小时，交换数据相对于比较数据更加耗时时，可以应用选择排序。

---Theselectionsortminimizesthenumberofswaps,butthenumberofcomparisonsisstillhigh.Itmight

beusefulwhentheamountofdataissmallandswappingdataitemsisverytime-consumingcomparedwithcomparingthem.大多数情况下，数据量小或基本有序时，插入排序最快。对于大的数据量排序，快速排序最快，第七章介绍。

---Theinsertionsortisthemostversatileofthethreeandisthebestbetinmostsituations,assumingtheamountofdataissmallorthedataisalmostsorted.Forlargeramountsofdata,quicksortisgenerallyconsideredthefastestapproach;时间和空间要求上的比较除了在速度方面比较排序算法外，另外还需要考虑算法实现过程中需要的内存空间有多大。本章三种算法都可以”就地”完成排序。即除了初始的数组外，几乎不需要其他内存空间。所有排序算法都需要一个额外的变量来暂存交换时的数据项。小结Thesortingalgorithmsinthischapterallassumeanarrayasadatastoragestructure.Sortinginvolvescomparingthekeysofdataitemsinthearrayandmovingtheitems(actuallyreferencestotheitems)arounduntilthey’reinsortedorder.AllthealgorithmsinthischapterexecuteinO(N2)time.Nevertheless,somecanbesubstantiallyfasterthanothers.Aninvariantisaconditionthatremainsunchangedwhileanalgorithmruns.Thebubblesortistheleastefficient,butthesimplestsort.TheinsertionsortisthemostcommonlyusedoftheO(N2)sortsdescribedinthischapter.Asortisstableiftheorderofelementswiththesamekeyisretained.Noneofthesortsinthischapterrequiremorethanasingletemporaryvariableinadditiontotheoriginalarray课堂练习1计算机排序算法与人类排序相比较，它的局限性是：A人类擅长发明新算法。B计算机只能处理数量固定的数据。C人类知道什么需要排序，而计算机不知道D计算机一次只能比较两件东西。2冒泡排序算法在哪两者之间交替进行：A比较和交换B移动和复制C移动和比较D复制和比较3选择排序中A最大的关键字聚集到左边(较小的下标)。B最小的关键字被重复的发现。C为了将每个数据项插入到正确排序的位置，很多数据项将被移动D有序的数据项聚集到右边。4插入排序中，文中描述的“被标记的队员”对应于insertSort.ava中的哪个变量AinBoutCtempDa[out]5.在插入排序中，“局部有序”是指：A一些数据项已经排好序了,但它们可能需要被移动。B大部分数据项已在它们最终排序的位置了，但仍有一些需要排序C只有一些数据项有序。D组内的数据项已经排好序，而组外面的数据项需要插入到组中来6．在插入排序中，一个数据项被插入到局部有序的组合后，它将A永远不会再移动。B永远不会向左边移动。C经常被移出这个组。D发现这组的数据项不断减少。7稳定性是指：A在排序中排除有次关键字的项。