《算法设计与分析》 实验2
全排列问题
DFS的路线图：
我们不需要存这个树，每次深搜走到底就是一条路线。
回溯的过程中需要注意：恢复原样。flag[i] = false;
合并排序（归并排序）
归并排序 —— 分治思想
- 确定分界点：mid == l+r >> 1
- 递归排序 ( left —— right)
- 归并：把两个有序的数组合并成一个有序的数组(合二为一)（?）
双指针算法：
首先 a[n] 的最小值和 b[n] 的最小值进行比较，将两者的最小值输出到 tmp[数组] 当中；
假设 a[n] 的最小值 ＜ b[n] 的最小值，则a[n]的最小值输出到tmp[0]当中，那么下一步，a[n]的指针右移一步，再与b[n]的最小值进行比较，输出二者的最小值；
一直到a[n]和b[n]的一方的指针先走到该数组的最大值则停止，将另一个数组的剩余部分直接原封不动的复制到tmp[n]的末尾即可。
归并排序的时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
递归的第二层：二分针
递归的第三层：四分针
以此类推： 直到n个1
所以每层都是n的计算量，总共logn层
所以归并排序的时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)