起始语

平时写算法的时候，很多时候思路有了，但是边界问题总是傻傻搞不清楚。所以找了一些经过千锤百炼的模版来帮助代码。持续更新中。。。

方便自己在通勤路上，记忆一下模版，所以发在了博客上。

算法基础

排序

快速排序

把每个比基准值大的值放到右边，比基准值小的值放到左边，再分别左右快速排序

void quick_sort(int q[], int l, int r) {
	if (l >= r) return;
  
  int x = q[l], i = l - 1, j = r + 1; //这里基准点l必须上取整，不然会死循环 
  // 假如是 1，2 进行快速排序，会出现排序一次后，左边界是 [0,-1]， 右边是[0,2]，会一直死循环
  while (i < j) {
    do i++; while (q[i] < x);
    do j--; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
  }
  
  quick_sort(q, l, j);
  quick_sort(q, j + 1, r);
}

归并排序

1. 确定分界点 mid = (l + r) / 2
2. 归并排序 left right
3. 归并 - 合二为一

const int N = 1000010;
int n;
int q[N], tem[N];

void merge_sort(int q[], int l, int r) {
  if (l >= r) return;
 
  int mid = l + r >> 1; // >> 运算符 优先程度和 + 相同
  merge_sort(q, l, mid);
  merge_sort(q, mid + 1, r);
  
  int k = 0, i = 1, j = mid + 1;
  while (i <= mid && j <= r) 
    if (q[i] <= q[j]) tmp[k ++] = q[i ++];
  	else tem[k ++] = q[j ++];
  while (i <= mid) tem[k ++] = q[i ++];
  while (j <= r) tem[k ++] = q[j ++];
    
  for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = tem[j];
}

二分查找

int bsearch_1(int l, int r) {
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid; //判断mid是否满足某种性质
    else l = mid + 1;
  }
  return l;
}

int bsearch_2(int l, int r) {
  while (l < r) {
    int mid = l + r + 1 >> 1; //除法是下取整，如果不加1 且 l = r - 1，那么区间[l, r]会变成区间[l, r]会进入死循环，因为 mid = l + r >> 1 = l + 1 + l >> 1 = l。所以当 l = mid 时，需要补偿 1
    if (check(mid)) l = mid; // l = mid 的话需要 + 1
    else r = mid - 1;
  }
  return l;
}