算法的基本概念、基本特性、算法复杂度的计里方法、描述算法的三种工具(流程图、N-S盒图、过程设计语言)、穷举法、递归法、排序算法的算法思想

算法概述

算法（Agorithm）：是指对特定问题求解步骤的一种描述。或者说，算法是为求解某问题而设计的操作步骤序列。求解同样的问题，不同的人写出的算法可能是不同的。算法的执行效率与数据结构的优劣有很大的关系。

基本特征

有穷性：任何一个算法必须由有限个步骤组成，并能在有限的时间内完成。
确定性：算法的每一步必须有确切的定义，解决问题的规则必须是唯一确定的，不可以有模糊的解释和二义性。
可行性：算法的每一个操作步骤在计算机上都是能够可行的。在设计一个算法时，必须要考虑它的可行性，否则不会得到满意的结果。
输入：一个算法有 0 个或多个输入。一个算法的执行总是与输入的初始数据有关的，不同的输入会产生不同的输出结果，因此，在算法执行的过程中必须保证准确的数据输入，才会得到正确的输出结果。
输出：一个算法有一个或多个输出。

评价优劣的指标

正确性：一个算法必须正确才有存在的意义，这是最基本的指标。
可读性：算法的书写、命名等应便于阅读和交流，方便对其进行分析、修改和引用。
健壮性：在一个算法中，可能会出现不合理的数据或非法的操作，一个算法应具有对这些问题进行检查和纠正的处理能力。
效率：算法的效率主要是指执行算法时计算机资源的消耗，包括计算机内存的消耗和计算机运行时间的消耗。一个算法只有正确性而无效率是没有意义的。

算法复杂度

评价一个算法优劣的主要标准是算法的执行效率与存储需求。算法的执行效率指的是时间复杂度（Time Complexity），存储需求指的是空间复杂度（Space Complexity）。

算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，需用设置一种衡量尺度。

基本运算反映了算法运算的主要特征，用基本运算的次数来度量算法工作量是客观的，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

算法复杂度记做 T(n) = O(f(n))

[!example]
例如，当需要查找某一元素时，可以将两个元素之间的比较作为基本运算。又如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算忽略不计。

算法所执行的基本运算次数还与问题的规模有关。例如，两个 20 阶矩阵相乘与两个 10 阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数显然是不同的，前者需要更多的运算次数。因此，在分析算法的工作量时，还必须对问题的规模进行度量。

描述算法的工具

自然语言

自然语言（Natural Language）是一种描述算法时使用方便人们交流的语言逻辑来描述计算机算法的方法。自然语言描述算法的难点在于如何用简单的自然语言来表达复杂的算法，需要仔细思考每个步骤的表达方式，以及如何使用恰当的词汇和语法来传达正确的含义。

S1：输入 x。
S2：如果 x < 0，f(x) = −1。
S3：如果 x = 0，f(x) = 0。
S4：如果 x > 0，f(x) = 1。
S5：输出 f(x)的值。
S6：结束。

流程图

流程图（Flow Chart）是一种描述算法的图形化描述，用流程图可以清晰地描述出算法的思路和过程。

N-S结构化流程图

N-S图，也称为盒图。在图中没有转向的箭头，因此不允许随意转移控制，使得程序的结构更为清晰。

N-S 图有以下特征：

每个构件具有明确的功能域。
控制转移必须遵守结构化设计要求。
易于确定局部数据和（或）全局数据的作用域。
易于表达嵌套关系和模块的层次结构。

算法介绍

算法名称	介绍	时间复杂度	空间复杂度
穷举法	鸡兔同笼
递归法	计算阶乘
冒泡排序	从左往右依次进行比对，大的数将被移到右侧。	$O(n^2)$	$O(1)$
简单选择排序	选出最小的数放在最左侧，以此类推。	$O(n^2)$	$O(1)$
快速排序	选出基准数，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧	$O(n \log n)$	$O(n)$
插入排序	与手动整理一副牌的过程非常相似，从左往右将数字插入正确的位置。	$O(n^2)$	$O(1)$
归并排序	将数字拆分成组排序，然后有序序列合并。	$O(n \log n)$	$O(n)$
二分查找	每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止	$O(\log n)$	$O(1)$

穷举法

穷举法（Exhaustive Attack Method）也称为枚举法，其依赖于计算机的强大计算能力来穷尽每一种可能性，从而达到求解问题的目的。穷举算法效率不高，但是适应于一些没有规律可循的场合。

[!example]
鸡兔同笼是中国古代的数学名题之一。是这样叙述的：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？

（1）可以利用穷举法，依次取鸡的数量为numC，计算兔的数量numR ，满足条件就是解。

#include <stdio.h>

int main() {
    int a=0;
    while (a<=35) {
        a+=1;
        if (a*2+(35-a)*4==94) {
            break;
        }
    }
    printf("%d",a);
}

递归法

能够将一个问题转化为另一个新的问题，而新的问题与原问题的解法相同或类同，不同的是仅是处理的对象，而且这些对象更小且变化有规律
可以通过上述转化而使问题简化
必须有一个明确的递归出口，或递归的边界

示例：阶乘

#include <stdio.h>
long int multiplyNumbers(int n);

int main()
{
    int n;
    printf("输入一个整数: ");
    scanf("%d", &n);
    printf("%d! = %ld", n, multiplyNumbers(n));
    return 0;
}
long int multiplyNumbers(int n)
{
    if (n > 1)
        return n*multiplyNumbers(n-1);
    else
        return 1;
}

C 语言实例 – 阶乘 | 菜鸟教程

排序算法

冒泡排序

[!note]
从左往右依次进行比对，大的数将被移到右侧。

冒泡排序（bubble sort）通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

如图 11-4 所示，冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右端。

设数组的长度为 n ，冒泡排序的步骤如图 11-5 所示。

首先，对 n 个元素执行“冒泡”，将数组的最大元素交换至正确位置。
接下来，对剩余 n−1 个元素执行“冒泡”，将第二大元素交换至正确位置。
以此类推，经过 n−1 轮“冒泡”后，前 n−1 大的元素都被交换至正确位置。
仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。

冒泡排序流程

算法特性

时间复杂度为 $O(n^2)$、自适应排序：各轮“冒泡”遍历的数组长度依次为 $n - 1$、$n - 2$、$\dots$、$2$、$1$ ，总和为 $(n - 1) n / 2$ 。在引入 flag 优化后，最佳时间复杂度可达到 $O(n)$ 。
空间复杂度为 $O(1)$、原地排序：指针 $i$ 和 $j$ 使用常数大小的额外空间。
稳定排序：由于在“冒泡”中遇到相等元素不交换。

选择排序（简单选择排序）

[!note]
选择出来最小的排序到最前面。

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组的长度为 n ，选择排序的算法流程如图 11-2 所示。

初始状态下，所有元素未排序，即未排序（索引）区间为 $[0,n−1]$ 。
选取区间 $[0,n−1]$ 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
选取区间 $[1,n−1]$ 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
以此类推。经过 n−1 轮选择与交换后，数组前 n−1 个元素已排序。
仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

算法特性

时间复杂度为 $O(n^2)$、非自适应排序：外循环共 $n - 1$ 轮，第一轮的未排序区间长度为 $n$ ，最后一轮的未排序区间长度为 $2$ ，即各轮外循环分别包含 $n$、$n - 1$、$\dots$、$3$、$2$ 轮内循环，求和为 $\frac{(n - 1)(n + 2)}{2}$ 。
空间复杂度为 $O(1)$、原地排序：指针 $i$ 和 $j$ 使用常数大小的额外空间。
非稳定排序：如下图所示，元素 nums[i] 有可能被交换至与其相等的元素的右边，导致两者的相对顺序发生改变。

快速排序

快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如图 11-8 所示。

选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。

[!note] 快速排序的分治策略
哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。

算法流程

快速排序的整体流程如图 11-9 所示。

首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
然后，对左子数组和右子数组分别递归执行“哨兵划分”。
持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

快速排序流程

算法特性

时间复杂度为 $O(n \log n)$、非自适应排序：在平均情况下，哨兵划分的递归层数为 $\log n$ ，每层中的总循环数为 $n$ ，总体使用 $O(n \log n)$ 时间。在最差情况下，每轮哨兵划分操作都将长度为 $n$ 的数组划分为长度为 $0$ 和 $n - 1$ 的两个子数组，此时递归层数达到 $n$ ，每层中的循环数为 $n$ ，总体使用 $O(n^2)$ 时间。
空间复杂度为 $O(n)$、原地排序：在输入数组完全倒序的情况下，达到最差递归深度 $n$ ，使用 $O(n)$ 栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

快速排序为什么快

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。

出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 $O(n^2)$ ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 $O(n \log n)$ 的时间复杂度下运行。
缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

插入排序

插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。
具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
图 11-6 展示了数组插入元素的操作流程。设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。

图 11-6 单次插入操作

算法流程

插入排序的整体流程如图 11-7 所示。

初始状态下，数组的第 1 个元素已完成排序。
选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。

算法特性

时间复杂度为 $O(n^2)$、自适应排序：在最差情况下，每次插入操作分别需要循环 $n - 1$、$n-2$、$\dots$、$2$、$1$ 次，求和得到 $(n - 1) n / 2$ ，因此时间复杂度为 $O(n^2)$ 。在遇到有序数据时，插入操作会提前终止。当输入数组完全有序时，插入排序达到最佳时间复杂度 $O(n)$ 。
空间复杂度为 $O(1)$、原地排序：指针 $i$ 和 $j$ 使用常数大小的额外空间。
稳定排序：在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序。

插入排序的优势

插入排序的时间复杂度为 $O(n^2)$ ，而我们即将学习的快速排序的时间复杂度为 $O(n \log n)$ 。尽管插入排序的时间复杂度更高，但在数据量较小的情况下，插入排序通常更快。

这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 $O(n \log n)$ 的算法属于基于分治策略的排序算法，往往包含更多单元计算操作。而在数据量较小时，$n^2$ 和 $n \log n$ 的数值比较接近，复杂度不占主导地位，每轮中的单元操作数量起到决定性作用。

实际上，许多编程语言（例如 Java）的内置排序函数采用了插入排序，大致思路为：对于长数组，采用基于分治策略的排序算法，例如快速排序；对于短数组，直接使用插入排序。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 $O(n^2)$ ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
选择排序在任何情况下的时间复杂度都为 $O(n^2)$ 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。
选择排序不稳定，无法应用于多级排序。

归并排序

归并排序（merge sort）是一种基于分治策略的排序算法，包含图 11-10 所示的“划分”和“合并”阶段。

划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

算法流程

如下图所示，“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。

计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right] ）。
递归执行步骤 1. ，直至子数组区间长度为 1 时终止。

“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。

后序遍历：先递归左子树，再递归右子树，最后处理根节点。
归并排序：先递归左子数组，再递归右子数组，最后处理合并。

归并排序的实现如以下代码所示。请注意，nums 的待合并区间为 [left, right] ，而 tmp 的对应区间为 [0, right - left] 。

算法特性

时间复杂度为 $O(n \log n)$、非自适应排序：划分产生高度为 $\log n$ 的递归树，每层合并的总操作数量为 $n$ ，因此总体时间复杂度为 $O(n \log n)$ 。
空间复杂度为 $O(n)$、非原地排序：递归深度为 $\log n$ ，使用 $O(\log n)$ 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 $O(n)$ 大小的额外空间。
稳定排序：在合并过程中，相等元素的次序保持不变。

二分查找

二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

[!question]
给定一个长度为 n 的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回 −1 。示例如图 10-1 所示。

二分查找流程

时间复杂度为 $O(\log n)$ ：在二分循环中，区间每轮缩小一半，因此循环次数为 $\log_2 n$ 。
空间复杂度为 $O(1)$ ：指针 $i$ 和 $j$ 使用常数大小空间。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

CS基地班 4. 算法基础

算法概述

基本特征

评价优劣的指标

算法复杂度

描述算法的工具

自然语言

流程图

N-S结构化流程图

算法介绍

穷举法

递归法

排序算法

冒泡排序

算法特性

选择排序（简单选择排序）

算法特性

快速排序

算法流程

算法特性

快速排序为什么快

插入排序

算法流程

算法特性

插入排序的优势

归并排序

算法流程

算法特性

二分查找