排序问题与算法的多样性

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.取区间 的中

4、点0.875;,9.计算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,问题分析,有序列直接插入排序的算法：,对于一个有

6、序列： - .欲将新数据A插入到有序列中，形成新的有序列，其做法是：将数据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，得到一个新序列。或者：两步同时进

7、行，即从右边最后一位开始，与52比较，若比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应排在 的右边:,然后取

8、余下数据列 , 的“中间位置”的数据 =57与52比较，显然52 ,因此52应插到 的左边：,小结：此排序方法称为有序列的折半插入排序,归纳：,有序列的折半插入排序的思想：先将数据与有序列中“中间位置”的数据进行比较，若有序列有2n+1个数据则“中间位置”的数据指的是第个n+1数；若有序列有2n个数据则“中间位置”的数据指的是第n个数; 如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于“中间位置”的数据，则新数据应插入到“中间位置”的数据的右边；如果新数据大于“中间位置”的数据，则新数据插入的位置应靠右边一半,即一次比较就排除了数据列中一半的位置，反复进行

9、比较直到确定新数据的位置,课堂练习：,1)分别用两种方法将数据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从小到大排列，用自然语言写