一趟扫描算法是什么

❶ 关于《操作系统》中的磁盘调度算法

（1）先来先服务调度算法
由于该算法就是按照磁道请求序列的先后次序依次访问磁道的，因此磁道的访问序列（服务顺序）就是：
110、180、32、115、15、120、60、70。
当前磁头在50号磁道。故磁头移动道数为：
（110-50）+（180-110）+（180-32）+（115-32）+（115-15）+（120-15）+（120-60）+（70-60）=60+70+148+83+100+105+60+10=636
（2）单向扫描调度算法
该算法是沿磁头移动方向访问距离当前磁道最近的磁道，当到达一个顶端时立刻返回到另一个顶端继续扫描。本题磁头移动方向是磁道增加的方向，当前磁头在50号磁道。因此磁道的访问序列（服务顺序）就是：60、70、110、115、120、180、15、32。而磁头移动道数与前面（1）问差不多，也是两两相减，然后求和。在此略

❷ 谁能讲一下冒泡排序原理

冒泡排序算法的原理如下：

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

(2)一趟扫描算法是什么扩展阅读：

算法优化：当里面的一层循环在某次扫描中没有交换则说明此时数组已经全部有序，无需再再次扫描。

所以可以添加一个标记每交换一次就进行标记，如果某次没有没有标记就说明已经有序了

写冒泡排序可以排序多个字符串。假设对4个字符串进行排序，每个字符串不超过10个 ，那么可以把这三个字符串看成一个二维数组，这样一个一位数组的指针就可以访问该数组，然后根据冒泡排序的原理就可以排序了。

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。

所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

❸ 常见排序算法以及对应的时间复杂度和空间复杂度

排序 ：将杂乱无章的数据，按照一定的方法进行排列的过程叫做排序。

排序大的分类可分为 内排序 和 外排序 ，不需要访问外存就能进行排序的叫做内排序。

排序也可以分为 稳定排序 和 不稳定排序

稳定排序 ：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，经过排序后 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、归并排序，基数排序都是稳定排序。
不稳定排序 ：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。

以升序为例，比较相邻的元素，如果第一个比第二个大，则交换他们两个。如果两个元素一样大，则继续比较下一对。所以冒泡排序是一种稳定排序。

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。快速排序是不稳定排序。

将序列分为两个部分{{有序序列},{无序}}，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。如果碰到相等的元素，就会把它插入到想等元素后面，顺序不会改变，所以直接插入排序是稳定排序。

在直接插入排序的基础上，对有序序列进行划分。例如：序列为 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 为有序序列，取 a[(i-1)/2] ，将其与 a[i] 比较，即可确定 a[i] 的范围 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然后继续在已确定的范围内进行二分。范围依次缩小为： 1/2、1/4、1/8、1/16...... 可快速确定a[i]应该插入的位置。二分插入排序也是稳定排序。

将整个序列分割成若干个小的子序列，每个子序列内分别进行插入排序。一般情况下步长取n/2。直到最后一次步长为1，即所有元素在一个组中进行排序。由于希尔排序是先将整个序列划分为多个子序列进行排序，相同的元素顺序在这个过程中顺序可能会被打乱，所以希尔排序是不稳定排序。

从待排序的数据元素中，选出最小或最大的元素与序列第一个数交换。直到所有数据排完。直接选择排序是不稳定排序。例如： {3，3，1} ，第一次排序就将1和第一个3交换，想等元素的顺序改变了。

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

堆排序是一种树形选择排序，是对直接选择排序的有效改进。
最大堆:每个节点的值都大于等于它的孩子节点。
最小堆:每个节点的值都小于等于它的孩子节点。
最大堆第0个数据是最大数，最小堆第0个数据是最小数。
堆排序是不稳定排序

思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
如何将两个有序序列合并？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]<a[0] ，取 b[0] 放入数组 c 中，然后继续比较数组 a 和 b 中的第一个元素，直到数组 a 和 b 中最后一对元素比较完成。

思想

将数组分成二组 a , b 如果这二组组内的数据都是有序的，那么就可以按照上述方法对这二组数据进行排序。如果这二组数据是无序的？
可以将 a , b 组各自再分成二组。递归操作，直到每个小组只有一个数据，每个小组只有一个元素所以我们可以认为它已经是有序序列，然后进行合并。
先分解后合并。
归并排序是稳定排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。从最低位起从0-9依次扫描序列，一边扫描一边将扫描到的数据加到新的序列中，得到一个序列。然后比较高一位，重复上述操作，直到最高位排序完成。数列就变成一个有序序列。基数排序是稳定排序。

以全是二位数的序列举例

无限猴子定理 :指一只猴子随机在打字机键盘上按键，最后必然可以打出法国国家图书馆的每本图书。

时间复杂度最低1次，最高可执行到世界的尽头。。。

❹ 目前常用的磁盘调度算法有哪几种每种算法优先考虑的问题是什么

(1)先来先服务(FCFS，First-Come First-Served)
此算法根据进程请求访问磁盘的先后次序进行调度。
(2)最短寻道时间优先(SSTF ，ShortestSeekTimeFirst)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3)扫描(SCAN)算法
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
(4)循环扫描(CSCAN)算法
CSCAN算法规定磁头单向移动，避免了扫描算法导致的某些进程磁盘请求的严重延迟。
(5) N-Step-SCAN和FSCAN调度算法
1) N-Step-SCAN算法。为克服前述SSTF、SCAN、CSCAN等调度算法都可能出现的磁臂停留在某处不动的情况即磁臂粘着现象，将磁盘请求队列分成若干个长度为N的子队列，按先来先服务算法依次处理这些子队列，而各队列分别以扫描算法进行处理。
2) FSCAN算法
FSCAN算法实质上是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个队列则是在 扫描期间，新出现的所有请求磁盘I/O进程的队列，放入另一等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。

❺ 排序算法的时间复杂度如何

排序算法的时间复杂度是若文件的初始状态是正序的，一趟扫描即可完成排序。

比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

次线性时间

对于一个算法，若其匹配T(n) = o(n)，则其时间复杂度为次线性时间（sub-linear time或sublinear time）。实际上除了匹配以上定义的算法，其他一些算法也拥有次线性时间的时间复杂度。例如有O(n)葛罗佛搜索算法。

常见的非合次线性时间算法都采用了诸如平行处理（就像NC1matrix行列式计算那样）、非古典处理（如同葛罗佛搜索那样），又或者选择性地对有保证的输入结构作出假设（如幂对数时间的二分搜索）。

不过，一些情况，例如在头 log(n) 比特中每个字符串有一个比特作为索引的字符串组就可能依赖于输入的每个比特，但又匹配次线性时间的条件。

“次线性时间算法”通常指那些不匹配前一段的描述的算法。它们通常运行于传统计算机架构系列并且不容许任何对输入的事先假设。但是它们可以是随机化算法，而且必须是真随机算法除了特殊情况。

❻ 从n个数中取出m个最大的最好的算法是什么

有很多算法，复杂度也不尽相同。以下简单举几个例子：
1. n×m遍扫描
【算法基本描述】n×m遍扫描
【算法思想】每次都扫描一遍数组，取出最大元素，这样扫描m遍就能得到m个最大的数
【算法复杂度】O(nm)

2.排序后取最大m个数
【算法基本描述】对n个数排序，对拍完序后的序列取m个最大的数
【算法复杂度】视排序的复杂度，一般为O(nlogn)或O(n^2)

3.最小堆
【算法基本描述】一遍扫描+最小堆
【算法伪代码】
00-建立一个最小堆（优先队列），最小堆的大小控制在m之内
01-for 每个数：
02-----if 这个数比最小堆的堆顶元素大：
03---------弹出最小堆的最小元素
04---------把这个数插入到最小堆
05-最小堆中的m个元素就是所要求的元素
06-其中最小堆的作用就是保持里面始终有m个最大元素，且m个元素中最小的元素在堆顶。
【算法复杂度】O(nlogm) 遍历O(n) 最小堆O(logm)
【其他】如果要求n个数中取最小的m个，只要把算法反一下即可

总结：当n与m差不多大时，采用复杂度较低的排序是比较可取的，因为简单。当m<<n时，排序是很浪费时间的，因为我们不需要后(n-m)个数，所以可以采用最小堆的方法。
我不敢说我的算法是最好的，但是它一定是一个复杂度较低的算法。