《排序问题与算法的多样性.ppt》由会员分享，可在线阅读，更多相关《排序问题与算法的多样性.ppt（25页珍藏版）》请在三一办公上搜索。
1、排序问题与算法多样性,作者：tornado_lwp,1.知识结构,算法的概念,算法的步骤,算法的特点,算法,小复习,2.算法的特点:思路简单清晰,叙述复杂,步骤繁琐,计算量大,完全依靠人力难以完成.而这些恰恰就是计算机的特长,它能不厌其烦地完成枯燥的、重复的繁琐的工作.正因为这些,现代算法的作用之一就是使计算机代替人完成某些工作,这也是我们学习算法的重要原因之一.,明确性:算法对每一个步骤都有确切的,能有效执行且得到确定结果的,不能模棱两可。,有效性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题。
2、,有限性:算法应由有限步组成,至少对某些输入,算法应在有限多步内结束,并给出计算结果,不唯一性:求解某一个问题的解法不一定是唯一的,对于同一个问题可以有不同的解法,在函数的应用部分,我们学习了用二分法求方程f(x)=0的近似解.如图所示,二分法的基本思想是:将方程的有解区间分为两个小区间,然后判断解在哪个小区间;继续把有解的区间一分为二进行判断,如此周而复始,直到求出满足精度要求的近似解.,1.确定有解区间(f(a)f(b)0).,2.取 的中点,3.计算函数f(x)在中点处的函数值,4.判断函数值 是否为零,如果为零,就是方程的解,问题就得到解决.,b)如果函数值 不为零,则分下列两种情形:
3、,2)若 则确定新的有解区间为,5.判断新的有解区间长度是否小于精确度:(1)如果新的有解区间长度大于精确度,则在新的有解区间的基础上重复上述步骤;(2)如果新的有解区间长度小于或等于精确度,则取新的有解区间的中点为方程的近似解.,1.求方程f(x)=x3+x2-1=0在区间 上的实数解,精确度为0.1.,解:1.因为f(0)=-1,f(1)=1,f(0)f(1)0.1,2.取 的区间中点0.5;,3.计算f(0.5)=-0.125;,4.由于f(0.5)f(1)0.1,练习,6.计算f(0.75)=-0.1563;,7.由于f(0.75)f(1)0.1,8.取区间 的中点0.875;,9.计
4、算f(0.875)=0.43555,10.由于f(0.75)f(0.875)0.1;,11.取区间 的中点0.8125,5.取 的区间中点0.75;,11.计算f(0.8125)=0.19653,12.因f(0.75)f(0.8125)0,得区间 精度0.8125-0.75=0.06250.1,13.该区间一满足精确度的要求,所以取该区间的中点0.78125,它是方程的一个近似解.,排序问题与算法多样性,作者：tornado_lwp,实例展示,你会使用这些字典吗？,为了便于查询和检索，我们常常根据需要将被查寻的对象按照一定的顺序排列，通常称为排序按照某种顺序排列的数据列为有序列,你会从这些书籍
5、中查阅你想要的东西吗？,新来的同学小黄身高1.75m，在班上是中等升高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？,象这样一种在已经按一定顺序排好的序列（有序列）中插入，我们就叫它有序列直接插入排序,teacher,小黄,？,问题：,我们在一个已经排好顺序的一系列数中插入一个数据，成为一个新的有序列，且仍按原来的规则排序。,要将8插入到1,3,5,7,9,11,13中，我们怎样考虑？,确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据,将这个位置空出来，将数据8插进去,8,问题分析,有序列直接插入排序的算法：,对于一个有序列：-.欲将新数据A插入
6、到有序列中，形成新的有序列，其做法是：将数据A与原有序列中的数据从右到左（也可以从左到右）进行比较，直到发现某一数据 使得 A，把A插入到 的右边；如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边,例题分析,例1已知有一组系列13,27,38,39,43,47,48,51,57,66,74,82，现要将数据52插入到数据中。,(1)请设计算法，确定52在新数据中的位置，并画出算法示意图,(2)在确定52的序列号后，请将52插入系列中,1.手工插入：,把原序列中912号的数据依次向右挪一位，空出9号位置来，并插入52，得到一个新序列。或者：两步同时进行，即从右边最后一位开始，与52
7、比较，若比52大就右挪，否则插入52.,确定52的序号：9;,为什么要从右边开始？,2.流程图：,确定52的位置：从右到左比较系列数与52的大小，使52在两个数之间，位置为9,插入数据，位置9以后的数据后移一位，在9位置插入52,把数据52插入到有序列13,27,51,57,82中构成一个新的有序列,练习：,分析：1.比较52与82,52 5152放51与57中间.得到新有序列13,27,51,52,57,82,思考：此题是否还有其它方法呢？,分析：,首先选择有序列的“中间位置”数据=51,将52与 进行比较，显然52,所以52应排在 的右边:,然后取余下数据列,的“中间位置”的数据=57与5
8、2比较，显然52,因此52应插到 的左边：,小结：此排序方法称为有序列的折半插入排序,归纳：,有序列的折半插入排序的思想：先将数据与有序列中“中间位置”的数据进行比较，若有序列有2n+1个数据则“中间位置”的数据指的是第个n+1数；若有序列有2n个数据则“中间位置”的数据指的是第n个数;如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则新数据应插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应靠右边一半,即一次比较就排除了数据列中一半的位置，反复进行比较直到确定新数据的位置,课堂练习：,1)分别用两种
9、方法将数据210插入到有序列6,56,98,114,156,320,421中，用自然语言写出排序算法的步骤,解：方法直接插入法：比较210与421,210156210放156和320之间得到新的有序列6,56,98,114,156,210,320,421,方法2折半插入法：取有序列中间数114210取320左边有序列中间数156210将210插入到156和320之间得出新的有序列,2)用直接插入排序法将61插入13,37,40,55,65,76,97中，共比较了（）A,3次 B,4次 C,5次 D,6次,思考题：如何将无序列15,3,10,12,8从小到大排列，用自然语言写出算法,A,B,3)用折半插入排序法将10插入有序列7,9,11,12,15中第2次是10与（）的比较A,10与7 B,10与9 C,10与12 D,10与15,课时小结：,有序列折半插入排序的思想和算法有序列直接插入排序的思想和算法注意理解同一个问题算法的多样性及各自的优缺点,
