2.1.2排序问题与算法的多样性.ppt

排序问题与算法的多样性 导入 你会不会从图书馆中寻找到你想要的书籍？ 　为了便于查询和检索，我们常常根据需要将被查寻的对象按照一定的顺序排列，通常称为排序． 　按照某种顺序排列的数据列为有序列． 导入 问题：将3插入到有序列{－3,－2,2,4,7}中,你能想到几种排序方法？ 提示:两种方法:有序列直接插入排序和有序列折半插入排序. 方法一：已知数列由小到大(或由大到小)排列整齐,再将3从右向左逐个与有序列中数据比较,确定3在排列中的位置,该位置的两侧数字必须满足: 左边小于等于(大于等于)3,右边大于等于(小于等于)3. -3 -2 2 4 7 3 此方法叫作有序列直接插入排序. 导入 方法二：首先选择有序列的“中间位置”数据2,将3与2进行比较，显然32,所以3应排在2的右边:{-3,-2,2,3,4,7}. 然后取余下数据列{4,7}的“中间位置”的数据4与3比较,显然34,因此3应插到4的左边：{-3,-2,2,3,4,7}. 此方法叫作有序列折半插入排序. 思考—有序列的排列问题 问题:把数据52插入到有序列{13,27,51,57,82}中构成一个新的有序列. 解法一: 1.比较52与82, ∵ 52 82∴52放82 左边;　　 2.比较52与57, ∵ 52 57∴52放57左边; 3.比较52与51, ∵ 52 51∴52放51与57中间; 4.得到新有序列{13,27,51,52,57,82}. a1 a2 a3 a4 a5 13 27 51 57 82 首先选择有序列的“中间位置”数据a3=51,将52与51进行比较，显然52 51,所以52应排在51的右边: a1 a2 a3 a4 a5 13 27 51 52 57 82 然后取余下数据列{57,82}的“中间位置”的数据a4=57与52比较，显然5257,因此52应插到57的左边: a1 a2 a3 a4 a5 a6 13 27 51 52 57 82 解法二: Big idea 归纳 · 概括 1．有序列直接插入排序法蕴涵的算法思想： 有序列直接插入法主要是通过逐一比较，通过有限次的“操作”将某一个数据插入原有序列的一种算法，它主要包含以下两步： 对于一个有序列：a1≤a2≤a3≤…≤an，欲将新数据A插入到有序列中，形成新的有序列． ①将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai，使得ai≤A，把A插入到ai的右边； ②如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边． Big idea 归纳 · 概括 2．有序列折半插入排序法蕴涵的算法思想及插入的方法和步骤： 折半插入排序的基本思想与二分法的思想一致，即逐步缩小所要比较的数据的范围，直到确定出所要插入的数据的位置为止．插入的方法如下： ①先将新数据与有序列中“中间位置”的数据进行比较: 若有序列有2n＋1个数据，则“中间位置”的数据指的是第n＋1个数；若有序列有2n个数据，则“中间位置”的数据指的是第n个数． Big idea 归纳 · 概括 ②如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则将新数据插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边的一半． 也就是说，一次比较就排除了数据列中一半的位置，反复进行这种比较直到确定新数据的位置，像这样的插入排序方法就称为折半插入排序方法． 分别用两种方法将数据210插入到有序列{6,56,98,114,156,320,421}中,用自然语言写出排序算法的步骤． 解法1(直接插入法)： ⑴比较210与421,∵210421∴210放421左边; ⑵比较210与320,∵210320∴210放320左边; ⑶比较210与156,∵210156∴210放156和320之间; ⑷得到新的有序列{6,56,98,114,156,210,320,421}. 解法2 (折半插入法)： ⑴取有序列中间数114210; ⑵取114右边有序列中间数320210; ⑶取320左边有序列中间数156210; ⑷将210插入到156和320之间; ⑸得出新的有序列. 练习 思考—无序数据排序 问题:将无序列{1,17,5,12,8,25,15}按照从小到大的顺序，用自然语言写出排序算法的步骤． 提示:参考有序列排序算法的思想. 从左向右,将无序列的第一个数据看成的一个序列{1},将17插入有序列{1}中,得到两个数据的有序列:{1,17}; 将第三个数据5插入到{1,17}中,得到有序列:{1,5,17}; … ….