直接插入 好O(n) 均O(n²) 坏O(n²)  辅O(1) 稳定

直接选择  O(n²)   O(n²)    O(n²)    O(1) 不稳

冒泡排序  O(n)    O(n²)    O(n²)    O(1) 稳定

希尔排序 ―――   O(n^1.25)              不稳  缩小增量排序

快速排序  O(nlogn) O(nlogn) O(n²) O(nlogn)不稳后往前找小交换

堆排序    O(nlogn) O(nlogn) O(nlogn) O(1) 不稳

归并排序  O(nlogn) O(nlogn)O(nlogn) O(1) 稳定 两两排序归并

基数排序 O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd) 稳定r=10,d位数

 

 

 

    四个特征：并发、共享、虚拟性、不确定性。五大管理功能：进程、文件、存储、设备、作业管理。运行、就绪、阻塞。

    操作系统内核包含支撑功能（中断处理、时钟管理、原语操作）、资源管理功能（进程、存储、设备管理）。引起阻塞的原因：启动某个IO操作、新数据尚未到底、无新工作可作。互斥临界区的管理原则：有空则进、无空等待、有限等待、让权等待。信号量机制有整型信号量、记录型、信号量集机制。公用信号量：实现互斥，等于临界资源数目；私用信号量实现同步。P（－1）V（＋1）。进程的高级原语通信的类型有：共享存储系统、消息传递系统、管道通信。管程实现同步机制的基础是条件结构。

    进程调度：三级调度 高级调度（长调度、作业调度、接纳调度）、中级调度（对换调度）、低级调度（进程调度）。调度方式：先来先服务、时间片轮转、优先级调度、多级反馈调度算法。优先级的确定：I/O型最高优先级、计算型进程 减少调度次数、主要是CPU处理的进程、为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时降低优先级。

    死锁产生的原因：资源竞争及进程推进顺序非法。产生死锁的四个必要条件：互斥条件、请求保持、不可剥夺条件、环路条件。死锁的处理：鸵鸟政策、预防政策（静态分配法、资源有序分配法）、避免政策（安全状态和银行家算法）、检测与解除死锁。

    线程也称为轻型进程：目的是提高系统内程序并发程度、提高吞吐量。线程作为调度和分配的基本单位，基本不拥有资源；进程作为独立分配资源的单位。线程可以创建线程，同一进程有多个线程。

    存储管理的功能：主存的分配和回收、提高主存的利用率、存储保护、主存扩充。可变分区的四种算法：最佳适应（保留最大空白区）、最差适应（不易产生碎片）、首次适应（最易合并相邻空白区）、循环首次适应。解决碎片的方法是拼接即紧凑。地址重定位是逻辑地址被转成主存物理地址的过程。可重定位分区是解决碎片问题的简单有效的方法。

    分页存储管理：页表的作用是实现从页号到物理块号的地址映射。地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成主存中的物理地址。快表：硬件实现，有一组联想高速存储器组成。两级页表机制：外层页表即页目录存放页表的物理地址，内层页表页的物理块号。

    分段存储管理：便于编程、分段共享、分段保护、动态链接、动态增长。段页式存储管理。

    虚拟存储管理：根据程序运行局部性原理，具有请求调入和置换功能；特征：离散性、多次性、对换性、虚拟性。请求分页的硬件支持：缺页中断特点：在指令执行期间产生和处理（一般中断在后）、返回时回到该指令的开始重新执行该指令（一般中断回到下一条）、一条指令可产生多次缺页中断。虚拟存储的页面置换算法 减少抖动颠簸：最佳置换、先进先出FIFO、最近最久未使用LRU、最近未用算法NUR。

    工作集：驻留内存，是进程集合。

    设备管理：目标提高设备利用率。I/O系统组成：设备、控制器、通道、总线、I/O软件。块设备（磁盘）：传输率高、可寻址、DMA方式。字符设备（终端、打印机）：传输率低、不可寻址、中断方式。中速（各种打印机）高速设备（磁带磁盘光盘）。设备管理的主要技术：中断技术、DMA、通道、缓冲技术。

    I/O软件的目的是设备独立性和统一命名。分四层：中断处理程序、设备驱动程序、与设备无关的系统软件（功能统一接口、设备命名、保护、缓冲、错误处理、存储分配释放）、用户级软件（I/O调用、格式化I/O、Spooling）。

    通道：目的是使数据独立于CPU。字节多路通道、数组选择通道、数组多路通道。

    DMA技术：指主存与I/O设备间直接成块传送，只需CPU启动信号，不需CPU干涉。缓冲技术：目的提高外设利用率，解决CPU与IO速度不匹配、减少中断频率放宽中断相应时间的限制、提高CPU与IO的并行。Spooling假脱机技术使独占设备变成多台虚拟设备，由预输入程序、缓输出技术、井管理程序、输入输出井组成。磁盘调度目标是使平均寻道时间最短。

    常见文件系统FAT32 NTFS HPFS VXT2 VFAT。文件控制块FCB是由基本信息（名、物理地址）、存取控制信息、使用信息组成。FCB的集合称为目录。磁盘分配表是外存空闲空间管理的数据结构。空闲空间管理方法有空闲区表、位示图、空闲块链、成组链接法。文件共享：硬链接ln 名 新名、软链接ls –s。

    作业 由程序、数据、作业说明书组成。作业的四种状态：提交、后备、执行、完成。作业调度算法：先来先服务、短作业先服务、相应比高优先、优先级调度、均衡调度算法。

    网络操作系统：有三类集中式、客户服务器模式、对等模式。常见：NT 、Unix、 SunOS、 Hpox、 aix、 linux。嵌入式操作系统：微型化、可定制、实时性、可靠性、易移植性（硬件抽象层HAL屏蔽了硬件平台的差异），常见：Win CE 、VxWorks、pSOS、 Palm OS 、C/OS-

    Unix采用三级索引、四种寻址方式。文件系统布局：引导块、超级块、索引结点区、数据存储区。进程控制语句：Fork创建、Exec执行、Exit结束、Signal相应事件、Kill发送软中断信号。进程调度采用动态优先数调度算法。采用分页式虚拟存储机制，二次机会页面替换算法。文件系统与设备驱动程序的接口通过设备开关表控制。正则表达式符号：.任意字符 *前一字符的多次出现 []选一个 ^否定 $行尾 \转义符  “”忽视特殊字符 \<字首匹配  \>字尾匹配。SHELL变量：IFS分割符 LOGNAME、$0本程序名 $#参数个数、$*所有位置参数、$@双引号内保持不变、$?上一命令的返回码、$$当前命令的进程、$!最近后台进程号、$-Shell标识位组成的字符串。

    Win2000系统：用户态即目态只能执行特权指令，核心态即管态可执行任何指令并改变状态。四类进程：系统支持进程、服务进程、环境子系统、应用程序。子系统动态链接库是服务进程和应用进程和系统交互的凭借。NTFS使用64位簇进行索引。进程对象属性包括进程标识、资源访问令牌、进程的基本优先级。采用二级页表结构来转换物理地址和虚拟地址。IO设备虚拟界面，将所有读写数据看成送往虚拟文件的字节流。体系结构分三层：IO系统层、设备驱动层、硬件抽象层HAL。

    DBMS特点：①数据结构化且统一管理，②有较高的数据独立性，③数据控制功能：安全性、完整性、并发控制（带来的数据不一致性有三类：丢失更新、不可重复读、读脏数据）、故障恢复（事务内部故障、系统、介质、病毒）

    三级模式：①内模式 存储模式：数据物理格式存储方式描述、②模式 概念模式：数据逻辑结构及联系描述、③外模式即用户模式 子模式。

    两级映射：模式到内模式（数据的物理独立性）、外模式到模式（数据的逻辑独立性）

    目或度n:R上的n元关系，元数：属性的个数，基数：元组的个数记录数，候选码：唯一标识一个元组，主码：关键字，主属性：全部候选码，全码：所有属性都是