折中算法

Ⅰ 比较两个算法的不同

l=l+0/s的位置不一样，第公式是o和s的值发生了变化。第二个公式，os的值还没发生变化。

Ⅱ 数据结构 折中查找算法/选择排序 起泡排序算法

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的，我们可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。
选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。

直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。

冒泡法
为了在a[1]中得到最大值，我们将a[1]与它后面的元素a[2]，a[3]，...，a[10]进行比较。首先比较a[1]与a[2]，如果a[1]<a[2]，则将a[1]与a[2]交换，否则不交换。这样在a[1]中得到的是a[1]与a[2]中的大数。然后将a[1]与a[3]比较，如果a[1]<a[3]，则将a[1]与a[3]交换，否则不交换。这样在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此继续，最后a[1]与a[10]比较，如果a[1]<a[10]，则将a[1]与a[10]交换，否则不交换。这样在a[1]中得到的数就是数组a的最大值（一共进行了9次比较）。

为了在a[2]中得到次大值，应将a[2]与它后面的元素a[3]，a[4]，...，a[10]进行比较。这样经过8次比较，在a[2]是将得到次大值。

如此继续，直到最后a[9]与a[10]比较，将大数放于a[9]，小数放于a[10]，全部排序到此结束。
从上面可以看出，对于10个数，需进行9趟比较，每一趟的比较次数是不一样的。第一趟需比较9次，第二趟比较8次，...，最后一趟比较1次。

以上数组元素的排序，用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素，第一个元素与外循环i有关的，用a[i]标识，第二个元素是与内循环j有关的，用a[j]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为i+1,i+2,...。

Ⅲ 进程调度算法

算法原理： 就是谁先来谁就先执行

算法优点 ：易于理解且实现简单，只需要一个队列，公平
算法缺点 ：有利于长进程，不利于短进程，有利于CPU 繁忙的进程，不利于I/O 繁忙的进程

算法原理： 对预计执行时间短的进程优先执行。
算法优点 ：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
算法缺点： 对长进程不利，可能长时间得不到执行产生饥饿，不能判断执行的优先级。

算法原理： 同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。响应比R定义： R =(W+T)/T = 1+W/T
T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。执行之前系统计算每个作业的响应比，选择其中R最大者执行。这种算法是介于前面两种之间的一种折中算法。
算法优点： 长作业也有机会投入运行，避免了饥饿。
算法缺点： 每次调度前要计算响应比，增加系统开销。

算法原理： 设置一个时间片，每个进程轮流使用时间片，若一个时间片内进程还没结束，也会被其他的进程抢占时间片而退出执行，进入等待队列。
算法优点： 简单易行、平均响应时间短。
算法缺点： 不利于处理紧急作业。时间片的大小的设置对系统性能的影响很大，因此时间片的大小应选择恰当

算法原理： 根据优先级的来判断执行哪个进程。可以分为静态优先级和动态优先级，即优先级可以根据情况改变。比如如果一个进程等了很久，我们就可以把他的优先级适当的提高。

算法优点 ：可以优先处理紧急事件，适用于实时操作系统。

算法缺点 ：可能导致那些优先级低的进程饥饿。

UNIX操作系统采取的便是这种调度算法。
算法原理 ：

实现先说明执行队列优先级Q1>Q2>Q3.......>Qn，分配的时间片Qn>Qn-1>...Q1.

进程在进入待调度的队列等待时，首先进入优先级最高的队列Q1等待。若在Q1队列里面还没执行完，则下放到Q2里面，等Q1里面的进程都执行完了之后再执行Q2。以此类推。
若在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
在多级反馈队列调度算法中，规定第一个队列的时间片略大于多数人机交互所需之处理时间时，能够较好的满足各种类型用户的需要。