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

1、第二章 算法初步,1算法的基本思想,理解教材新知,应用创新演练,考点一,把握热点考向,考点二,1.2 排序问题与算法的多样性,12排序问题与算法的多样性,由于人类具有主观能动性，将数据a插入到有序列a1，a2，an中时，能很快找到适当的位置，而计算机解决此类问题时，其解决方式不同计算机每次只能比较两个数据的大小，不能直接“看”出应插到有序列a1，a2，an的哪个位置，因此要想用计算机解决排序问题必须要设计算法，使得每次仅比较两个数的大小 问题：若将3插入到有序列3，2,2,4,7中，排序方法有几种？ 提示：有两种,1排序 为了便于查询和检索，常常根据某种要求把被查询的对象用 表示出来，并把 按

2、大小排列，是信息处理中一项基本的工作，通常称为排序 2排序的方法 (1) 排序法； (2) 排序法,数字(或者符号),数字,有序列直接插入,折半插入,1有序列直接插入排序法蕴涵的算法思想： 有序列直接插入法主要是通过逐一比较，通过有限次的“操作”将某一个数据插入原有序列的一种算法，它主要包含以下两步： 对于一个有序列：a1a2a3an，欲将新数据A插入到有序列中，形成新的有序列 将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai，使得aiA，把A插入到ai的右边； 如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边,2有序列折半插入排序法蕴涵的算法思想及插入的方法

3、和步骤： 折半插入排序的基本思想与二分法的思想一致，即逐步缩小所要比较的数据的范围，直到确定出所要插入的数据的位置为止 插入的方法如下： 先将新数据与有序列中“中间位置”的数据进行比较 若有序列有2n1个数据，则“中间位置”的数据指的是第n1个数；若有序列有2n个数据，则“中间位置”的数据指的是第n个数,如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则将新数据插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边的一半 也就是说，一次比较就排除了数据列中一半的位置，反复进行这种比较直到确定新数

4、据的位置，像这样的插入排序方法就称为折半插入排序方法,例1将4插入有序列8，3,0,2,6中，分别用直接插入排序法和折半插入排序法写出算法 思路点拨(1)利用直接插入排序法，只要按从右到左的顺序将4逐个与有序列中数据进行比较即可； (2)利用折半插入排序法，应找到中间位置a30与4进行比较，然后把剩下数据中间位置的数据依次与4比较，直到找到4的位置,精解详析法一：直接插入排序法： (1)4与6比较，由于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的左

5、边，故 4在8与3之间； (4)得新的有序列8，4，3,0,2,6 一点通两种算法的共同点是每次将新数据与有序列中的数据进行比较；不同点是直接插入排序法总是将数据A与原有序列中的数据从右到左依次进行比较，而折半插入排序法总是将新数据与该有序列中的“中间位置”的数据进行比较,1将数据6通过直接插入排序的方法插入有序列 1,3,5,7,9,11,13中，需要作比较大小的次数为 () A3B4 C5 D6 解析：数据6依次与13,11,9,7,5比较，共作5次比较大小,答案：C,2若用折半插入排序法将4插入到有序列0,1,2,3中，则 第一次应与该有序列中的哪个数比较 () A0 B1 C2 D3

6、解析：因为有序列中有22个数，所以应先与第2个数1进行比较,答案：B,3请利用直接插入排序和折半插入排序的方法分别写出 将数据43插入有序列21,39,46,57,67,73,84,96的算法 解：直接插入排序算法： 将43与96比较，4396，所以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

7、折半插入排序算法： 共8个数，中间位置上的数是57，将43与57进行比较，4357,43在有序列的左半部分；再将余下数据的中间位置上的数39与43进行比较，3943,43在数据39的右边，又4346，可得43在39与46之间，即新的有序列为21,39,43,46,57,67,73,84,96.,例2将无序列1,17,5,12,8,25,15按照从小到大的顺序，用自然语言写出排序算法的步骤 思路点拨根据无序列排序的方法操作即可，用自然语言把每步操作叙述出来即可得到算法的步骤 精解详析1.将17插入到序列1中得新序列1,17； 2将5插入到序列1,17中得1,5,17； 3将12插入到序列1,5,

8、17中， 125，且1217， 应将12插入到5与17之间得序列1,5,12,17；,4将8插入到序列1,5,12,17中，取序列中间数5， 85，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应在12的右侧，故应将15插入到12与17之间得序列1,5,8,12,15,17,25,一点通对一组无序的数据列进行排序时，通常将这组无序的数据列的第一个数据看成一个有序列，将第二个数据插入到这

9、个有序列得到一个有序列；然后，将第三个数据插入到上面的有序列中，又得到一个有序列，按照这种方法，直到将最后一个数据插入到有序列中，得到一个有序列，这样实质上就是完成了对无序的数据列排序，最后得到的有序列就是对无序的数据组排序的结果,4将有序列5,4,3,2,1按照从小到大的顺序输出，需要 排序的次数为 () A7 B8 C9 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插入到2,3,4,5中，得1,2,3,4,5，需4次排序 故共需123410次排序,答案：D,5设计

10、算法，将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各数进行比较，因为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对于一个无序列将其重新进行有序排列的方法： 方法一：利用有序列插入排序法来解决 方法二：利用“选择排序”的方法来解决例如