算法设计实例教程 课件 第3、4章 排序算法-算法设计实例教程、查找-算法设计实例教程

算法设计实例教程教学分析目录CONCENTS123456789第3章排序算法第1章数据结构基础第2章基础算法第4章查找第5章字符串和高精度运算第6章图论算法第7章动态规划算法第8章计算几何基础第9章高级算法排序算法是算法设计中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。第3章排序算法排序算法的稳定性：如果两个数值相等的数，在排序前和排序后能保持两个数在序列中前后位置顺序不变的排序算法称为稳定排序，否则为不稳定排序。例如，有Ai=Aj，排序前Ai在Aj的前面，排序后Ai仍然还在Aj的前面，这时候就称为稳定排序，否则，就称为不稳定排序。时间复杂度：对排序数据的总操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。3.1排序的相关概念冒泡排序（BubbleSort）是一种简单实用的排序算法。它是从队列首部开始，依次比较两个相邻的数据，如果顺序错误就把它们进行交换，直至没有数据可以交换为止。在这个过程中，待排序的元素会经由交换慢慢“浮”到数列的顶端，就如同水池中的气泡最终会上浮到顶端一样，故名“冒泡排序”。3.2冒泡排序在使用冒泡排序时，首先应该确定是进行升序排序还是降序排序。升序排序就是将待排列的数据按照从小到大的顺序排序，当升序排序时，需要较大的数向后“沉”，而将较小的数向前“冒”。降序排序则正好相反，它是将待排列得数据按照从大到小的顺序排序，它需要较小的数向后“沉”，而将较大的数向前“冒”。第1步：比较相邻的元素。如果第一个比第二个大，就交换他们两个。第2步：对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。第3步：针对所有的元素重复以上的步骤，除了最后一个。第4步：持续每次对越来越少的元素重复步骤1~3，直到没有任何一对数字需要比较。3.2.1冒泡排序算法描述例如，将序列“5，4，3，2，1”变成升序“1，2，3，4，5”的“冒泡排序”的示意图如图3.1。从图中可以看出随着“5”逐渐“沉”下去，“1”逐渐“冒”了上来。重复沉“4”“3”“2”“1”会冒到最顶上。3.2.1冒泡排序算法描述图3.1冒泡原理示意【例3.1】冒泡排序时间限制：1000ms内存限制：32MB问题描述编写一个程序：从键盘上输入整数个数n（n<255），按照冒泡排序的思想，对n个整数进行升序排序，最后输出排序结果。输入说明输入的数据之间空一格，最后一个回车。输出说明打印输出的时候空一格。输入样例9876543210输出样例01234567893.2.2冒泡排序程序实现举例问题分析：首先需要建立一个int类型的数组arr存储待排序数据，然后利用冒泡排序对数组中的数据进行排序。如果是n个数排序，共需要n-1轮排序。这就需要建立一个循环结构。设置一个循环控制变量i，通过控制变量i实现n-1轮排序。令i=1作为循环的初始条件，用“i<=n-1”作为循环控制表达式，用“i++”作为循环控制变量的改变。循环体完成数组的每轮排序比较。循环语句如下：for(i=1;i<=n-1;i++){//每轮比较的程序代码}冒泡排序使用了两层循环嵌套，外层循环称为遍历。例如，第一轮遍历就是外层循环的第一次迭代。在每次内层循环的迭代过程中，对列表中剩余的未排序元素进行排序，直到最高值冒泡到最后为止。第一轮遍历将进行N-1次比较，第二轮遍历将进行N-2次比较，而每轮后续遍历将比前一轮减少一次比较操作。当待排序序列是有序的时候（最好情况），比较次数为n-1次，没有数据交换，此时时间复杂度为O(n)；当待排序序列是逆序的时候（最坏的情况），当初始序列从大到小逆序时，需要进行n-1趟排序，进行n(n-1)/2次比较和交换，此时的时间复杂度为O(n2)。空间复杂度：冒泡排序只需要一个临时变量来交换数据，所以为O(1)。3.2.3冒泡排序算法分析选择排序(SelectionSort)是一种简单直观的排序算法。它的基本思想：首先在待排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3.3选择排序（SelectionSort）n个记录的选择排序可经过n-1轮选择排序得到有序结果。具体算法描述如下：3.3.1选择排序算法描述第1步：待排序序列为R[1..n]，有序序列为空；第2步：第i趟排序(i=1,2,3…,n-1)开始时，当前有序序列和无序序列（待排序列）分别为R[1..i-1]和R(i..n）。该趟排序从当前无序序列中选出关键字最小的记录R[k]，将它与无序序列的第1个记录R交换，使R[1..i]和R(i+1..n)分别变为记录个数增加1个的新有序序列和记录个数减少1个的新无序序列；第3步：n-1趟结束，数组有序了。

例如，将序列“53，64，28，72，1”变成升序“1，28，53，64，72”的“选择排序”的第一轮操作如图3.3所示。从图中可以看出随着待排序序列中的元素“1”首先被“选择”出来与数组下标为0的元素“53”交换位置，然后在待排序序列“64，28，72，53”中继续“选择”最小的元素“28”与数组下标为1的元素“64”交换位置，重复相同的操作，直至待排序序列完全有序。

图3-3第一轮选择排序示意图3.3.1选择排序算法描述【例3.2】选择排序时间限制：1000ms内存限制：32MB问题描述编写一个算法实现选择排序思想，并将乱序数列变成升序数列。输入说明第一行输入数据元素的个数，第二行为待排序的数据元素，输入的数据之间空一格，最后一个回车。输出说明打印输出的时候空一格，尾数后没有空格。输入样例1071468952310输出样例12345678910

3.3.2选择排序算法实现举例3.3.2选择排序算法实现举例问题分析根据题意和选择排序的基本思想，可以定义变量n存储待排序的元素个数，然后根据第一行输入的数值n动态分配存储空间大小arr=(int*)malloc(sizeof(int)*n)，而在选择排序的过程中，在每一轮排序中找到数值最小的元素，并临时存储在minIdx中，直到本轮循环结束for(inti=0;i<n-1;i++){intminIdx=i;for(intj=i+1;j<n;j++){if(arr[minIdx]>arr[j]){minIdx=j;}}后把值最小元素“放”到arr[i]的位置。temp=arr[minIdx];arr[minIdx]=arr[i];arr[i]=temp;选择排序是一种简单直观的排序算法，无论待排序序列是正序还是逆序，每⼀轮的最⼩（最大）值都需要⽐较到最后才能确定，那么，最坏情况和最好情况下都需要⽐较n-1次，再加上遍历整个序列的O(n)，总的复杂度为O(n2)，平均复杂度也是O(n2)。所以，选择排序比较适合数据规模不大的情形。空间复杂度方面，选择排序只需要⼀个额外用来存放“临时最⼩值”的空间，除此之外，不占用额外的内存，所以空间复杂度为O(1)，同时，选择排序是不稳定排序。。

3.3.3选择排序算法分析插入排序（Insertion-Sort）是一种简单直观的排序算法。它的工作原理是将未排好序的元素⼀个个地插⼊到已排好序（开始时为空）的序列中，插⼊时，需要与已排好序的元素进⾏多次⽐较，直到找到合适（比前一个元素大，比后一个元素小或者比前一个元素小，比后一个元素大）的位置插⼊，⽽原来已排好序的部分元素可能需要进⾏后移操作，最后形成有序序列。

3.4插入排序（InsertionSort）第4步：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；第6步：重复步骤2~5，直到序列有序。

第5步：将新元素插入到该位置后；第2步：取出下一个元素，在已经排序的元素序列中从后向前扫描；第1步：从第一个元素开始，此时，只有一个元素，该元素可以看作已排序；第3步：如果该元素（已排序）大于新元素，将该元素移到下（后移）一位置；一般来说，插入排序一般都采用in-place在数组上实现。具体算法描述如下：3.4.1插入排序算法描述例如，将序列“5，4，3，2，1”变成升序“1，2，3，4，5”的“插入排序”的操作如图3.4所示。3.4.1插入排序算法描述图3-4插入排序示意图【例3.4】插入排序时间限制：1000ms内存限制：32MB问题描述实现插入排序算法，并将乱序数列变成升序数列。输入说明第一行输入数据元素的个数，第二行为待排序的数据元素，输入的数据之间空一格，最后一个回车。输出说明打印输出的时候空一格，尾数后没有空格。输入样例1023846815473271450输出样例234152347685071843.4.2插入排序算法实现举例3.4.2插入排序算法实现举例算法分析定义两个变量i和j分别的控制外层循环和内层循环，然后依次取出待排序序列中的各个元素存储在val中，用val与未排序序列中元素arr[j]比较，直到找到val的“位置”，经过n1轮排序即可得到有序序列，核心参考代码如下：1voidsort_array(int*arr,intn)

2{

3for(inti=1;i<n;i++){

4intval=arr[i];

5for(intj=i-1;j>=0;j--){

6if(val<arr[j]){//待插入的元素小于当前元素的值，7arr[j+1]=arr[j];//当前元素向后移动一个位置8arr[j]=val;

9}

10else{

11break;

12}

13}

14}

15}空间复杂度：插入排序在实现上，一般采用in-place在数组上实现，即只需用到O(1)的额外空间，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。时间复杂度：最坏情况：当待排序序列正好为逆序状态，⾸先遍历整个序列，然后⼀个个地将待插⼊元素放在已排序的序列最前⾯，之后的所有元素都需向后移动⼀位，所以⽐较和移动的时间复杂度都是O(n)，再加上遍历整个序列的复杂度，总复杂度为O(n2)。最好情况：当待排序序列正好为正序状态，则遍历完整个序列，当插⼊元素时，只⽐较⼀次就够了，所以时间复杂度为O(n)。平均情况：当被插⼊的元素放在已排序的序列中间位置时，为平均情况，⽐较和移动的时间复杂度为O(n2)，所以总的时间复杂度依然为O(n2)。稳定性：插⼊排序的⽐较是从有序序列的末尾开始，也就是想要插⼊的元素和已经有序的最⼤者开始⽐起，如果⽐它⼤则直接插⼊在其后⾯，否则⼀直往前找直到找到它该插⼊的位置。如果遇见⼀个和插⼊元素值相等的，那么插⼊元素把想插⼊的元素放在相等元素的后⾯。值相等元素的前后顺序没有改变，所以插⼊排序是稳定的。3.4.3插入排序算法分析归并排序是建立在归并操作上的一种有效的排序算法。其基本思想是将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序算法是基于分治策略而设计的。在被称为划分的第一阶段中，算法将数据递归地分成两部分，直到数据的规模小于定义的阈值。在被称为归并的第二阶段中，算法不断地进行归并和处理，直到得到最终的结果。3.5归并排序（MergeSort）3.5.1归并排序算法描述01第1步：把长度为n的输入序列分成两个长度为n/2的子序列；02第2步：对这两个子序列分别采用归并排序；03第3步：将两个排序好的子序列合并成一个最终的排序序列。例如：将待排序序列[25,6,93,17,41,86,32,79,58]排成升序序列[6,17,25,32,41,58,79,86,93]的归并操作如图3.5所示。3.5.1归并排序算法描述图3-5归并排序示意图【例3.6】合并两个序列时间限制：1000ms内存限制：32MB问题描述输入两个递增的序列，输出合并这两个序列后的递增序列。输入说明每个测试案例包括3行：第一行为1个整数n（1<=n<=1000000）表示这两个递增序列的长度。第二行包含n个整数，表示第一个递增序列。第三行包含n个整数，表示第二个递增序列。输出说明对应每个测试案例，输出合并这两个序列后的递增序列。输入样例413572468输出样例12345678。3.5.2归并排序算法实现举例：算法分析将两个递增序列合并成为一个递增序列，常规的操作是将第二个递增追加到第一个递增序列的后面，然后进行冒泡排序就可以得到一个递增序列。但是，当问题规模增大时，时间复杂度急剧增加，本题尝试用归并排序思想来解决。因归并的方法采用了分治的策略，性能大大提升，归并排序和选择排序一样，性能不受输入数据的影响，但其性能比选择排序大大提升，因为其时间复杂度一直为O(nlogn），不过，带来的代价是需要额外的内存空间。时间复杂度：归并排序的时间主要消耗在划分序列和合并序列上，由于采⽤递归⽅式进⾏合并，如果集合长度为n，那么划分的层数就是logn，每一层进行归并操作的运算量是n。所以，归并排序的时间复杂度等于每一层的运算量×层级数，即O(nlogn)，⽽且不管元素是否基本有序都需要进行类似操作，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都相同。空间复杂度：归并排序是需要用到额外空间的，但是每次归并所创建的额外空间都会随着方法结束而释放，因此单次归并操作开辟的最大空间是n。所以，归并排序的空间复杂度是O(n)。归并排序是稳定排序算法。3.5.3归并排序算法分析快速排序和冒泡排序一样，也是交换类排序⽅法。其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。3.6快速排序（QuickSort）快速排序使用分治法来把一个序列分为两个子序列。具体算法描述如下：3.6.1快速排序算法描述第1步：从数列中挑出一个元素，称为“基准”（pivot）；第2步：将所有元素比基准值小的集中在基准左边（或者右边），所有元素比基准值大的集中在基准的右边（或者左边，相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区（partition）操作；第3步：采用递归（recursive）思想把小于基准值元素的子数列和大于基准值元素的子数列排序再一次进行快速排序。第4步：重复以上过程，直到序列有序。例如：将待排序序列[59,16,83,97,21,45,3,74,68]排成升序序列[3,16,21,45,59,68,74,83,97]的快速排序的第一轮操作如图3.6所示。快速排序遍历开始的时候是从后面j往前遍历，当元素值大于pivot时j--；元素值小于pivot时，j保持不变，并且将j指向的值替换i指向的值，i++；这时，i从前往后遍历，小于pivot的值就i++；遇到大于pivot的元素时，i不变，并且将i指向的值替换j指向的值，j--，这样交替进行，直到i和j指向同一位置。3.6.1快速排序算法描述图3-6快速排序的第一轮操作示意图【例3.7】快速排序时间限制：1000ms内存限制：32MB问题描述用递归法实现快速排序算法，并将乱序数列变成升序。输入说明第一行输入数据元素的个数，第二行为待排序的数据元素，输入的数据之间空一格，最后一个回车。输出说明打印输出的时候空一格，尾数后没有空格。输入样例108536236729641195078输出样例21923364150677885963.6.2快速排序算法实现举例算法分析定义两个变量i和j为数组的下标，最开始时i=0，j=n-1，取出待排序序列中的第一个元素a[0]作为“基准”，即pivot=a[0]，然后从数组的最后一个元素开始依次与pivot比较，直到找到比pivot小的元素并且交换位置，同时i++，这时从数组元素a[i]开始依次与pivot依次比较，直到找到比pivot大的元素并且交换位置，如此交替进行直到i==j。第一轮快速排序结束，得到序列是以pivot为基准，左边的元素都比pivot小，右边的元素都比pivot大的序列。以此为基础，进一步对pivot的左右两侧的子序列进行重复的操作直至整个序列保持有序。时间复杂度：最坏情况时，每⼀次选取的基准元素都是最⼤或最⼩的，复杂度为O(n2)，最好情况时，每⼀次选取的基准元素都能平分整个序列，由于快排涉及到递归调⽤，所以时间复杂度为O(nlog2n)。平均情况下复杂度也是O(nlog2n)。空间复杂度：快速排序使⽤的辅助空间是O(1)，⽽消耗空间较大的是在递归调⽤的时候了，因为每次递归就要保留⼀些数据，每⼀次都平分数组的情况下空间复杂度为O(logn)，最差的情况下空间复杂度为O(n)，快速排序是不稳定排序。3.6.3快速排序算法分析排序算法通常可以分为比较类排序和非比较类排序，冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序都属于比较类排序，而计数排序、基数排序和桶排序都属于非比较类排序。每一种排序算法都有特定的使用情形，一般来说，选择合适的排序算法既取决于当前输入数据的规模，也取决于当前输入数据的状态。对于基本有序且规模较小的输入列表，使用高级算法会给代码带来不必要的复杂度，而性能的提升可以忽略不计。例如，对于较小的数据集，一般不使用归并排序，冒泡排序更容易理解和实现。如果数据已经被部分排好序了，则可以使用插入排序。对于较大的数据集，归并排序算法是最好的选择。表3-1为常见排序算法的时间复杂度和空间复杂度以及稳定性情况。3.7排序算法的性能比较3.7排序算法的性能比较排序方法时间复杂度（平均）时间复杂度（最坏）时间复杂度（最好）空间复杂度稳定性冒泡排序O(n2)O(n2)O(n)O(1)稳定选择排序O(n2)O(n2)O(n2)O(1)不稳定插入排序O(n2)O(n2)O(n)O(1)稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)稳定希尔排序O(n1.3-2)O(n2)O(n)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定桶排序O(n+k)O(n2)O(n)O(n+k)稳定表3-1常见排序算法性能情况3.8本章小结排序是算法设计中一种重要的操作，其主要功能就是对一个待排序序列进行重新排列成按照数据元素某个属性值有序的序列。实现排序的两个基本操作：（1）比较。“比较”待排序序列中两个关键字的大小；（2）移动。“移动”记录。正如本章节开始所介绍的常见的排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。每种排序算法都有自己特点和适用场景，那么如何选择一种排序算法呢？一般来说：当待排序列中元素很少的时候，适合选用插入排序；当待排序列中所有的元素几乎有序，也比较适合选用插入排序；而如果着重考虑排序算法最坏情况，适合选用堆排序；当希望排序算法的平均性能比较好时，选用快速排序比较合适；当待排序列中元素从一个密集几何中抽取出的时候，适合选用桶排序；如果期望编写的代码尽可能简练，选择插入排序比较合适3.8本章小结算法设计实例教程教学分析目录CONCENTS123456789第4章查找第1章数据结构基础第2章基础算法第3章排序算法第5章字符串和高精度运算第6章图论算法第7章动态规划算法第8章计算几何基础第9章高级算法查找也称搜索，搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。第4章查找4.1.1顺序查找的基本概念

顺序查找算法又称顺序搜索算法或者线性搜索算法，是所有查找算法中最基本、最简单的，对应的时间复杂度为O(n)。顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。其基本思想是从线性表的第1个元素开始，通过逐个比较表中的关键字，直到找到符合要求的关键字，完成查找，或搜索整个表，没有找到符合要求的关键字，则表示查找失败。但是这种查找方法的效率较低，主要针对数量较少，无规则的数据。如果查找表中的数据已经按顺序排列，则可以使用一种称为二分查找的方法。。4.1顺序查找时间限制：1000ms内存限制：65535KB问题描述输入10个数，要求输出其中的最大值。输入说明测试数据有多组，每组10个数。输出说明对于每组输入,请输出其最大值（有回车）。输入样例102223152657985963240输出样例max=1524.1.2顺序查找的应用举例1：找最大值

算法分析创建一个数组以及创建一个变量max，给变量max赋初值为然后跟数组中每个元素一一进行判断，如果数组中的数比max大那么把这个数赋给max，以此类推，直到查找完数组中的所有元素即可完成查找，停止运算。实现的代码如下：intmain(){intd[10],i,max;for(i=0;i<10;i++)scanf("%d",&d[i]);max=d[0];for(i=1;i<10;i++){if(max<d[i])max=d[i];}printf("max=%d\n",max);return0;}时间限制：1000ms内存限制：32MB问题描述输入一行字符串，计算其中A-Z大写字母出现的次数。输入说明案例可能有多组，每个案例输入为一行字符串。输出说明对每个案例按A-Z的顺序输出其中大写字母出现的次数。输入样例DFJEIWFNQLEF0395823048+_+JDLSFJDLSJFKK4.1.3顺序查找的应用举例2：字母统计

输出样例A:0B:0C:0D:3E:2F:5G:0H:0I:1J:4K:2L:3M:0N:1O:0P:0Q:1R:0S:2T:0U:0V:0W:1X:0Y:0Z:04.1.3顺序查找的应用举例2：字母统计

算法分析该问题的策略就是建立一个长度为26的整型数组用来统计每个字母的出现次数，然后依次遍历字符串中的每一个字符，对字符进行判断，如果该字符是某个字母，就将该字母对应的统计数据加1。代码如下：intmain(){charstr[10000]={0};intcount[26]={0};inti;while(scanf("%s",str)!=EOF){for(i=0;i<strlen(str);i++){if('A'<=str[i]&&str[i]<='Z'){count[str[i]-'A']++;}}for(i=0;i<26;i++){printf("%c:%d\n",'A'+i,count[i]);}}return0;}4.2.1二分查找的基本概念二分查找又称折半查找、二分搜索、折半搜索等，是一种采用了分治策略的查找算法。二分查找只能用于有序线性表的查找。假设在一个长度为n的有序数组中查找一个数字，如果使用顺序查找的方式逐一检查数组中的每个数字，那么需要O（n）的时间复杂度，而如果使用二分查找，时间复杂度可以优化到O（logn）。随着线性表的规模n越大，二分查找在时间性能上的优越性就会越明显。4.2二分查找

4.2.1二分查找的基本概念二分查找的查找策略是：每次将位于线性表中间的数字和目标数字比较。如果中间数字正好等于目标数字，那么就找到了目标数字。如果中间数字大于目标数字，那么下一次查找的时候只需要在线性表的前半部分找，这是因为线性表是排序的，后半部分的数字都大于或等于中间数字，所以一定都大于目标数字，也就没有必要再在后半部分查找。如果中间数字小于目标数字，那么接下来只需要查找线性表的后半部分，这是因为排序数组的前半部分的数字都小于或等于中间数字，所以一定都小于目标数字，也就没有必要再在前半部分查找。从查找的过程可以看出，二分查找是一种递归的过程。由于二分查找算法每次都将查找范围减少一半，对于包含n个元素的列表，用二分查找最多需要log2n步。但是由于二分查找要求待查找的数据必须是线性有序的，对于没有经过排序的数据，可以通过排序算法进行预排序，然后进行二分查找的操作。4.2二分查找

时间限制：1000ms内存限制：65535KB问题描述有n个已经从小到大排序好的数据（不重复），从键盘输入一个数，用二分查找方法，判断target是否在这n个数中。输入说明第1行，数组的长度length第2行，n个整数（int范围内，不重复），中间用空格分隔；第3行，整数target。输出说明如果找到target，输出其位置；否则输出-1。4.2.2二分查找的应用举例1：查找元素x

输入样例10102030405060708090100906-10359122输出样例8-1算法分析使用二分查找算法在一个已排序（升序）的数组中查找一个指定的元素，首先将这个待查找元素与数列中位于中间位置的元素进行比较，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。1.循环方式intsearch_loop(inta[],intsize,inttarget){intleft=0,mid;intright=size-1;while(left<=right){mid=left+(right-left)/2;//定位查找区间的中间元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左边区域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右边区域else//a[mid]就是要查找的元素returnmid;}return-1;//没有找到目标值}4.2.2二分查找的应用举例1：查找元素x

在上面的函数定义中，分别使用了left和right两个变量记住查找的范围。初始情况下left为0，right为数组长度-1，分别指向数组的起始和结束位置。随着查找的推进，每次都根据判断的结果，更新left或者right的值，直到left>right就结束循环。如果直到循环结束都没有找到目标值，则输出-1。2.递归方式由于每次查找的方法是一样的，不一样的仅仅是查找的数组的范围，因此递归是一种很直观的实现方式。用一对整数变量表示目标元素的查找区间的起始和结束位置，并作为参数传递给递归函数。随着查找范围的不断缩小，直到查找区间包含的元素个数少于或等于1个，查找就停止了。实现代码如下：intsearch_recur(inta[],intleft,intright,inttarget){intmid;if(left>right)return-1;//没有找到目标值mid=left+(right-left)/2;//定位查找区间的中间元素if(a[mid]>target)search_recur(a,left,mid-1,target);//递归地查找mid左边区域elseif(a[mid]<target)search_recur(a,mid+1,right,target);//递归地查找mid右边区域else//a[mid]就是要查找的元素returnmid;}4.2.2二分查找的应用举例1：查找元素x

4.2.2二分查找的应用举例1：查找元素

递归的优势就是代码简洁，且能够直观的对应解决问题的思路，但存在的问题是内存消耗太大。main函数实现如下：intmain(){intlength,target,i;while(scanf("%d",&length)!=EOF){for(i=0;i<length;i++)scanf("%d",&a[i]);scanf("%d",&target);printf("%d\n",search_recur(a,0,length-1,target));}return0;}时间限制：1000ms内存限制：65535KB问题描述统计一个数字在一个有序数组中出现的次数。比如输入一个有序数组{1,2,2,2,3,3,3,4,5}和数字2，由于2在数组中出现了3次，因此程序的输出结果为3。输入说明第1行，数组的长度第2行，一个有序数组{1,2,2,2,3,3,3,4,5}第3行，1个待查找的整数target。输出说明如果数组中包含target，则输出其在数组中出现的次数位置；否则输出0。输入样例1012223334552输出样例34.2.3二分查找的应用举例2：统计数字在有序数组中出现的次数

4.2.3二分查找的应用举例2：统计数字在有序数组中出现的次数

算法分析一种直观的方式是使用顺序查找的方式遍历整个数组，只要找到某个元素目标元素target相等，则统计值加1。由于对数组的n个元素都进行了一次检查，所以该算法的时间复杂度为O(n)。使用二分查找在数组中查找元素target在数组中的位置，由于数组是有序的，因此所有相等的值在数组中的位置是连续的，因此可以继续在该位置的前后查找与target相等的元素。前面已经分析过，二分查找能够快速的缩小查找的范围，将算法的时间复杂度降低到O(logn)。使用二分查找法进行数字统计的函数实现如下：intnum(inta[],intsize,inttarget){intleft=0,right=size-1,mid,sum=0;inti;while(left<=right){mid=left+(right-left)/2;//定位查找区间的中间元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左边区域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右边区域else//a[mid]就是要查找的元素{sum=1;//找到了一个目标元素break;}}for(i=mid+1;i<size&&a[i]==target;i++)//向左统计sum++;for(i=mid-1;i>0&&a[i]==target;i--)//向右统计sum++;returnsum;4.2.3二分查找的应用举例2：统计数字在有序数组中出现的次数

在顺序查找和二分查找中，算法要处理的数据以线性表的形式表示。在线性表中，数据元素之间是线性关系，每个数据元素只有一个直接前驱和一个直接后继。但是在图中，任意两个数据元素之间都可能存在直接的关系，通常用节点表示数据元素，用连接两个节点的边表示数据元素之间的关系。图的搜索算法通常用来解决基于状态空间的搜索问题。所谓状态就是为了区分不同事物而引入的一组数据元组，如X=[x1,x2,x3...xn]，其中每一个元素xi被称为状态分量。首先把问题表示转化为一个由多个状态组成的集合，如果可以通过一些定义好的运算使得某个状态跳转到下一个状态，那么这两个状态之间就形成了一个关联关系。所有的状态，以及状态之间的关联关系就形成了一个拓扑图。解题的过程就是对图的搜索。对一个图进行搜索意味着从图中的一个节点开始，按照某种特定的顺序依次遍历图中的边，从而找到一条从起始节点到目标节点的路径，或是遍历图中所有的节点，找到符合检索要求的节点。按照搜索顺序的不同，可以将搜索算法分为广度优先算法和深度优先搜索。4.3图的搜索

DFS（DepthFirstSearch），即深度优先搜索。其搜索策略是：从图中某节点v出发，沿着一条路径一直搜索下去，当无法搜索时，回退到刚刚访问过的节点。具体说来包括以下几个步骤：4.3.1DFS的基本概念

（1）初始化图中的所有节点，将它们都标记为未被访问。（2）从图中的某个节点v出发，访问v并标记其已被访问。（3）依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复步骤2～3），这一过程一直进行到已发现从出发节点可达的所有节点为止。（4）如果当前已经没有未被访问的邻接节点时，则回退到上一步刚刚访问过的节点，继续重复步骤2~3。按照深度优先搜索，当搜索到某一步时，发现原先的选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术被称为回溯法，而满足回溯条件的某个状态被称为“回溯点”。4.3.1DFS的基本概念

按照深度优先搜索算法遍历图中的节点，我们会发现后被访问的节点，其邻接点先被访问，这是典型的后来者先服务，可以借助于栈的结构来实现。由于递归本身就是使用栈实现的，因此使用递归的方法更方便。深度优先搜索算法可以用以下伪代码来表示：voidDFS(GraphG,nodev){nodew;visit(v);visited[v]=True;for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])DFS(G,w);}从图G中的某一个节点v开始，首先访问节点v，并将v的状态设置为已访问。随后依次对v的所有邻接节点w进行遍历，如果w是一个未被访问过的节点，则继续使用深度优先搜索算法以w为出发节点进行搜索。由于算法是递归调用的，当v的某个邻接节点w访问不下去的时候，函数返回到v，继续对v的下一个邻接节点使用DFS展开搜索。。4.3.1DFS的基本概念

下面以下图为例模拟深度优先搜索算法的搜索路线。4.3.1DFS的基本概念

图4-1二叉树树是图的一种特殊形式，是连通且没有回路的图。图中所示的是一棵二叉树，即每个父节点最多只有两个子节点，其中一个是左子节点，一个是右子节点。现在我们要使用深度优先算法遍历树中的每一个节点，那么节点编号所组成的序列就是遍历的顺序。假设我们规定对每一个节点来说，先访问其左子节点，后访问其右子节点。按照深度优先搜索算法：（1）从根节点1开始（2）先访问1的左子节点2，然后以递归的方式遍历以2为根节点的子树，以此类推，得到1→2→4→7遍历序列。（3）到达节点7后，发现其没有左子节点，也没有右子节点，于是返回到节点4，节点4的也没有右子节点，于是继续向上返回到节点2，节点2有右子节点，于是访问节点5，更新遍历序列为1→2→4→7→5。（4）节点5既没有左子节点，也没有右子节点，于是返回到其父节点2。此时节点2完成了其所有子节点的遍历，于是继续向上返回到节点1。（5）此时节点1已完成了左节点的遍历，继续访问其右节点3，更新遍历序列为1→2→4→7→5→3。节点3没有左子节点，于是访问其右节点6，更新遍历序列为1→2→4→7→5→3→6。（6）节点6先访问左子节点8，由于节点8没有子节点，于是完成访问后返回节点6，然后访问节点6的右子节点9，更新遍历序列为1→2→4→7→5→3→6→8→9。同样，由于节点9也没有子节点，于是完成访问后返回节点6。（7）节点6已完成其所有子节点的访问，于是返回节点3，同样，节点3也完成了所有子节点的访问，于是返回节点1，完成所有节点的遍历和递归访问。得到结论，基于深度优先搜索算法遍历该树的所有节点时，访问序列为：1→2→4→7→5→3→6→8→9。4.3.1DFS的基本概念

BFS（BreadthFirstSearch），即广度优先搜索。其搜索策略是：从起点开始，对与其邻接的所有节点都访问一边，然后依次从这些已经访问过的邻接点出发，再对它们的邻接点进行访问。具体说来包括以下几个步骤：4.3.2BFS的基本概念

（1）初始化所有节点均未被访问，并初始化一个空队列。（2）从图中的某个节点v出发，访问v并标记其已被访问，将v入队列。（3）如果队列非空，则继续执行，否则算法结束。（4）将队头元素v移出队列，依次访问v的所有未被访问的邻接点，标记已被访问并将它们加入队的尾部。转向步骤3。按照广度优先搜索算法遍历图中的节点，我们会发现每次都是从队列的头部拿出一个节点进行扩展，而新扩展出的节点都是加到队列的尾部，因此所有的节点按照先进先出的顺序被访问，可以借助于队列的结构来实现。队列是一种先进先出的数据结构，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。4.3.2BFS的基本概念

广度优先搜索算法可以用以下伪代码来表示：voidBFS(GraphG,nodev){初始化一个空队列queue;将nodev加入queue头部；while(queue不为空){nodev=queue_front();visited[v]=True；pop_front(queue);for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])将节点w加入queue尾部；}}下面依然以图4-1为例模拟广度优先搜索算法的搜索路线。按照广度优先搜索算法：（1）队列初始条件下为空queue={}；（2）从根节点1开始，将节点1放入队列，得到队列为{1}。（3）将队列中的第一个元素1取出来，将其标记为已访问，并将1的所有未访问的邻接节点放入队列的尾部，队列更新为{2，3}，访问序列为1。（4）将队列中的第一个元素2取出来，将其标记为已访问，并将2的所有未访问的邻接节点放入队列的尾部，队列更新为{3，4，5}，访问序列为1→2。（5）将队列中的第一个元素3取出来，将其标记为已访问，并将3的所有未访问的邻接节点放入队列的尾部，队列更新为{4，5，6}，访问序列为1→2→3。（6）将队列中的第一个元素4取出来，将其标记为已访问，并将4的所有未访问的邻接节点放入队列的尾部，队列更新为{5，6，7}，访问序列为1→2→3→4。4.3.2BFS的基本概念

（7）将队列中的第一个元素5取出来，将其标记为已访问，由于5没有未访问的邻接节点，于是队列更新为{6，7}，访问序列为1→2→3→4→5。（8）将队列中的第一个元素6取出来，将其标记为已访问，并将6的所有未访问的邻接节点放入队列的尾部，队列更新为{7，8，9}，访问序列为1→2→3→4→5→6。（9）将队列中的第一个元素7取出来，将其标记为已访问，由于7没有未访问的邻接节点，队列更新为{8，9}，访问序列为1→2→3→4→5→6→7。（10）将队列中的第一个元素8取出来，将其标记为已访问，由于8没有未访问的邻接节点，队列更新为{9}，访问序列为1→2→3→4→5→6→7→8。（11）将队列中的第一个元素9取出来，将其标记为已访问，由于9没有未访问的邻接节点，队列更新为{}，访问序列为1→2→3→4→5→6→7→8→9。（12）由于队列为空，结束循环，搜索结束，最终得到的树的广度优先搜索序列为1→2→3→4→5→6→7→8→94.3.2BFS的基本概念

时间限制：1000ms内存限制：32MB问题描述输入一个包含n个节点的树，节点编号依次为0、1...n-1，以及一个包含n-1条无向边的edges列表，其中edges[i]=[a,b]表示节点a和节点b中存在一条无向边。当选择其中任何一个节点作为根节点时，都可形成一棵高度为h的树。在所有可能的树中，具有最小高度的树被称为最小高度树。要求找到所有的最小高度树，并依次输出它们的根节点编号。输入说明一个整数n，代表树的节点数。一个二维矩阵edges，表示树的边输出说明所有最小高度树的根节点编号。输入样例n=4edges=[[1,0],[1,2],[1,3]]输出样例[1]4.3.3DFS与BFS的应用举例1：最小高度树

算法分析以样例输入为例，该树包括4个节点，3条边，当我们选择其中任何一个节点作为树根时，都可以相应构造出一棵树，树的结构如下：4.3.3DFS与BFS的应用举例1：最小高度树

图4-2不同高度的树其中最小高度树是以节点1为根的树，树高为1。由于树的连通性且没有环，任何一个节点都可以作为树根，从而形成一棵树。直观的解决办法是依次对每一个可能形成的树使用DFS算法，然后计算树中每个节点的高度，并将其中最大值作为树的高度。但是这种算法的时