第1部分第二章§11.2排序问题与算法的多样性课件.ppt

1、第第二二章章算算法法初初步步1 1算算法法的的基基本本思思想想理解教材新知理解教材新知应用创新演练应用创新演练考点一考点一把握热点考向把握热点考向考点二考点二1.21.2排序排序问题问题与算与算法的法的多样多样性性返回返回返回12排序问题与算法的多样性排序问题与算法的多样性返回返回 由于人类具有主观能动性，将数据由于人类具有主观能动性，将数据a插入到有序列插入到有序列a1，a2，an中时，能很快找到适当的位置，而计算机解决中时，能很快找到适当的位置，而计算机解决此类问题时，其解决方式不同计算机每次只能比较两个此类问题时，其解决方式不同计算机每次只能比较两个数据的大小，不能直接数据的大小，不能直

2、接“看看”出应插到有序列出应插到有序列a1，a2，an的哪个位置，因此要想用计算机解决排序问题必须要设的哪个位置，因此要想用计算机解决排序问题必须要设计算法，使得每次仅比较两个数的大小计算法，使得每次仅比较两个数的大小 问题：若将问题：若将3插入到有序列插入到有序列3，2,2,4,7中，排序方中，排序方法有几种？法有几种？提示：提示：有两种有两种返回 1排序排序 为了便于查询和检索，常常根据某种要求把被查询的为了便于查询和检索，常常根据某种要求把被查询的对象用对象用 表示出来，并把表示出来，并把 按大小排列，按大小排列，是信息处理中一项基本的工作，通常称为排序是信息处理中一项基本的工作，通常称

3、为排序 2排序的方法排序的方法 (1)排序法；排序法；(2)排序法排序法数字数字(或者符号或者符号)数字数字有序列直接插入有序列直接插入折半插入折半插入返回 1有序列直接插入排序法蕴涵的算法思想：有序列直接插入排序法蕴涵的算法思想：有序列直接插入法主要是通过逐一比较，通过有限次的有序列直接插入法主要是通过逐一比较，通过有限次的“操作操作”将某一个数据插入原有序列的一种算法，它主要包含将某一个数据插入原有序列的一种算法，它主要包含以下两步：以下两步：对于一个有序列：对于一个有序列：a1a2a3an，欲将新数据，欲将新数据A插入到插入到有序列中，形成新的有序列有序列中，形成新的有序列 将数据将数据

4、A与原有序列中的数据从右到左依次进行比较，与原有序列中的数据从右到左依次进行比较，直到发现某一数据直到发现某一数据ai，使得，使得aiA，把，把A插入到插入到ai的右边；的右边；如果数据如果数据A小于原有序列中的所有数据，则将小于原有序列中的所有数据，则将A插入到插入到原序列的最左边原序列的最左边返回 2有序列折半插入排序法蕴涵的算法思想及插入的方有序列折半插入排序法蕴涵的算法思想及插入的方法和步骤：法和步骤：折半插入排序的基本思想与二分法的思想一致，即逐步折半插入排序的基本思想与二分法的思想一致，即逐步缩小所要比较的数据的范围，直到确定出所要插入的数据的缩小所要比较的数据的范围，直到确定出所

5、要插入的数据的位置为止位置为止 插入的方法如下：插入的方法如下：先将新数据与有序列中先将新数据与有序列中“中间位置中间位置”的数据进行比较的数据进行比较 若有序列有若有序列有2n1个数据，则个数据，则“中间位置中间位置”的数据指的是的数据指的是第第n1个数；若有序列有个数；若有序列有2n个数据，则个数据，则“中间位置中间位置”的数据指的数据指的是第的是第n个数个数返回 如果新数据小于如果新数据小于“中间位置中间位置”的数据，则新数据插入的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于的位置应该在靠左边的一半；如果新数据等于“中间位置中间位置”的数据，则将新数据插入到的数据，则将新数

6、据插入到“中间位置中间位置”的数据的右边；如的数据的右边；如果新数据大于果新数据大于“中间位置中间位置”的数据，则新数据插入的位置应的数据，则新数据插入的位置应该在靠右边的一半该在靠右边的一半 也就是说，一次比较就排除了数据列中一半的位置，也就是说，一次比较就排除了数据列中一半的位置，反复进行这种比较直到确定新数据的位置，像这样的插入反复进行这种比较直到确定新数据的位置，像这样的插入排序方法就称为折半插入排序方法排序方法就称为折半插入排序方法返回返回 例例1将将4插入有序列插入有序列8，3,0,2,6中，分别用中，分别用直接插入排序法和折半插入排序法写出算法直接插入排序法和折半插入排序法写出算

7、法 思路点拨思路点拨(1)利用直接插入排序法，只要按从右到利用直接插入排序法，只要按从右到左的顺序将左的顺序将4逐个与有序列中数据进行比较即可；逐个与有序列中数据进行比较即可；(2)利用折半插入排序法，应找到中间位置利用折半插入排序法，应找到中间位置a30与与4进行比较，然后把剩下数据中间位置的数据依次与进行比较，然后把剩下数据中间位置的数据依次与4比较，比较，直到找到直到找到4的位置的位置 返回 精解详析精解详析法一：法一：直接插入排序法：直接插入排序法：(1)4与与6比较，由于比较，由于46，则，则4在在6的左边；的左边；(2)4与与2比较，由于比较，由于42，则，则4在在2的左边；的左边

8、；(3)4与与0比较，由于比较，由于40，则，则4在在0的左边；的左边；(4)4与与3比较，由于比较，由于48，则，则4在在8的右边，的右边，则则4在在8与与3之间；之间；(6)得新的有序列得新的有序列8，4，3,0,2,6 返回 法二：法二：折半插入排序法：折半插入排序法：(1)4与与0比较，由于比较，由于48，则，则4在在8的右边；的右边；(3)4与与3比较，由于比较，由于43，则，则4在在3的左边，故的左边，故 4在在8与与3之间；之间；(4)得新的有序列得新的有序列8，4，3,0,2,6 一点通一点通两种算法的共同点是每次将新数据与有序列中两种算法的共同点是每次将新数据与有序列中的数据

9、进行比较；不同点是直接插入排序法总是将数据的数据进行比较；不同点是直接插入排序法总是将数据A与原与原有序列中的数据从右到左依次进行比较，而折半插入排序法有序列中的数据从右到左依次进行比较，而折半插入排序法总是将新数据与该有序列中的总是将新数据与该有序列中的“中间位置中间位置”的数据进行比较的数据进行比较返回1将数据将数据6通过直接插入排序的方法插入有序列通过直接插入排序的方法插入有序列1,3,5,7,9,11,13中，需要作比较大小的次数为中，需要作比较大小的次数为 ()A3B4C5 D6解析：解析：数据数据6依次与依次与13,11,9,7,5比较，共作比较，共作5次比较大小次比较大小答案：答

10、案：C返回2若用折半插入排序法将若用折半插入排序法将4插入到有序列插入到有序列0,1,2,3中，则中，则第一次应与该有序列中的哪个数比较第一次应与该有序列中的哪个数比较 ()A0 B1C2 D3解析：解析：因为有序列中有因为有序列中有22个数，所以应先与第个数，所以应先与第2个个数数1进行比较进行比较答案：答案：B返回3请利用直接插入排序和折半插入排序的方法分别写出请利用直接插入排序和折半插入排序的方法分别写出将数据将数据43插入有序列插入有序列21,39,46,57,67,73,84,96的算法的算法解：解：直接插入排序算法：直接插入排序算法：将将43与与96比较，比较，4396，所以，所以

11、43在在96的左边；的左边；将将43与与84比较，比较，4384，所以，所以43在在84的左边；的左边；将将43与与73比较，比较，4373，所以，所以43在在73的左边；的左边；将将43与与67比较，比较，4367，所以，所以43在在67的左边；的左边；将将43与与57比较，比较，4357，所以，所以43在在57的左边；的左边；返回将将43与与46比较，比较，4339，故，故43在在39与与46之间排序后这一之间排序后这一有序列为有序列为21,39,43,46,57,67,73,84,96折半插入排序算法：折半插入排序算法：共共8个数，中间位置上的数是个数，中间位置上的数是57，将，将43与

12、与57进行比较，进行比较，4357,43在有序列的左半部分；再将余下数据的中间位置在有序列的左半部分；再将余下数据的中间位置上的数上的数39与与43进行比较，进行比较，3943,43在数据在数据39的右边，又的右边，又435，且，且125，8在在5的右侧，取序列的右侧，取序列12,17的中间数的中间数12，817，25应在应在17的右侧，插入得序列的右侧，插入得序列1,5,8,12,17,25；返回 6将将15插入到插入到1,5,8,12,17,25中，取序列的中间数中，取序列的中间数8，158，15应在应在8的右侧，取序列的右侧，取序列12,17,25的中间的中间数数17，1512，15应在

13、应在12的右侧，故应将的右侧，故应将15插入到插入到12与与17之间得序列之间得序列1,5,8,12,15,17,25返回 一点通一点通对一组无序的数据列进行排序时，通常将对一组无序的数据列进行排序时，通常将这组无序的数据列的第一个数据看成一个有序列，将第二这组无序的数据列的第一个数据看成一个有序列，将第二个数据插入到这个有序列得到一个有序列；然后，将第三个数据插入到这个有序列得到一个有序列；然后，将第三个数据插入到上面的有序列中，又得到一个有序列，个数据插入到上面的有序列中，又得到一个有序列，按照这种方法，直到将最后一个数据插入到有序列中，得按照这种方法，直到将最后一个数据插入到有序列中，得

14、到一个有序列，这样实质上就是完成了对无序的数据列排到一个有序列，这样实质上就是完成了对无序的数据列排序，最后得到的有序列就是对无序的数据组排序的结果序，最后得到的有序列就是对无序的数据组排序的结果返回4将有序列将有序列5,4,3,2,1按照从小到大的顺序输出，需要按照从小到大的顺序输出，需要排序的次数为排序的次数为 ()A7 B8C9 D10解析：解析：1.把把4插入到插入到5中，得中，得4,5，需，需1次排序；次排序；2把把3插入到插入到4,5中，得中，得3,4,5，需，需2次排序；次排序；3把把2插入到插入到3,4,5中，得中，得2,3,4,5，需，需3次排序；次排序；4把把1插入到插入到

15、2,3,4,5中，得中，得1,2,3,4,5，需，需4次排序次排序故共需故共需123410次排序次排序答案：答案：D返回5设计算法，将设计算法，将36,6,12,24,38,46,0排序排序解：解：1.36是有序列，将是有序列，将36与与6比较，因为比较，因为366，故得，故得到有序列到有序列6,36；2将将12与与6,36各数进行比较，因为各数进行比较，因为126，故得，故得到有序列到有序列6,12,36；3将将24与与6,12,36各数进行比较，因为各数进行比较，因为2412,2436，故得，故得到有序列到有序列6,12,24,36,38；返回5将将46与与6,12,24,36,38各数进

16、行比较，因为各数进行比较，因为4638，故得，故得到有序列到有序列6,12,24,36,38,46；6将将0与与6,12,24,36,38,46各数进行比较，因为各数进行比较，因为06，故得，故得到有序列到有序列0,6,12,24,36,38,46所以排序之后的结果为所以排序之后的结果为0,6,12,24,36,38,46返回 1对于一个无序列将其重新进行有序排列的方法：对于一个无序列将其重新进行有序排列的方法：方法一：利用有序列插入排序法来解决方法一：利用有序列插入排序法来解决 方法二：利用方法二：利用“选择排序选择排序”的方法来解决例如：给定一的方法来解决例如：给定一个无序列个无序列23,12,56,40,98,33,56,67，首先从这个数据列中，首先从这个数据列中，选出小的数据放在第选出小的数据放在第1个位置上；然后从余下的数据列中选个位置上；然后从余下的数据列中选出最小的数据放在第出最小的数据放在第2个位置反复执行上述步骤，直到数个位置反复执行上述步骤，直到数据列成为序列通常这种排序方法称为选择排序据列成为序列通常这种排序方法称为选择排序 2对无序的数据列排序的实质是将数据插入到有序列对无序的数据列排序的实质是将数据插入到有序列中的一个过程中的一个过程返回