《2.1.2 排序问题与算法的多样性.doc》由会员分享，可在线阅读，更多相关《2.1.2 排序问题与算法的多样性.doc（1页珍藏版）》请在三一文库上搜索。
1、2.1.2排序问题及算法的多样性教学目标：1掌握数据排序的原理能使用直接排序法给一组数据排序，进而能设计理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用。教学重点：排序法的排序步骤教学难点：排序法的计算机程序设计教学过程 排序排序的算法很多，课本主要介绍里两种排序方法：直接插入排序和折半插入排序1、有序列直接插入排序基本思想：插入排序的思想就是读一个，排一个。将第个数放入数组的第个元素中，以后读入的数与已存入数组的数实行比较，确定它在从大到小的排列中应处的位置将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中（因为算法简单，能够举例说明）2、折半插入排序基本思想：先
2、与一组数据中间位置的数比较，类似于二分法的算法思想。练习：例1 已知有序列158，159，160，162，163，165，166，170，171，172，175,设计算法将169插入，使其从小到大排列，构成新的数据列。分析：这是一个有序列，可采用直接插入排序法一个一个的比较实行排序，也可用折半排序法实行排序。解法一：有序列直接插入排序，步骤如下：1. 先比较169与175，169175.2. 再比较169与172，169172.3. 再比较169与171，169171.4. 再比较169与170，169170.5. 再比较169与166，169166.所以将169插入166与170之间，得到一
3、个新的有序列。解法二：有序列折半插入排序，步骤如下：1.选择中间位置的数据165，2. 将169与165比较，169165，所以169应排在165的右边。3. 取166，170，171，172，175的中间位置171.4. 将169与171比较，169171，所以169应排在171的左边.5. 取166，170中间位置166.6. 将166与169比较，169166，而169170，所以169应插在166与170之间。点评：有序列直接插入排序，要把需插入的数据与有序列中的数据依次比较，直到找到其插入的位置，比较的次数较多；折半插入排序法比较一次就排除了数据列中一半的数据，减少了比较次数，优化了运算过程。3.有序列插入排序 主要用来解决无序列的排序问题