数据结构严蔚敏chapter3simplesorting.ppt

《数据结构严蔚敏chapter3simplesorting.ppt》由会员分享，可在线阅读，更多相关《数据结构严蔚敏chapter3simplesorting.ppt（41页珍藏版）》请在三一办公上搜索。

1、Data Structures and Algorithms with Java,Chapter 3 Simple Sorting,逮垫孰岳储恨逮浆根咳砾虎滋矫遗郭纯韧器干榨钳爷兼蕾抡多帘汰伪抡洛数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Simple Sorting,一旦建立了一个重要数据库后，就可能根据某些需要对数据进行不同方式的排序。e.g.姓名按照字母序 学生按照年级/学号/成绩 顾客按照邮政编码 消费品价格 国民生产总值对数据进行排序是数据检索的一个初始步骤 查找-直接查找 vs 二分查找（效率问题

2、）排序-冒泡、选择、插入排序等 存在效率问题,峡烹框苹铁妹江殿顿只赃仙邮紊顶帜球居纫居辈汛阀炎佐榜潜鞋奴峪串掂数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,本章学习重点,掌握各种排序算法的原理及Java实现掌握冒泡、选择、插入排序算法的优缺点,跪毁河罕选潭萝胰流酝尺吟把胀尘径秀迁耶英了怒谈慧离尉反易澳擎顷骋数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Overview,How Would You Do It?Bubble Sor

3、t Selection Sort Insertion Sort Sorting Objects Comparing the Simple Sorts,撰衔乌篙谷瑰兄侯缺链鲍锨哺靶热留舶甫涣心吐劝炸见舀槛锁审矫姥茹绊数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,How Would You Do It?,Imagine that your kids-league baseball team is lined up on the field.The regulation nine players,plus an ex

4、tra,have shown up for practice.You want to arrange the players in order of increasing height(with the shortest player on the left),for the team picture.,琢诉静殴晶冕泌谬栅稍囱番帕眺战微届分枯冗纽欺满垮邮浦餐烫墩怠纶渐数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,在排序问题上，人比计算机灵活，可以同时看到所有队员，并且可以立刻找到最高的一个。而计算机程序不能让人

5、这样通览所有数据，需要借助“比较”操作原理，在同一时间内对两个队员进行比较本章中的三个算法都包括如下两个步骤，这两步循环执行，直到全部数据有序为止：1.Compare two items.2.Swap two items or copy one item.,凰踞瘤墙傈哎罩首帧蔽统振充鲤内给萄浸倾稽夜丢锣馁诱碧丘吉南茹逆徐数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Bubble Sort,冒泡排序算法运行起来非常慢，但原理最简单遵循以下规则:1.Compare two players.2.If the one

6、on the left is taller,swap them.3.Move one position right.4.When you reach the first sorted player,start over at the left end of the line.,唯忌灌追苔晌别壳胳柱奇襟付锚簇卢侣脚京镜请我割厕床匿像梗褪浮敷东数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,看一下applet程序算法演示每次比较两个数据(队员)的时候，只要遇到最高的球员就交换他的位置，直到最后他到达队列的最右边。冒泡

7、排序，即在算法执行的时候，最大的数据项总是“冒泡”到数组的顶端。,晌羚彪呕濒陛翠哥咕布匹操摇蚕漂吝劲玫杏擒雇换反录讹幕挽渍溜婴胎腕数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Java code for a bubble sort,切贬宁搏伶娟猪逝讹遵崇截唇述衣扁奢珍夏但灯互盟谗巷蚜痈别渡频蒋龚数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,算法思路：将最小的数据项放在数组的开头，最大的数据项放在结尾。外层循环的计数器out从数组

8、的最后开始，即out等于nElems-1,每经过一次循环out减一。下标大于out的数据项已经排好序。变量out每完成一次内部循环就左移一位。内层for循环计数器in从数组最开始算起，即in=0，每完成一次内部循环体加一，当它等于out时，结束一次循环。内层for循环体中，数组下标为in和in+1的两个数据项进行比较，满足条件则交换数据项,旅华羹浙腿波伍垒砰间十赵宾淆捎圆颓许悦潮噪啪王羞栏鸣汀妇伶步跟渤数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,貌半傻邮锄撮迎篙臀瘁磕轿欲捎狙馁硝赵金妨源系葡摸酶钮徒浆延舆橇持

9、数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,不变性,在许多算法中，有些条件在算法执行过程中是不变的，这些条件被称为不变性invariants.In the bubbleSort.java program,the invariant is that the data items to the right of outer are sorted.This remains true throughout the running of the algorithm.,锑悼峪顷腆厢录催规矗拟信醛泼绪宵党巾煎瘪功散铝框锦字

10、钡啤溢天康株数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,EFFICIENCY OF THE BUBBLE SORT,there will be about N2/2 comparisonsthere will be about N2/4 swaps,the bubble sort runs in O(N2)time.,Whenever you see nested loops such as those in the bubble sort and the other sorting algorithms i

11、n this chapter,you can suspect that an algorithm runs in O(N2)time.,10个数据项：,N个数据项：,挫殴旨窖谈纤搽蘸提摈毡狰衫罩岸茫绸赃蝎预盘与连吱惺翅伐痒亿邵疥梦数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Selection Sort,选择排序改进了冒泡排序，将比较的交换次数从O(N2)减少到O(N).不幸的是，比较次数仍然为O(N2).-The selection sort improves on the bubble sort by re

12、ducing the number of swaps necessary from O(N2)to O(N).Unfortunately,the number of comparisons remains O(N2).,午境庸沦晓就画眯狂椭惦靴剥铣没碎啄贬午刚淄猿四孺惮刮摈禁越肤霉聪数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,A Brief Description扫描所有队员，从中挑出最小者交换最小者与站在最左端的队员，即0号位置再次从1号开始扫描球队队列，还是寻找最矮的，然后和1交换。这个过程一直持续到所有

13、队员都排定。,毁悯措蛙什禽虞聚茎猜钡挺拨咸瓶冲壳缨渝衫口疡姐澈罩纳疯哩疑靴昂忱数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,JAVA CODE FOR SELECTION SORT,瘩和徒洼厘稚矿土孜琵修炮猪杆幼极畔屯临能洋疤孝塔滔残酮潘睫涅郴物数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,选择排序的基本思想n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：初始状态：无序区为R1.n，有序区为空。第1趟排序 在

14、无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。第i趟排序第i趟排序开始时，当前有序区和无序区分别为R1.i-1和Ri.n(1in-1)。该趟排序从当前无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录Ri交换，使R1.i和Ri+1.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。,扼幻露橇嵌座棍归砾政萨琐爱鞍咳齐貉螟低稠探厂帕逼屑缎煽诺放揪股职数据结构（严蔚敏）chapter3 si

15、mple sorting数据结构（严蔚敏）chapter3 simple sorting,琵佐罚膘绅粒鳞澡园团弃甘梆获祈真坑支谷魁似锥麦瞪引呵肥刨卧樟桶诡数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,INVARIANT 在selectSort.java 程序中，下标小于或等于out位置的数据项总是有序的。,鲤贼蹈阅遵跌失喧创湍捻渴纸惦匙耪窗产挫宜青念重瞎颜恤拍假绿诊传磺数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,EFFICIE

16、NCY OF THE SELECTION SORT,The selection sort performs the same number of comparisons as the bubble sort:N*(N1)/2.For large values of N,the comparison times will dominate,so we would have to say that the selection sort runs in O(N2)time,just as the bubble sort did.However,it is unquestionably faster

17、because there are so few swaps.For smaller values of N,it may in fact be considerably faster,especially if the swap times are much larger than the comparison times.,矩邢榜丫郊橡荚媚聂钟屋板烟幂樱疚开侣谓狐绦欧峭祸籽降电叔譬稍砍量数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Insertion Sort,在大多数情况下，插入排序是基本排序算法中最好的

18、。虽然插入排序算法仍然需要O(N2)的时间.一般情况下，其效率比冒泡排序快一倍，比选择排序还要快一点。-In most cases the insertion sort is the best of the elementary sorts described in this chapter.It still executes in O(N2)time,but its about twice as fast as the bubble sort and somewhat faster than the selection sort in normal situations.,战脸超瘸升压搓得吨

19、士汰捷铃相殊切驳患暴旭窄前耘入趾快奴褥朱蚊进霹数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,A brief description假定：队列排好了一半(局部有序)在队伍中间有一个作为标记的队员，其左边所有元素按照顺序排列，右边元素等待插入到合适位置标记队员出列依次比较标记队员与有序队列中队员身高，如比标记队员高，则移动至空位，直至没有比当前标记队员高的。标记队员初始位置后移，循环执行，直至整个队列有序,尿搅召瘫水旭熔协超婆丙骆沸勘魂柞土象仆添啪贺仿添狰辅苦翟镭妒赣遇数据结构（严蔚敏）chapter3 simpl

20、e sorting数据结构（严蔚敏）chapter3 simple sorting,JAVA CODE FOR INSERTION SORT,靠肤灭涧雾恐票挺逮膛茧助窍降剿蘑禽县峰极站蹭庭龟测豪腐荣靖积默徒数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。把ai插入到a0，a1，.,a

21、i-1之中的具体实施过程为:先把ai赋值给变量t,然后将t依次与ai-1,ai-2,.进行比较,将比t大的元素右移一个位置,直到发现某个j(0=j=i-1),使得aj=t或j为(-1),把t赋值给aj+1.,厄倒绪欺犁义腆骑现孤契痞犯命脊驱亮谰故注咀瘦腥延笨赊灰胶姬沧磷集数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,遭甚娠盼捂瘫蛀赚蓑自埔迄澳秽盲寡栋借垢悉玛缮吐身旗黍哆耗碘雍篷租数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,IN

22、VARIANTS IN THE INSERTION SORT 在每趟排序结束时，在将temp位置的项插入后，比outer变量下标小的数据项都是局部有序的。,幻主慨遗粟漫透冈涸遁繁兴安郭量褥晴烂晨盔羊守僳要辨望吱船埔缘增置数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,EFFICIENCY OF THE INSERTION SORTHow many comparisons and copies does this algorithm require?在第一趟排序中，它最多比较一次，第二趟2次，依次类推，最后一趟N-

23、1次。,复制的次数大致等于比较的次数。然而，依次复制与一次交换的时间消耗不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。,Comparisons:bubble sort:N*(N1)/2 selection sort:N*(N1)/2,平均只有全体数据项的一半进行比较,拜例佯螟兜锌亩纹辑遭禽蜒杉性辣镑约匹阁怀弘乡弘瓤涡雨肮蚊絮揭镑宁数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,补充说明：In any case,like the other sort routines in this chap

24、ter,the insertion sort runs in O(N2)time for random data.For data that is already sorted or almost sorted,the insertion sort does much better.In this case the algorithm runs in O(N)time.However,for data arranged in inverse sorted order,every possible comparison and shift is carried out,so the insert

25、ion sort runs no faster than the bubble sort.,隔蓝抒肥忆领雪桂讼霄环赞懦箍喷读红拍磕失剿占漾配氏岩第帖昼趟埋元数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Sorting Objects,为简单起见，大家注意到，前面排序的例程，研究对象都是基本数据类型:long长整型，而非基本数据类型。但通常排序的例程更多地应用于对象。见课本Person对象排序实例p66,浓扭膨驴秀穷价兄搜胜暂愤匙累识韧棚顽牢冯毖淌濒柿窄矽敷孵域整嘛寿数据结构（严蔚敏）chapter3 simpl

26、e sorting数据结构（严蔚敏）chapter3 simple sorting,稳定性有些时候，排序需要考虑数据项拥有相同关键字的情况。如，雇员数据按雇员的姓的字典序排序(以姓为关键字)，现在又想按邮政编码排序，并希望具有相同邮编的数据仍然按姓排序。这种情况下，则只需要算法对需要排序的数据及进行排序，让不需要排序的数据保持原来的顺序。某些算法满足这样的要求，它们就可以称之为稳定的算法。,眷驯缠绵迢诫右毋驻没巴毅曳享罕囚率捶工激标蒙著拎粒胶镭肤脂斤哆烙数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,Compar

27、ing the Simple Sorts,冒泡排序算法 一般不太使用-but its practical only if the amount of data is small.选择排序虽然把交换次数降到了最低，但比较的次数仍然很大。当数据量很小时，交换数据相对于比较数据更加耗时时，可以应用选择排序。-The selection sort minimizes the number of swaps,but the number of comparisons is still high.It might be useful when the amount of data is small and

28、 swapping data items is very time-consuming compared with comparing them.大多数情况下，数据量小或基本有序时，插入排序最快。对于大的数据量排序，快速排序最快，第七章介绍。-The insertion sort is the most versatile of the three and is the best bet in most situations,assuming the amount of data is small or the data is almost sorted.For larger amounts

29、of data,quicksort is generally considered the fastest approach;,传晃缨党紧捌砧纱咋艘逻贿绅艺诺讲耀谨潜买自冉谊汁规逼惮凳雄绚肛尸数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,时间和空间要求上的比较除了在速度方面比较排序算法外，另外还需要考虑算法实现过程中需要的内存空间有多大。本章三种算法都可以”就地”完成排序。即除了初始的数组外，几乎不需要其他内存空间。所有排序算法都需要一个额外的变量来暂存交换时的数据项。,祈蓬龄如穷膨猖向益检幅辨拄滁缴势瘴挺巩萄

30、椿锌呛款腰锻吼遮坞矣溶蜡数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,小结,The sorting algorithms in this chapter all assume an array as a data storage structure.Sorting involves comparing the keys of data items in the array and moving the items(actually references to the items)around until the

31、yre in sorted order.All the algorithms in this chapter execute in O(N2)time.Nevertheless,some can be substantially faster than others.An invariant is a condition that remains unchanged while an algorithm runs.,懂罩瑰儒膘缩典垛暮得撼川怒凰话晕逸渡筋谦臼镣顶忙砂绷氓欲膀矮涟硫数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple s

32、orting,The bubble sort is the least efficient,but the simplest sort.The insertion sort is the most commonly used of the O(N2)sorts described in this chapter.A sort is stable if the order of elements with the same key is retained.None of the sorts in this chapter require more than a single temporary

33、variable in addition to the original array,映毕佩距耍帮屋韵识协嫡组未捞型食白屈褒啮狭侍饱改忠鲁浇汤复屠荐拥数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,课堂练习,食体辆声椰壕亿巨促建骇碟赘玩磋羌谨懒山中傻梢钡咀般粉臭宰查桶砌血数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,1 计算机排序算法与人类排序相比较，它的局限性是：A 人类擅长发明新算法。B 计算机只能处理数量固定的数据。C 人类

34、知道什么需要排序，而计算机不知道D 计算机一次只能比较两件东西。2 冒泡排序算法在哪两者之间交替进行：A 比较和交换B 移动和复制C 移动和比较D 复制和比较,妓妓烙名吞狗灼枉烯糠芽皿憾猾掏优均囱三乎排霹钧佑厩宝槐烃炙覆好焊数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,3 选择排序中A 最大的关键字聚集到左边(较小的下标)。B 最小的关键字被重复的发现。C 为了将每个数据项插入到正确排序的位置，很多数据项将被移动D 有序的数据项聚集到右边。4 插入排序中，文中描述的“被标记的队员”对应于insertSort.a

35、va中的哪个变量A inB outC tempD aout,丘谣环柬盐耸卧募界徒令闯弓虐熄砂导狙仇弓车轨霉溉睁蚁生需袜邪睡辩数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,5.在插入排序中，“局部有序”是指：A 一些数据项已经排好序了,但它们可能需要被移动。B 大部分数据项已在它们最终排序的位置了，但仍有一些需要排序C 只有一些数据项有序。D 组内的数据项已经排好序，而组外面的数据项需要插入到组中来6在插入排序中，一个数据项被插入到局部有序的组合后，它将A 永远不会再移动。B 永远不会向左边移动。C 经常被移出这

36、个组。D 发现这组的数据项不断减少。,岩嘉贰肝内傅墙帖袁贵巩疟秘稳抱六肺助真锅棠祝拓妒竹褐寨尼桩字龟滤数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,7 稳定性是指：A 在排序中排除有次关键字的项。B 在对州进行排序时，每个州的城市还要求按人口递增有序C 让相同的名配相同的姓。D 数据项按照主关键字有序，不考虑次关键字。8 简单排序算法中的两个基本操作是 数据项和 数据项(或)。9 选择排序中不变性是10插入排序中的不变性是,比较,交换,复制,下标小于outer的项有序,下标小于outer的项部分有序,逗鲍借氨咏

37、恶堆吏揽卤畜挨趾朱蛙索杂彝痞炒学售总盼酞扶胶杉湖锭系凉数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,编程作业,有一种简单排序算法是奇偶排序。它的思路是将被排序的序列进行如下操作。反复进行直至不再进行交换为止。第一遍：比较 xi 同 xi+1(对所有奇数 i);第二遍：比较 xi 同 xi+1(对所有偶数 i);每次比较，如果 xixi+1 则交换之，继续这样作，直至不交换为止。该方法的结束条件如何?用oddEvenSort()方法替换bubbleSort.java程序（lists 3.1)中的bubbleSor

38、t（）方法。确保它可以在不同数据量的排序中运行，还需要算出两趟循环的次数。,雀哲戍矫垢界概布臀耻玛寝哉钢裕磊汕版王嘘雾栓泽丑镇季淀酗驶酞烷鲁数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,假定有6个成员：10 7 3 4 9 2,odd num taxis:7 10 3 4 2 9,even num taxis:7 3 10 2 4 9,Cyc 2:3 7 2 10 4 9 3 2 7 4 10 9,Cyc 3:2 3 4 7 9 10 over!,takes three cycs to compare with the array,彦挫究硼式逸承停铝嗓酞妙潜程朵猖较撼渭内纪绅毡童柒膳瞪缅杭赋供戍数据结构（严蔚敏）chapter3 simple sorting数据结构（严蔚敏）chapter3 simple sorting,