《数据结构严蔚敏chapter3simplesorting》由会员分享，可在线阅读，更多相关《数据结构严蔚敏chapter3simplesorting（41页珍藏版）》请在金锄头文库上搜索。
1、Data Structures and Algorithms Data Structures and Algorithms with Javawith JavaChapter 3 Simple SortingChapter 3 Simple Sorting逮垫孰岳储恨逮浆根咳砾虎滋矫遗郭纯韧器干榨钳爷兼蕾抡多帘汰伪抡洛数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingSimple SortingSimple Sortingn n一旦建立了一个重要数据库后，就可能根据某些需一旦建立了一个重要数据库后，就可能根据某些需一旦建立了
2、一个重要数据库后，就可能根据某些需一旦建立了一个重要数据库后，就可能根据某些需要对数据进行不同方式的排序。要对数据进行不同方式的排序。要对数据进行不同方式的排序。要对数据进行不同方式的排序。 e.g. 姓名按照字母序 学生按照年级/学号/成绩 顾客按照邮政编码 消费品价格 国民生产总值n n对数据进行排序是数据检索的一个初始步骤对数据进行排序是数据检索的一个初始步骤对数据进行排序是数据检索的一个初始步骤对数据进行排序是数据检索的一个初始步骤 查找查找查找查找 - - - - 直接查找直接查找直接查找直接查找 vs vs vs vs 二分查找（效率问题）二分查找（效率问题）二分查找（效率问题）二
3、分查找（效率问题） 排序排序排序排序 - - - - 冒泡、选择、插入排序等冒泡、选择、插入排序等冒泡、选择、插入排序等冒泡、选择、插入排序等 存在效率问题存在效率问题存在效率问题存在效率问题峡烹框苹铁妹江殿顿只赃仙邮紊顶帜球居纫居辈汛阀炎佐榜潜鞋奴峪串掂数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting本章学习重点本章学习重点n n掌握各种排序算法的原理及掌握各种排序算法的原理及JavaJava实现实现n n掌握冒泡、选择、插入排序算法的优掌握冒泡、选择、插入排序算法的优缺点缺点跪毁河罕选潭萝胰流酝尺吟把胀尘径秀迁耶英了怒
4、谈慧离尉反易澳擎顷骋数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingOverviewOverview How Would You Do It? How Would You Do It? Bubble Sort Bubble Sort Selection Sort Selection Sort Insertion Sort Insertion Sort Sorting Objects Sorting Objects Comparing the Simple Sorts Comparing the Simple Sorts撰衔
5、乌篙谷瑰兄侯缺链鲍锨哺靶热留舶甫涣心吐劝炸见舀槛锁审矫姥茹绊数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting How Would You Do It? How Would You Do It?nImagine that your kids-league baseball team is lined up on the field. The regulation nine players, plus an extra, have shown up for practice. You want to arrange the p
6、layers in order of increasing height (with the shortest player on the left), for the team picture.琢诉静殴晶冕泌谬栅稍囱番帕眺战微届分枯冗纽欺满垮邮浦餐烫墩怠纶渐数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting在排序问题上，人比计算机灵活，可以同时看到所有队在排序问题上，人比计算机灵活，可以同时看到所有队在排序问题上，人比计算机灵活，可以同时看到所有队在排序问题上，人比计算机灵活，可以同时看到所有队员，并且可以立刻找到最高的一
7、个。员，并且可以立刻找到最高的一个。员，并且可以立刻找到最高的一个。员，并且可以立刻找到最高的一个。而计算机程序不能让人这样通览所有数据，需要借助而计算机程序不能让人这样通览所有数据，需要借助而计算机程序不能让人这样通览所有数据，需要借助而计算机程序不能让人这样通览所有数据，需要借助 “比较比较比较比较”操作原理，在同一时间内对两个队员进行比操作原理，在同一时间内对两个队员进行比操作原理，在同一时间内对两个队员进行比操作原理，在同一时间内对两个队员进行比较较较较本章中的三个算法都包括如下两个步骤，这两步循环执本章中的三个算法都包括如下两个步骤，这两步循环执本章中的三个算法都包括如下两个步骤，这
8、两步循环执本章中的三个算法都包括如下两个步骤，这两步循环执行，直到全部数据有序为止：行，直到全部数据有序为止：行，直到全部数据有序为止：行，直到全部数据有序为止：1. Compare two items.1. Compare two items.1. Compare two items.1. Compare two items.2. Swap two items or copy one item.2. Swap two items or copy one item.2. Swap two items or copy one item.2. Swap two items or copy one
9、item.凰踞瘤墙傈哎罩首帧蔽统振充鲤内给萄浸倾稽夜丢锣馁诱碧丘吉南茹逆徐数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting Bubble Sort Bubble Sortn n冒泡排序算法运行起来冒泡排序算法运行起来非常慢，但原理最简单非常慢，但原理最简单遵循以下规则遵循以下规则: :1. 1. Compare two players.2. 2. If the one on the left is taller, swap them.3. 3. Move one position right.4. 4. When you
10、reach the first sorted player, start over at the left end of the line.唯忌灌追苔晌别壳胳柱奇襟付锚簇卢侣脚京镜请我割厕床匿像梗褪浮敷东数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting看一下applet程序算法演示每次比较两个数据(队员)的时候，只要遇到最高的球员就交换他的位置，直到最后他到达队列的最右边。冒泡排序，即在算法执行的时候，最大的数据项总是“冒泡”到数组的顶端。APPLET晌羚彪呕濒陛翠哥咕布匹操摇蚕漂吝劲玫杏擒雇换反录讹幕挽渍溜婴胎腕数据结构
11、（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingnJava code for a bubble sortJava code for a bubble sort切贬宁搏伶娟猪逝讹遵崇截唇述衣扁奢珍夏但灯互盟谗巷蚜痈别渡频蒋龚数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingn算法思路：将最小的数据项放在数组的开头，最大的数据项放在结尾。外层循环的计数器out从数组的最后开始，即out等于nElems-1,每经过一次循环out减一。下标大于out的数据项已经排好序。
12、变量out每完成一次内部循环就左移一位。内层for循环计数器in从数组最开始算起，即in=0，每完成一次内部循环体加一，当它等于out时，结束一次循环。内层for循环体中，数组下标为in和in+1的两个数据项进行比较，满足条件则交换数据项旅华羹浙腿波伍垒砰间十赵宾淆捎圆颓许悦潮噪啪王羞栏鸣汀妇伶步跟渤数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting貌半傻邮锄撮迎篙臀瘁磕轿欲捎狙馁硝赵金妨源系葡摸酶钮徒浆延舆橇持数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesort
13、ingn不变性不变性在许多算法中，有些条件在算法执行过程中是不变的，这些条件被称为不变性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.锑悼峪顷腆厢录催规矗拟信醛泼绪宵党巾煎瘪功散铝框锦字钡啤溢天康株数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simpl
14、esortingnEFFICIENCY OF THE BUBBLE SORTEFFICIENCY OF THE BUBBLE SORTthere will be about Nthere will be about N2 2/2 comparisons/2 comparisonsthere will be about Nthere will be about N2 2/4 swaps/4 swapsthe bubble sort runs in the bubble sort runs in O(NO(N2 2) ) time. time. Whenever you see nested lo
15、ops such as those in the bubble sort and Whenever you see nested loops such as those in the bubble sort and the other sorting algorithms in this chapter, you can suspect that the other sorting algorithms in this chapter, you can suspect that an algorithm runs in O(Nan algorithm runs in O(N2 2) time.
16、) time.10个数据项：N个数据项：挫殴旨窖谈纤搽蘸提摈毡狰衫罩岸茫绸赃蝎预盘与连吱惺翅伐痒亿邵疥梦数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting Selection SortSelection Sortn选择排序改进了冒泡排序，将比较的交选择排序改进了冒泡排序，将比较的交换次数从换次数从O(NO(N2 2) )减少到减少到O(N).O(N).不幸的是，不幸的是，比较次数仍然为比较次数仍然为O(NO(N2 2).). - - The selection sort improves on the The selecti
17、on sort improves on the bubble sort by reducing the number of bubble sort by reducing the number of swapsswaps necessary from necessary from O(NO(N2 2) to O(N).) to O(N). Unfortunately, Unfortunately, the number ofthe number of comparisons comparisons remains remains O(NO(N2 2).).午境庸沦晓就画眯狂椭惦靴剥铣没碎啄贬午
18、刚淄猿四孺惮刮摈禁越肤霉聪数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingn nA Brief DescriptionA Brief Description扫描所有队员，从中挑出最扫描所有队员，从中挑出最扫描所有队员，从中挑出最扫描所有队员，从中挑出最小者小者小者小者交换最小者与站在最左端的交换最小者与站在最左端的交换最小者与站在最左端的交换最小者与站在最左端的队员，即队员，即队员，即队员，即0 0 0 0号位置号位置号位置号位置再次从再次从再次从再次从1 1 1 1号开始扫描球队队列，号开始扫描球队队列，号开始扫描球队队
19、列，号开始扫描球队队列，还是寻找最矮的，然后和还是寻找最矮的，然后和还是寻找最矮的，然后和还是寻找最矮的，然后和1 1 1 1交交交交换。这个过程一直持续到所换。这个过程一直持续到所换。这个过程一直持续到所换。这个过程一直持续到所有队员都排定。有队员都排定。有队员都排定。有队员都排定。APPLET毁悯措蛙什禽虞聚茎猜钡挺拨咸瓶冲壳缨渝衫口疡姐澈罩纳疯哩疑靴昂忱数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingnJAVA CODE FOR SELECTION SORTJAVA CODE FOR SELECTION SORT瘩和
20、徒洼厘稚矿土孜琵修炮猪杆幼极畔屯临能洋疤孝塔滔残酮潘睫涅郴物数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingn n选择排序的基本思想选择排序的基本思想nnnn个记录的文件的直接选择排序可经过个记录的文件的直接选择排序可经过个记录的文件的直接选择排序可经过个记录的文件的直接选择排序可经过n-1n-1n-1n-1趟直接选择排趟直接选择排趟直接选择排趟直接选择排序得到有序结果：序得到有序结果：序得到有序结果：序得到有序结果：初始状态：无序区为初始状态：无序区为初始状态：无序区为初始状态：无序区为R1.nR1.nR1.nR1.n，
21、有序区为空。，有序区为空。，有序区为空。，有序区为空。第第第第1 1 1 1趟排序趟排序趟排序趟排序 在无序区在无序区在无序区在无序区R1.nR1.nR1.nR1.n中选出关键字最小的记录中选出关键字最小的记录中选出关键字最小的记录中选出关键字最小的记录RkRkRkRk，将，将，将，将它与无序区的第它与无序区的第它与无序区的第它与无序区的第1 1 1 1个记录个记录个记录个记录R1R1R1R1交换，使交换，使交换，使交换，使R1.1R1.1R1.1R1.1和和和和R2.nR2.nR2.nR2.n分别分别分别分别变为记录个数增加变为记录个数增加变为记录个数增加变为记录个数增加1 1 1 1个的新
22、有序区和记录个数减少个的新有序区和记录个数减少个的新有序区和记录个数减少个的新有序区和记录个数减少1 1 1 1个的新无序个的新无序个的新无序个的新无序区。区。区。区。第第第第i i i i趟排序趟排序趟排序趟排序第第第第i i i i趟排序开始时，当前有序区和无序区分别为趟排序开始时，当前有序区和无序区分别为趟排序开始时，当前有序区和无序区分别为趟排序开始时，当前有序区和无序区分别为R1.i-1R1.i-1R1.i-1R1.i-1和和和和Ri.n(1in-1)Ri.n(1in-1)Ri.n(1in-1)Ri.n(1in-1)。该趟排序从当前无序区中选出关键字。该趟排序从当前无序区中选出关键字
23、。该趟排序从当前无序区中选出关键字。该趟排序从当前无序区中选出关键字最小的记录最小的记录最小的记录最小的记录RkRkRkRk，将它与无序区的第，将它与无序区的第，将它与无序区的第，将它与无序区的第1 1 1 1个记录个记录个记录个记录RiRiRiRi交换，使交换，使交换，使交换，使R1.iR1.iR1.iR1.i和和和和Ri+1.nRi+1.nRi+1.nRi+1.n分别变为记录个数增加分别变为记录个数增加分别变为记录个数增加分别变为记录个数增加1 1 1 1个的新有序区和个的新有序区和个的新有序区和个的新有序区和记录个数减少记录个数减少记录个数减少记录个数减少1 1 1 1个的新无序区。个的
24、新无序区。个的新无序区。个的新无序区。 这样，这样，这样，这样，n n n n个记录的文件的直接选择排序可经过个记录的文件的直接选择排序可经过个记录的文件的直接选择排序可经过个记录的文件的直接选择排序可经过n-1n-1n-1n-1趟趟趟趟直接选择排序得到有序结果。直接选择排序得到有序结果。直接选择排序得到有序结果。直接选择排序得到有序结果。 扼幻露橇嵌座棍归砾政萨琐爱鞍咳齐貉螟低稠探厂帕逼屑缎煽诺放揪股职数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting琵佐罚膘绅粒鳞澡园团弃甘梆获祈真坑支谷魁似锥麦瞪引呵肥刨卧樟桶诡数据结构
25、（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingn nINVARIANT INVARIANT 在在selectSort.java selectSort.java 程序中，下标小于或程序中，下标小于或等于等于outout位置的数据项总是有序的。位置的数据项总是有序的。鲤贼蹈阅遵跌失喧创湍捻渴纸惦匙耪窗产挫宜青念重瞎颜恤拍假绿诊传磺数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingnEFFICIENCY OF THE SELECTION SORTEFFICIENCY
26、 OF THE SELECTION SORTnThe selection sort performs the same number The selection sort performs the same number of comparisons as the bubble sort: of comparisons as the bubble sort: N*(NN*(N1)/21)/2. .nFor For large values of Nlarge values of N, the comparison times , the comparison times will domina
27、te, so we would have to say that will dominate, so we would have to say that the selection sort runs in the selection sort runs in O(NO(N2 2) ) time, just as time, just as the bubble sort did.the bubble sort did.nHowever, it is unquestionably faster because However, it is unquestionably faster becau
28、se there are so there are so few swapsfew swaps. For . For smaller values of smaller values of N N, it may in fact be considerably , it may in fact be considerably fasterfaster, , especially if the swap times are much larger especially if the swap times are much larger than the comparison times.than
29、 the comparison times.矩邢榜丫郊橡荚媚聂钟屋板烟幂樱疚开侣谓狐绦欧峭祸籽降电叔譬稍砍量数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting Insertion SortInsertion Sortn在大多数情况下，插入排序是基本排序算法在大多数情况下，插入排序是基本排序算法中最好的。虽然插入排序算法仍然需要中最好的。虽然插入排序算法仍然需要O(NO(N2 2) )的时间的时间. .一般情况下，其效率比冒泡排序快一一般情况下，其效率比冒泡排序快一倍，比选择排序还要快一点。倍，比选择排序还要快一点。 - In
30、 most cases the insertion sort is the - In most cases the insertion sort is the best best of the elementary sorts described in this chapter. of the elementary sorts described in this chapter. It still executes in It still executes in O(NO(N2 2) ) time, but its about time, but its about twice as fast
31、 as the bubble sort and somewhat faster twice as fast as the bubble sort and somewhat faster than the selection sort in normal situations.than the selection sort in normal situations.战脸超瘸升压搓得吨士汰捷铃相殊切驳患暴旭窄前耘入趾快奴褥朱蚊进霹数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingn nA brief descriptionA b
32、rief descriptionA brief descriptionA brief description假定：队列排好了一半假定：队列排好了一半假定：队列排好了一半假定：队列排好了一半( ( ( (局部局部局部局部有序有序有序有序) ) ) )在队伍中间有一个作为标记在队伍中间有一个作为标记在队伍中间有一个作为标记在队伍中间有一个作为标记的队员，其左边所有元素按的队员，其左边所有元素按的队员，其左边所有元素按的队员，其左边所有元素按照顺序排列，右边元素等待照顺序排列，右边元素等待照顺序排列，右边元素等待照顺序排列，右边元素等待插入到合适位置插入到合适位置插入到合适位置插入到合适位置标记队员
33、出列标记队员出列标记队员出列标记队员出列依次比较依次比较依次比较依次比较标记队员标记队员标记队员标记队员与与与与有序队有序队有序队有序队列中队员列中队员列中队员列中队员身高，如比标记队身高，如比标记队身高，如比标记队身高，如比标记队员高，则移动至空位，直至员高，则移动至空位，直至员高，则移动至空位，直至员高，则移动至空位，直至没有比当前标记队员高的。没有比当前标记队员高的。没有比当前标记队员高的。没有比当前标记队员高的。标记队员初始位置后移，循标记队员初始位置后移，循标记队员初始位置后移，循标记队员初始位置后移，循环执行，直至整个队列有序环执行，直至整个队列有序环执行，直至整个队列有序环执行，
34、直至整个队列有序APPLET尿搅召瘫水旭熔协超婆丙骆沸勘魂柞土象仆添啪贺仿添狰辅苦翟镭妒赣遇数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingnJAVA CODE FOR INSERTION SORTJAVA CODE FOR INSERTION SORT靠肤灭涧雾恐票挺逮膛茧助窍降剿蘑禽县峰极站蹭庭龟测豪腐荣靖积默徒数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesortingn n算法思想：算法思想： 把把把把n n n n个待排序的元素看成为一个有序表和一个无序
35、个待排序的元素看成为一个有序表和一个无序个待排序的元素看成为一个有序表和一个无序个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含表，开始时有序表中只包含一个元素，无序表中包含表，开始时有序表中只包含一个元素，无序表中包含表，开始时有序表中只包含一个元素，无序表中包含有有有有n-1n-1n-1n-1个元素，排序过程中每次从无序表中取出第一个元素，排序过程中每次从无序表中取出第一个元素，排序过程中每次从无序表中取出第一个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为个元素，将它插入到有序表中的适当位置，使之成为个元素，将它
36、插入到有序表中的适当位置，使之成为个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复新的有序表，重复新的有序表，重复新的有序表，重复n-1n-1n-1n-1次可完成排序过程。次可完成排序过程。次可完成排序过程。次可完成排序过程。 把把把把aiaiaiai插入到插入到插入到插入到a0a0a0a0，a1a1a1a1，.,ai-1.,ai-1.,ai-1.,ai-1之中的具体之中的具体之中的具体之中的具体实施过程为实施过程为实施过程为实施过程为: : : :先把先把先把先把aiaiaiai赋值给变量赋值给变量赋值给变量赋值给变量t,t,t,t,然后将然后将然后将然后将t t t t依次与
37、依次与依次与依次与ai-1,ai-2,.ai-1,ai-2,.ai-1,ai-2,.ai-1,ai-2,.进行比较进行比较进行比较进行比较, , , ,将比将比将比将比t t t t大的元素右移一大的元素右移一大的元素右移一大的元素右移一个位置个位置个位置个位置, , , ,直到发现某个直到发现某个直到发现某个直到发现某个j(0=j=i-1),j(0=j=i-1),j(0=j=i-1),j(0=j=i-1),使得使得使得使得aj=taj=taj=tajxi+1 xixi+1 则交换之则交换之，继续这样作，直至，继续这样作，直至不交换为止。不交换为止。 该方法的结束条件如何该方法的结束条件如何
38、? ?用用oddEvenSort()oddEvenSort()方法替换方法替换bubbleSort.javabubbleSort.java程序（程序（lists 3.1)lists 3.1)中的中的bubbleSortbubbleSort（）方（）方法。确保它可以在不同数据量的排序中运行，还需要算出法。确保它可以在不同数据量的排序中运行，还需要算出两趟循环的次数。两趟循环的次数。 雀哲戍矫垢界概布臀耻玛寝哉钢裕磊汕版王嘘雾栓泽丑镇季淀酗驶酞烷鲁数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting假定有假定有6个成员：个成员：1073492oddnumtaxis:7103429evennumtaxis:7310249Cyc2:37210493274109Cyc3:2347910over!takesthreecycstocomparewiththearray彦挫究硼式逸承停铝嗓酞妙潜程朵猖较撼渭内纪绅毡童柒膳瞪缅杭赋供戍数据结构（严蔚敏）chapter3simplesorting数据结构（严蔚敏）chapter3simplesorting
