教育专题：快排及二分查找（插入 (2)

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,快排及二分查找（插入）,快排,快速排序（,Quicksort,）是对,冒泡排序,的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以,递归,进行，以此达到整个数据变成有序,序列,。,快排,设要排序的,数组,是,A0AN-1,，首先任意选取一个数据,k,（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的,排序算法,，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。,假设用户输入了如下数组,创建变量,i=0,（指向第一个数据）,j=5(,指向最后一个数据,),k=6(,赋值,为第一个数据的值,),。,快排,下标,0,1,2,3,4,5,数据,6,2,7,3,8,9,快排,我们要把所有比,k,小的数移动到,k,的左面，所以我们可以开始寻找比,6,小的数，从,j,开始，从右往左找，不断递减变量,j,的值，我们找到第一个下标,3,的数据比,6,小，于是把数据,3,移到下标,0,的位置，把下标,0,的数据,6,移到下标,3,，完成第一次比较：,下标,0,1,2,3,4,5,数据,3,2,7,6,8,9,i=0 j=3 k=6,快排,接着，开始第二次比较，这次要变成找比,k,大的了，而且要从前往后找了。递加变量,i,，发现下标,2,的数据是第一个比,k,大的，于是用下标,2,的数据,7,和,j,指向的下标,3,的数据的,6,做交换，数据状态变成下表：,下标,0,1,2,3,4,5,数据,3,2,6,7,8,9,i=2 j=3 k=6,称上面两次比较为一个循环。接着，再递减变量,j,，不断重复进行上面的循环比较。,快排,在本例中，我们进行一次循环，就发现,i,和,j“,碰头”了：他们都指向了下标,2,。于是，第一遍比较结束。得到结果如下，凡是,k(=6),左边的数都比它小，凡是,k,右边的数都比它大：,下标,0,1,2,3,4,5,数据,3,2,6,7,8,9,快排,如果,i,和,j,没有碰头的话，就递加,i,找大的，还没有，就再递减,j,找小的，如此反复，不断循环。注意判断和寻找是同时进行的。,然后，对,k,两边的数据，再分组分别进行上述的过程，直到不能再分组为止。,注意：,第一遍快速排序不会直接得到最终结果，只会把比,k,大和比,k,小的数分到,k,的两边。为了得到最后结果，需要再次对下标,2,两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。,二分查找,二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的,关键字,与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置,记录,将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,二分查找法的算法要求,必须采用,顺序存储结构,必须按关键字大小有序排列。,二分查找的源代码,Int,binary_search(constintarr,int,low,int,high,int,key),Int,mid=low+(high-low)/2;,if(low,high),return-1;,else,If(,arr,mid=key),Return mid;,Else if(,arr,midkey),Return binary_search(arr,low,mid-1,key);,else,Return binary_search(arr,mid+1,high,key);,二分插入,上面已经学习了二分查找法，我们在回顾一下插入排序法。在插入排序法中，我们每次向有序数列中插入一个数，使之在合适的位置，并使得数列有序。,我们在学习了二分查找法后，可以用二分查找的这种办法来快速找到合适的位置，这也是我们算法的一种,分治法。,二分插入,同学们想一下，怎么才能用二分法找到数据的插入位置呢？,找到位置的条件：,LOWHIGH,同学们可自己举例来证明,二分插入,找到的合适位置应该就是,LOW,的下标，找到后就需要在这个位置插入这个数据。如何插入呢？,从数组的最后一个元素开始，依次往后移一位。,例：,合并果子,(NOIP2004),在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过,n-1,次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为,1,，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有,3,种果子，数目依次为,1,，,2,，,9,。可以先将,1,、,2,堆合并，新堆数目为,3,，耗费体力为,3,。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为,12,，耗费体力为,12,。所以多多总共耗费体力,=3+12=15,。可以证明,15,为最小的体力耗费值。,例：,合并果子,(NOIP2004),【,输入文件,】,输入文件,fruit.in,包括两行，第一行是一个整数,n,（,1=n=10000,），表示果子的种类数。第二行包含,n,个整数，用空格分隔，第,i,个整数,ai,（,1=,ai,=20000,）是第,i,种果子的数目。,【,输出文件,】,输出文件,fruit.out,包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于,231,。,【,样例输入,】31 2 9【,样例输出,】15,