1、i=1i=6j=10flag=falseflag=true:循环退出 表1当然，对分查找法与数据结构中的二叉树思想一致，所以我们也可以用二叉树来表示对分查找算法的对分过程。如图2 图2（二）标准对分算法变式 图3如图3所示，变式和原式区别在于 变式去掉的用来标识有没有找到key的flag变量计算可得 当key在当前数组（a）中不存在时 ij 即 i=j+1 ，当key存在于数组中时i=j，所以在循环结束后 我们可以 通过 i和j的关系来判断 key是否存在。（三）求大于等于/小于等于key的第一个/最后一个数1.求大于等于key的第一个数 图4 图5如图4所示，变式和原式区别在于 变式去掉的用
2、来标识有没有找到key的flag变量以及去掉了找到后退出的代码 即去掉了 Exit Do。第一轮第二轮第三轮第四轮第五轮m9467i15j188表2设key为21 当key等于a（m）时 j还要往前走 一直到到第一个第一个小于key的值 即19这个值的位置。同时根据i=j 可得 i=j+1 所以最后i是第一个值的位置。2.求小于等于key的最后一个数 图6 图71411121310表3设key为21 当key等于a（m）时 i还要往前走 一直到到最后一个大于key的值 即19这个值的位置。（四） 使用对分查找算法求值相同的数量图8 图9观察图8代码可知 这是一个求大于等于key的第一个数和求小
3、于等于key的最后一个数的合体，先求出key的第一个位置。而后求出最后一个的位置。这样就可以得到长度为 最后一个数的位置 减去 第一个数的位置 +1，即j-i+1。（五） 使用二叉树解决实际问题1.根据对分次数求key 图10 图11 观察图10代码可知 这是一个标准的对分查找，只是在标准对分上新添加了一个变量c。观察可知，c是用来记录对分次数。根据对分查找算法的原理 每一次对分 都会把范围分成两段（即两种可能）。在不知道Key不知道是多少的前提下。需要把两种可能都计算。这样刚好与二叉树的图一致，见图11。例如 求当C等于2时key等于多少？可以从图上对分次数中可得第一次对分到5 即c=1，第
4、二次对分到 2或8 即c=2,以此类推。由此可得 当c等于2时 key = 2 或8 。2.根据i、j变换求key 图12 图13 观察图12代码可知 这是一个标准的对分查找，只是在标准对分上新添加了一个变量c。观察可知，c是用来求和的。这样刚好与二叉树的图一致，即 往左走 c-1 往右走 c+1 见图13。可以从图上对分次数中可得第一次对分到5 即c=0，第二次对分到 2或8 即c=1或-1,以此类推。由此可得 当c等于2时 key =9。（六） 其他变式变式1（取第一个）L = 1: R = 10Do While L + 1 a（m） ThenL = mElseR = mEnd IfLoo
5、pPrint Str（L + 1）变式2（取第一个）m = （L + R + 1） 2变式3（死循环，无法执行）Do While L = RL = m + 1变式4（死循环，无法执行）m = （L + R - 1） 2变式5（取第一个）R = m - 1变式6（取第一个）Print Str（L）所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经
6、过大量的推理和分析。考纲中的排序包括冒泡排序，选择排序。但是在实际解题中还会碰到其他排序，例如桶排序、插入排序、快速排序、索引排序及冒泡排序的优化。本文将针对冒泡、选择、插入、桶排序、快速排序、索引排序及冒泡排序优化进行分析。冒泡排序冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算
7、，直至完成第（n一1）个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。For i = 1 To n - 1For j = n To i + 1 Step -1If a（j） a（j - 1） Then降序排Dim flag As Booleanflag = Falsen = 10 a（j - 1） = t: flag = TrueIf flag = False Then Exit
8、 For冒泡优化1Dim last As Integerflag = Truelast = 1Do While flag = TrueFor j = n To last + 1 Step -1 last = j:Loop 冒泡优化2选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍
9、选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。k = iFor j = i + 1 To n a（k） Then k = jIf k i Thent = a（k）: a（k） = a（i）: a（i） = tIf a（i） a（j） Thent = a（i）: a（i） = a（j）: a（j） = t快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此
10、方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法通过多次比较和交换来实现排序，其排序流程如下：（1）首先设定一个分界值，通过该分界值将数组分成左右两部分。（2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。（3）然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。（4）重复上述过程，可以看出，这是一个递归定义。通
11、过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。桶排序 （Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（n）。但桶排序并不是 比较排序，他不受到 O（n log n）下限的影响。Dim b（1 To 100） As IntegerFor i = 1 To 10b（a（i） = b（a（i） + 1s1 =
12、For i = 1 To 100For j = 1 To b（i）s1 = s1 + Str（i）Text2.Text = s1插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法1。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动Dim key As IntegerDim j As Integerj = 0For i = 2 To nkey = a（i）j = i - 1Do W
13、hile j = 1 And key a（j）a（j + 1） = a（j）j = j - 1a（j + 1） = key索引排序，是基于冒泡排序法的一种优化算法，算法核心是:用一个数组元素的值做另一个数组元素的下标，然后交换下标。例如 a（b（1） a（b（j - 1） Thent = b（j）: b（j） = b（j - 1）: b（j - 1） = tList1.AddItem a（b（i）递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。Function f（x As Integer） As IntegerIf x = 1 Thenf = 1f = f（x - 1） * xEnd FunctionSub f（x As Integer）Exit SubEnd Sub
