算法的基础知识是软件评测师考试的重要考点，经常出现在上午场的客观选择题当中。算法是问题求解过程的精确描述，它为解决某一特定类型的问题规定了一个运算过程，算法实质上是特定问题的可行的求解方法、规则和步骤。下面就该知识点并结合例题进行总结学习。
一、算法的时间复杂度和空间复杂度
（1）时间复杂度
时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。对于一个算法的时间开销T(n)，从数量级大小考虑，当n增大到一定值后，T(n)计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都可以忽略，即采用渐进分析，表示为T(n)=O(f(n))。其中，n反映问题的规模，T(n)是算法运行所消耗时间的总量， O是数学分析中常用的符号“大O”，而f(n)是自变量为n的某个具体的函数表达式。例如，若f(n)=n^2+2n+1，则时间复杂度T(n)=O(n^2)。
时间复杂度的三种情况分析：
1）最佳情况：使算法执行时间最少的输入。一 般情况下，不进行算法在最佳情况下的时间复杂度分析。
2）最坏情况：使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它给我们提供一个保障，实际情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且对于许多算法来说，平均情况通常与最坏情况下的时间复杂度一样。
3）平均情况：我们都知道，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的时间复杂度，需要进入一个新的概念：平均情况时间复杂度，后面简称平均时间复杂度。平均情况的时间复杂度要考虑每一种输入及其该输入的概率。
（2）空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。反映的是一个趋势，我们用S(n)来定义。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)等。例如：
（1）inta= 1;
int b = 2;
a++;
b++;
int c = a + b;
代码中的 a、b、c 所分配的空间都不随着处理数据量变化，因此它的空间复杂度S(n)= O(1)；
（2）int[ ] m = new int[n]；
for(i=1; i<=n; ++i) {
j= i;
j++;
}
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码后面虽然有for循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即S(n)= O(n)。
二、常见的8种排序算法
经过排序，如果a原本在b前面，而a=b，排序之后a仍然在b的前面，我们就说该算法是稳定的；如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面，我们就说该算法是不稳定的。常见的8种排序算法如下所示：
（1）直接插入排序：算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。实现步骤：
1）从第一个元素开始，该元素可以认为已经被排序；
2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
4）重复步骤3），直到找到已排序的元素小于或者等于新元素的位置；
5）将新元素插入到该位置后；
重复步骤2）~5）。
平均时间复杂度：O(n^2)；
稳定性：稳定。
（2）Shell（希尔）排序：希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。
平均时间复杂度：O(n^1.3)；
稳定性：不稳定。
（3）直接选择排序：一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。实现步骤：
n个记录的直接选择排序可经过n-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趟结束，数组有序化了。
平均时间复杂度：O(n^2)；
稳定性：不稳定。
（4）堆排序：是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。算法描述：
1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
平均时间复杂度：
稳定性：不稳定。
（5）冒泡排序：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。实现步骤：
1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3）针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1）~3），直到排序完成。
平均时间复杂度：O(n^2)；
稳定性：稳定。
（6）快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。算法描述：
1）从数列中挑出一个元素，称为 “基准”；
2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
3）递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
平均时间复杂度：
稳定性：不稳定。
（7）归并排序：建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。算法描述：
1）把长度为n的输入序列分成两个长度为n/2的子序列；
2）对这两个子序列分别采用归并排序；
3）将两个排序好的子序列合并成一个最终的排序序列。
平均时间复杂度：
稳定性：稳定。
（8）基数排序：按照低位先排序，然后收集；再按照高位排序，然后再收集；以此类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。算法描述：
1）取得数组中的最大数，并取得位数；
2）arr为原始数组，从最低位开始取每个位组成radix数组；
3）对radix进行计数排序（利用计数排序适用于小范围数的特点）。
平均时间复杂度：
稳定性：稳定。
三、8种排序算法的时间复杂度和空间复杂度汇总表
下面是近几年对该知识点考察过的真题，以后仍是考试出题的重点，大家要重视起来。
【2017年第40-41题】给定包含n个正整数的数组 A和正整数 x，要判断数组 A中是否存在两个元素之和等于x，先用直接插入排序算法对数组A进行排序，再用以下过程P来判断是否存在两个元素之和等于x。
low=1;
high=n;
while（high>low）
if A[low]+A[high]==x return true;
else if A[low]+A[high]>x low++;
else high--;
return false;
则过程 P的时间复杂度为（1），整个算法的时间复杂度为（ 2）。
（1）
A、O(n)
B、O(nlgn）
C、O(n²)
D、O(n²lgn)
（2）
A、O(n)
B、O(nlgn)
C、O(n²)
D、O(n²lgn)
解析：本题考查算法时间复杂度的基本知识。
（1）有一层循环while，遍历判断，所以时间复杂度为n；
（2）如下图所示：直接插入排序的时间复杂为O(n²) ;
故正确答案为：（1）A（2）C
【2018年第26题】通过设置基准(枢轴)元素将待排序的序列划分为两个子序列，使得其一个子序列的元素均不大于基准元素，另一个子序列的元素均不小于基准元素，然后再分别对两个子序列继续递归地进行相同思路的排序处理，这种排序方法称为（）。
A、快速排序
B、冒泡排序
C、简单选择排序
D、归并排序
解析：本题考查排序方法的基础知识。
本题考察的就是快速的基本概念。快速排序通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。算法描述：
1）从数列中挑出一个元素，称为 “基准”；
2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
3）递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
故正确答案为：A
【2019年第25题】对n个关键码构成的序列采用简单选择排序法进行排序的过程是：第一趟经过n-1次关键码之间的比较，确定出最小关键码在序列中的位置后，再将其与序列的第一个关键码进行交换，第二趟则在其余的n-1个关键码中进行n-2次比较，确定出最小关键码的位置后，再将其与序列的第二个关键码进行交换······以此类推，直到序列的关键码从小到大有序排列。在简单选择排序过程中，关键码之间的总比较次数为（ ）。
A、n (n-1)/2
B、n^2/2
C、n (n+1)/2
D、nlogn
解析：本题考查排序算法的基础知识。
第一趟比较（n-1）次，第二趟比较（n-2）次，以此类推，一直到最后比较1次，最终比较的次数为1+2+3+…+（n-2）+（n-1）=n (n-1)/2。
故正确答案为：A
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2021年10月19日
作者：昊洋讲师
版权所有，侵权必究
