变化形式

减去一个常量
减去一个常量因子
减去的规模是可变的

插入排序

O(n^2)

理解

要将n个数据排序，那么就要将n-1个数排序……如此。

伪代码

  1. for i<-1 to n-1 do
  2.     v<-A[i]
  3.     j<-i-1
  4.     while j>=0 and A[j]>v do
  5.         A[j+1]<-A[j]
  6.         j<-j-1
  7.     A[j+1]<-v

拓扑排序

使用有向无环图来指明事件的优先次序。也就是将图的所有节点在一条水平线上排开，形成拓扑序列。

减治（减一）法

理解

每次从头找入度为0的点，删去，再找下一个，直到找完。

深度搜索

生成全排列

将数字的所有可能的排列列出

减治法

从低到上去排列。生成的不是字典排列（不是从小到大）

茶托方法

移动数字

伪代码

  1. 将第一个排列初始化为

生成子集

n个元素所形成的集合的所有子集

减治法

前一个生成的子集保留下来，再去生成新的子集

扩展

将子集表达为比特串。元素存在为1，不存在为0

生成二进制反射格雷码

根据规律一层一层处理
n位Gray码={（n-1）位Gray码，在第n位填0或1；0或1}

伪代码

假币问题

有n个外观完全相同的硬币，其中1个是假币，其他n-1个的重量完全一样，假币较轻。求用一个天平，称几次可以找出假币

折半查找

寻找中位数

伪代码

  1. //输出K对应值的下标
  2. l<-0;r<-n-1;
  3. while l<=r do
  4.     m<-[(l+r)/2]
  5.     if K=A[m] return m
  6.     else if K<A[m] r<-m-1
  7.     else l<-m+1
  8. return -1

约瑟夫斯问题

n个人围成一圈，编号从1~n；从第一个人开始喊口号，只喊1和2，喊2的人淘汰直到只有1个人为止。求编号。
不考虑编号时：奇数：f(n)=f(2n+1) 偶数：f(n)=f(2n)

减治法

以喊到2则淘汰为例：
格式：人数(n) 获胜者编号(0-n-1)
1 0
2 0
3 2
4 0
5 2
6 4
7 6
8 0
总结出规律：n个人的获胜者编号=（n-1个人的获胜者编号+2）mod n
那么递归函数：f[n]=(f[n-1]+2) mod n; f[1]=0

程序代码

  1. int win(int n,int f)
  2. {
  3.     if (n == 1)
  4.         return 0;
  5.     return (win(n - 1, f) + f) % n;
  6. }

减可变规模算法

计算中值和选择问题

中值问题：求中间值
选择问题：n个数，求第k个最小元素问题

Lomuto划分

O(nlog(n))

伪代码

  1. //用第一个元素作为中轴对子数组进行划分
  2. //input：数组A[0...n-1]的一个子数组A[l...r]
  3. //output：A[l..r]的划分和中轴的新位置
  4. p<-A[l]
  5. s<-l
  6. for i<-l+1 to r do
  7.     if A[i]<p
  8.         s<-s+1;swap(A[s],A[i])
  9. swap(A[l],A[s])
  10. return s

例：
p124

插值查找

二叉查找树的查找和插入

NIM博弈

n堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后意见物品着获胜。

以3 4 5为例：
将每堆的堆数分解为二进制数：011 100 101；
一位位分析：第一位有2个1，第二位有1个1，第三位有2个1（异或后就会只剩下第二位的1）
先手可以在后手选择时，保持剩余的1的数量为偶数
那么此时不论后手怎么拿，都不会是最后拿走的人。
然而异或操作可以看做是：判断单个位中1的个数，偶数个为0，奇数个为1
那么问题就变为：一些二进制数，异或后，为0先手输，为1先手赢。