一、考点

1、冒泡排序原理和实现

1）原理

两两相邻的数进行比较，如果反序就交换，否则不交换。

2）实现

1， 3， 2， 4， 6， 5，进行冒泡排序。

步骤如下：

第一轮：拿 1，3，进行比较，1 < 3，因此位置不变，第一轮得到 1，3，2，4，6，5；

第二轮：拿 3， 2，进行比较，3 > 2，因此交换位置，第二轮得到 1，2，3，4，6，5；

第三轮：拿 3， 4，进行比较，3 < 4，因此位置不变，第三轮得到 1，2，3，4，4，6，5；

第四轮：拿 4， 6，进行比较，4 < 5，因此位置不变，第四轮得到 1，2，3，4，6，5；

第五轮：拿 6， 5，进行比较，6 > 5，因此交换位置，第五轮得到1，2，3，4，5，6。

冒泡排序最终结果：1，2，3，4，5，6

2、延伸

1）算法的概念

1 + 2 + 3 + 4 + … + n 的值是多少？

① 解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作；

② 一个问题可以有多种算法，每种算法都不同的效率；

如： 1 + 2 + 3 + 4 + … + n的值，这道题，可以进行改进一下，不要直接加，直接加的效率很低。可以采用 梯形的面积算法（ (上底 + 下底) x 高 / 2），用到此题中，为 (1 + n) * n/2，即最终结果为 n(n+1)/2，这样效率就会提高很多。

③ 一个算法具有五个特征

• 有穷性：有结束的时候。
• 确切性：每一步都是有意义的（不能随便写一步没有意义的）。
• 输入项：如一个算法有100项，则从1加到100这样的值。
• 输出项：最终要给一个结果。
• 可行性：算法的每一步都是正确的，可以执行。

2）时间复杂度和空间复杂度的概念

① 算法评定

• 算法分析的目的在于选择合适算法和改进算法；
• 一个算法的评价主要从 时间复杂度 和 空间复杂度 来考虑。

② 时间复杂度

• 执行算法所需要的计算工作量。一般来说，计算机算法是 问题规模 n 的函数 f(n)，算法的时间复杂度也因此记做 T(n)=O(f(n));
• 问题的规模n 越大，算法执行的时间的增长率 与 f(n) 的增长率 正相关，称作 渐进时间复杂度（Asymptotic Time Complexity），简称 时间复杂度。

③ 时间复杂度计算方式

<1> 得出算法的计算次数的公式；；

// 1 + 2 + 3 + ... + n
$sum = 0;
for ($i = 1; $i <= $n; $i++) {
    $sum += $i;
}
// 计算了 n次，则 时间复杂度：O(n)，因此 时间复杂度

<2> 用 常数1 来取代所有时间中的所有加法常数；（如：假设我们的计算次数为 3，或者是其他的固定常数，都要写成 O(1)，不能写成 O(3)，因此，凡固定常数的次数，都写成 O(1)。）；

<3> 在修改后的运行次数函数中，只保留最高阶项；

<4> 如果最高阶存在且不是1，则去除与这个项相乘的常数（如：计算出来的是 2n^2 + 3n + 1，则时间复杂度为 O(n^2)，只拿最高阶即可，不用管前面的常数）

④ 举例

• 常数阶：O(1) ：无论常数为几，都替换为1。

• 线性阶：O(n) ：从 1 加到 n。
• 平（立）方阶：O(n^2)/O(n3)

• 特殊平方阶：O(n^2/2+n/2) -> O(n^2)

• 对数阶：O(log2n)

常见时间复杂度：常数阶、线性阶、平方阶、立方阶、对数阶、nlog2n阶、指数阶。

效率比较：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)

注：综上所述，值越小，效率越高。

⑤ 时间复杂度其他概念

• 最坏情况：最坏情况时的运行时间，一种保证，如果没有特别说明，说的时间复杂度即为最坏情况的时间复杂度。
• 平均情况：期望的运行时间。

⑥ 空间复杂度

• 算法需要消耗的内存空间，记作 S(n) = O(f(n))；
• 包括 程序代码所占用的空间，输入数据所占用的空间 和 辅助变量所占用的空间 这三个方面；
• 计算和表示方法与时间复杂度类似，一般用 复杂度的渐近性 来表示。

⑦ 空间复杂度计算方式

• 有时用空间换取时间；
• 冒泡排序的元素交换，空间复杂度 O(1)

3）常见排序算法

① 冒泡排序；

• 原理：两两相邻的数进行比较，如果反序就交换，否则不交换。
• 时间复杂度：最坏(即比较次数最多的情况)(O(n^2))，平均 (O(n^2))。
• 空间复杂度：O(1)

② 直接插入排序；

• 原理：每次从无序表中去取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
• 时间复杂度：最坏（O(n^2)），平均（O(n^2)）
• 空间复杂度：O(1)

③ 希尔排序；

• 原理：把待排序的数据根据增量分成几个子序列，对子序列进行插入排序，直到增量为1，直接进行插入排序；增量的排序，一般是数组的长度的一般，再变为原理增量的一半，直到增量为1。
• 时间复杂度：最差（O(n^2)），平均（O(n*log2n)）
• 空间复杂度：O(1)

④ 选择排序；

• 原理：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
• 时间复杂度：最坏（O(n^2)），平均（O(n^2)）
• 空间复杂度：O(1)

⑤ 快速排序；

• 原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归完成。（把数据中中间劈开，使用递归分别进行排序，然后再进行比较这两部分的大小）。
• 时间复杂度：最差（O(n^2)），平均（O(nlog2n)）【相当来说，不稳定】
• 空间复杂度：最差（O(n)），平均（O(log2n)）

⑥ 堆排序

• 原理：把待排序的元素按照大小在二叉树位置上排列，排序好的元素要满足：父节点的元素要大于等于子节点；这个过程叫做 堆化过程，如果根节点存放的是最大的数，则叫做大根堆，如果是最小，就叫小根堆，可以把根节点拿出来，然后再堆化，循环到最后一个节点。
• 时间复杂度：最差（O(nlog2n)），平均（O(nlog2n)）
• 空间复杂度：O(1)

⑦ 归并排序

• 原理：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。
• 时间复杂度：最差（O(nlog2n)），平均（O(nlog2n)）
• 空间复杂度：O(n)

总结：快速排序、归并排序的理想时间复杂度都是 O(nlog2n)，但是快速排序的时间复杂度并不稳定，最坏情况下复杂度为 O(n^2)，所以最理想的算法还是归并排序。

常考题：以下算法中哪个的效率更快？（如果有 归并排序 优先选择，没有的话，选择 快速排序）

4）常见查找算法

① 二分查找【常考】

• 原理：从数组的中间元素开始，如果中间元素正好是要查找的元素，搜索结束，如果某一个特定元素大于或者小中间元素，则在数组大于或者小于中间元素的那一半中查找，而且跟开始一样从中间开始比较，如果某一步骤数组为空，代表找不到。
• 时间复杂度：最差（O(log2n)），平均（O(log2n)）
• 空间复杂度：迭代（O(1)）、递归（O(log2n)）

② 顺序查找

• 原理：按照一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。
• 时间复杂度：最差（O(n)），平均（O(n)）
• 空间复杂度：O(1)

总结：二分查找算法的时间复杂度最差是 O(log2n)，顺序查找的时间复杂度最差为 O(n)，所以二分查找法更快，但是递归情况下，二分查找更消耗内容，时间复杂度为 O(log2n)。

二、解题方法

此类考点非常重要也较为复杂，需要大家充分理解各种排序算法和查找算法的原理以及实现方式，另外还需要理解时间复杂度和空间复杂度的计算方式和概念，此类考察点毋庸置疑是考察大家的逻辑思维能力，因此需要大家仔细研究各种算法的实现方式。

三、真题

1、请简述时间复杂度和空间复杂度的概念。

• 时间复杂度：用来描述时间的消耗计算量；
• 空间复杂度：内存的计算量（使用到的内存）。

2、对无须数组排序，最优的时间复杂度是什么，用PHP或者JavaScript写出一个实际的例子（如了解，给出算法的名称），该算法的空间复杂度是什么？

• 可以写 归并排序 或者 快速排序。

3、一个有序数组中，查询特定item是否存在的最优算法是什么？时间复杂度是什么？

• 最优算法：二分查找法
• 二分查找法 时间复杂度：O(log2n)