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

返回 第二章 算法初步 §1算法的基本思想 理解教材新知 应用创新演练 考点一 把握热点考向 考点二 1.2 排序问题与算法的多样性 1．2　排序问题与算法的多样性 由于人类具有主观能动性，将数据a插入到有序列{a1，a2，…，an}中时，能很快找到适当的位置，而计算机解决此类问题时，其解决方式不同．计算机每次只能比较两个数据的大小，不能直接“看”出应插到有序列{a1，a2，…，an}的哪个位置，因此要想用计算机解决排序问题必须要设计算法，使得每次仅比较两个数的大小． 问题：若将3插入到有序列{－3，－2,2,4,7}中，排序方法有几种？ 提示：有两种． 1．排序 为了便于查询和检索，常常根据某种要求把被查询的对象用 表示出来，并把 按大小排列，是信息处理中一项基本的工作，通常称为排序． 2．排序的方法 (1) 排序法； (2) 排序法． 数字(或者符号) 数字 有序列直接插入 折半插入 1．有序列直接插入排序法蕴涵的算法思想： 有序列直接插入法主要是通过逐一比较，通过有限次的“操作”将某一个数据插入原有序列的一种算法，它主要包含以下两步： 对于一个有序列：a1≤a2≤a3≤…≤an，欲将新数据A插入到有序列中，形成新的有序列． ①将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai，使得ai≤A，把A插入到ai的右边； ②如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边． 2．有序列折半插入排序法蕴涵的算法思想及插入的方法和步骤： 折半插入排序的基本思想与二分法的思想一致，即逐步缩小所要比较的数据的范围，直到确定出所要插入的数据的位置为止． 插入的方法如下： ①先将新数据与有序列中“中间位置”的数据进行比较． 若有序列有2n＋1个数据，则“中间位置”的数据指的是第n＋1个数；若有序列有2n个数据，则“中间位置”的数据指的是第n个数． ②如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则将新数据插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边的一半． 也就是说，一次比较就排除了数据列中一半的位置，反复进行这种比较直到确定新数据的位置，像这样的插入排序方法就称为折半插入排序方法． [例1]　将－4插入有序列{－8，－3,0,2,6}中，分别用直接插入排序法和折半插入排序法写出算法． [思路点拨]　(1)利用直接插入排序法，只要按从右到左的顺序将－4逐个与有序列中数据进行比较即可； (2)利用折半插入排序法，应找到中间位置a3＝0与－4进行比较，然后把剩下数据中间位置的数据依次与－4比较，直到找到－4的位置． [精解详析]法一：直接插入排序法： (1)－4与6比较，由于－46，则－4在6的左边； (2)－4与2比较，由于－42，则－4在2的左边； (3)－4与0比较，由于－40，则－4在0的左边； (4)－4与－3比较，由于－4－3，则－4在－3的左边； (5)－4与－8比较，由于－4－8，则－4在－8的右边，则－4在－8与－3之间； (6)得新的有序列{－8，－4，－3,0,2,6}． 法二：折半插入排序法： (1)－4与0比较，由于－40，则－4在0的左边； (2)－4与－8比较，由于－4－8，则－4在－8的右边； (3)－4与－3比较，由于－4－3，则－4在－3的左边，故 －4在－8与－3之间； (4)得新的有序列{－8，－4，－3,0,2,6}． [一点通]　两种算法的共同点是每次将新数据与有序列中的数据进行比较；不同点是直接插入排序法总是将数据A与原有序列中的数据从右到左依次进行比较，而折半插入排序法总是将新数据与该有序列中的“中间位置”的数据进行比较． 1．将数据6通过直接插入排序的方法插入有序列 {1,3,5,7,9,11,1