1. 排序算法总结
排序算法是什么?有多少种?排序算法总结又是怎样?以下是为您整理的排序算法总结，供您参考!
排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。
排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。
稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。
以下来总结常用的排序算法，加深对排序的理解。
冒泡排序
原理
俩俩比较相邻记录的排序码，若发生逆序，则交旅派配换;有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。
性能
时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。
优化
若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。
代码
插入排序
原理
依次选择一个待排序的数据，插入到前边已排好序的序列中。
性能
时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。
优化
直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。
折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。
使用场景
当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。
代码
希尔排拆指序
原理
插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：
插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。
但插入排序在每次往前插入时只能将数据移动一位，效率比较低。
所以希尔排序的思想是：
先是取一个合适的gap
缩小间隔gap，例如去gap=ceil(gap/2)，重复上述子序列划分和排序
直到，最后gap=1时，将所有元素放在同一个序列中进行插入排序为止。
性能
开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点;其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。
代码
选择排序
原理
每次从未排序的序列中找到最小值，记录并最后存放到已排序序羡碰列的末尾
性能
时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的(把最小值交换到已排序的末尾导致的)，每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。
代码
快速排序
原理
分而治之思想：
Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1…q]，左边的元素都比基准小，右边的元素都比基准大;
Conquer：对俩个划分的数组进行递归排序;
Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。
性能
快排的平均时间复杂度为O(NlogN)，空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N);且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。
优化
当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。
所以快排的优化思路如下：
优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。
在规模较小情况下，采用直接插入排序
代码
归并排序
原理
分而治之思想：
Divide：将n个元素平均划分为各含n/2个元素的子序列;
Conquer：递归的解决俩个规模为n/2的子问题;
Combine：合并俩个已排序的子序列。
性能
时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。
优化
优化思路：
在规模较小时，合并排序可采用直接插入;
在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。
代码
堆排序
原理
堆的性质：
是一棵完全二叉树
每个节点的值都大于或等于其子节点的值，为最大堆;反之为最小堆。
堆排序思想：
将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
依次将根节点与待排序序列的最后一个元素交换
再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
性能
时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。
使用场景
想知道最大值或最小值时，比如优先级队列，作业调度等场景。
代码
计数排序
原理
先把每个元素的出现次数算出来，然后算出该元素所在最终排好序列中的绝对位置(最终位置)，再依次把初始序列中的元素，根据该元素所在最终的绝对位置移到排序数组中。
性能
时间复杂度为O(N+K)，空间复杂度为O(N+K)，算法是稳定的，与初始序列无关，不需要进行比较就能排好序的算法。
使用场景
算法只能使用在已知序列中的元素在0-k之间，且要求排序的复杂度在线性效率上。
代码
桶排序
原理
根据待排序列元素的大小范围，均匀独立的划分M个桶
将N个输入元素分布到各个桶中去
再对各个桶中的元素进行排序
此时再按次序把各桶中的元素列出来即是已排序好的。
性能
时间复杂度为O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空间复杂度为O(N+M)，算法是稳定的，且与初始序列无关。
使用场景
算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中;可应用于数据量分布比较均匀，或比较侧重于区间数量时。
基数排序
原理
对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：
MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序
性能
时间复杂度为O(d*(N+K))，空间复杂度为O(N+K)。
总结
以上排序算法的时间、空间与稳定性的总结如下：
2. cpu调度算法决定了进程执行的顺序.若有n个进程需要调度，有多少种可能的调度顺
前两天做操作系统作业的时候学习了一下几种进程调度算法，在思考和讨论后，有了一些自己的想法，现在就写出来，跟大家讨论下。，或者说只有有限的CPU资源，当系统中有多个进程处于就绪状态，要竞争CPU资源时，操作系统就要负责完成如何分配资源的任务。在操作系统中，由调度程序来完成这一选择分配的工作，调度程序所使用的算法即是调度算法。调度算法需要考虑的指标主要有尽量保证CPU资源分配的公平性；按照一定策略强制执行算法调度；平衡整个计算机系统，尽量保持各个部分都处于忙碌状态。而根据系统各自不同的特点和要求，调度算法又有一些侧重点和目标不同，因此，算法按照系统差异主要分为三大类：批处理系统中的调度算法，代表调度算法有：先来先服务、最短作业优先、最短剩余时间优先。交互式系统中的调度算法，代表调度算法有：轮转调度、优先级调度、多级队列、最短进程优先、保证调度、彩票调度、公平分享调度。实时系统中的调度算法，代表调度算法有：速率单调调度、最早最终时限优先调度。下面就上述提到的调度算法中挑出几个进行重点分析：保证调度保证调度是指利用算法向用户做出明确的性能保证，然后尽力按照此保证实现CPU的资源分配。利用这种算法，就是定一个进程占用CPU的时间的标准，然后按照这个标准去比较实际占用CPU的时间，调度进程每次使离此标准最远的进程得到资源，不断满足离所保证的标准最远的进程，从而平衡资源分配满足这个标准的要求。保证调度算法的优点是：能很好的保证进程公平的CPU份额，当系统的特点是：进程的优先级没有太大悬殊，所制定的保证标准差异不大，各个进程对CPU的要求较为接近时，比如说系统要求n个进程中的每个进程都只占用1/n的CPU资源，利用保证调度可以很容易的实现稳定的CPU分配要求。但缺点是，这种情况太过理想，当系统的各个进程对CPU要求的紧急程度不同，所制定的保证较为复杂的时候，这个算法实现起来比较困难。彩票调度彩票调度这种算法的大意是指向进程提供各种系统资源如CPU资源的彩票，当系统需要做出调度决策时，随机抽出一张彩票，由此彩票的拥有者获得资源。在彩票调度系统中，如果有一个新的进程出现并得到一些彩票，那么在下一次的抽奖中，该进程会有同它持有彩票数量成正比例的机会赢得奖励。进程持有的彩票数量越多，则被抽中的可能性就越大。调度程序可以通过控制进程的彩票持有数量来进行调度。彩票调度有很多优点：首先，它很灵活，系统增加分给某个进程的彩票数量，就会大大增加它占用资源的可能性，可以说，彩票调度的反应是迅速的，而快速响应需求正是交互式系统的一个重要要求。其次，彩票调度算法中，进程可以交换彩票，这个特点可以更好的保证系统的平衡性，使其各个部分都尽可能的处于忙碌状态。而且利用彩票调度还可以解决许多别的算法很难解决的问题，例如可以根据特定的需要大致成比例的划分CPU的使用。速率单调调度速率单调调度算法是一种可适用于可抢占的周期性进程的经典静态实时调度算法。当实时系统中的进程满足：每个周期性进程必须在其周期内完成，且进程之间没有相互依赖的关系，每个进程在一次突发中需要相同的CPU时间量，非周期的进程都没有最终时限四个条件时，并且为了建模方便，我们假设进程抢占即刻发生没有系统开销，可以考虑利用速率单调算法。速率单调调度算法是将进程的速率（按照进程周期所算出的每秒响应的次数）赋为优先级，则保证了优先级与进程速率成线性关系，这即是我们所说的速率单调。调度程序每次运行优先级最高的，只要优先级较高的程序需要运行，则立即抢占优先级低的进程，而优先级较低的进程必须等所有优先级高于它的进程结束后才能运行。速率单调调度算法可以保证系统中最关键的任务总是得到调度，但是缺点是其作为一种静态算法，灵活性不够好，当进程数变多，系统调度变得复杂时，可能不能较好的保证进程在周期内运行。最早最终时限优先调度最早最终时限优先调度算法是一个动态算法，不要求进程是周期性的，只要一个进程需要CPU时间，它就宣布它的到来时间和最终时限。调度程序维持一个可运行的进程列表，按最终时限排序，每次调度一个最终时限最早的进程得到CPU 。当新进程就绪时，系统检查其最终时限是否在当前运行的进程结束之前，如果是，则抢占当前进程。由于是动态算法，最早最终优先调度的优点就是灵活，当进程数不超过负载时，资源分配更优，但也同样由于它的动态属性，进程的优先级都是在不断变化中的，所以也没有哪个进程是一定可以保证满足调度的，当进程数超过负载时，资源分配合理度会急速下降，所以不太稳定。