一些说在前面的要点

• 稳定性
  • 在我们以下学过的排序算法中，只有选择排序和快速排序不是稳定的。
  • 稳定性，就是有两个相同的数字，在排序后两个数字的相对位置不变。（前面的在前面，后面的在后面）
• 逆序对
  • 前面的一个数字大于后面一个数字，这就叫做逆序对。
  • 例如 $5\ 1\ 2\ 3\ 4$ 中，有 $4$ 对逆序对。

结构体

结构体使用 struct 关键字定义。对于目前的我来说，没什么要记的。例如：

struct test {
    int val, num;
}a;
a.val;

二分的意义

优化。顾名思义，将一整个有序的数列分成两个部分，不断缩小边界，查找某个数字。
二分的时间复杂度为 $O(log\ 2\ n)$ 。

此时，我们学的还是整数二分以及浮点二分。

整数二分的两个模板

二分的前提是这个序列是有序的，也就是单调递增的。
一般来说，二分会取中间值进行初始化，再判断这个中间值是否大于目标值。若是，则缩减左边界，否则缩减右边界。直至逼近答案。
说“逼近”，是因为有时查找的元素不存在于序列中，那所二分出的答案是接近于的，但又是不正确的。所以要加上一个特判。除非说明给出的想查询的元素所有都是存在于序列中的。

指针的作用

指针，顾名思义，就是指向某一东西的标志。

当我们想存地址时，就可以使用指针变量：

int a ;
int *b = &a ;

b就是一个指针变量，存着a的地址。

宏定义和类型定义

宏定义，将一个指令导向另一个指令。宏定义属于预处理指令，使用规范为：

#define [标识符] [常量]