最近重刷Acwing的时候感觉对一些算法在细节上有了新的构思~故此总结。望各位大佬指出其中的纰漏。y总说过对于模板算法的态度就是记忆，但一定不是死记硬背——而是找到其中关键的记忆点，然后记忆推理逻辑和算法过程。

01-快速排序

void quickSort(int a[], int l, int r) {
    if(l >= r)  return;
    int x = a[l], i = l - 1, j = r + 1;
    while(i < j) {
      do i ++; while(a[i] < x);
      do j --; while(a[j] > x);
      if(i < j)  swap(a[i], a[j]);
    }
    quickSort(a, l, j);
    quickSort(a, j + 1, r);
}

分界点x的选择对快排算法非常关键——定义了大部分边界情况。这里选择x = a[l]为例。

• if(l >= r)

递归终止条件。y总讲课的时候提到过if(l == r)和if(l >= r)没区别，但是如果直接写if(l > r)便会出错。稍加思考就知道l == r是程序在终止前一定会到达的状态。

//if(l > r)  BUG验证样例
5
1 4 2 3 5   //Infinite loops   quickSort(a, 0, 0);

• while(i < j)

循环终止条件。

这里不能加=。因为这个循环需要确保下一层递归中l和r的合法性。如果加上=的话，那--就会多一次，会导致下一层的r变成负值——进一步的数组访问越界。

// while(i <= j)   BUG验证样例
2
1 2  //Illegal access to array      q[-3];

• while(a[i] < x)&&while(a[j] > x)

这里不能加=。 对于--操作来说，会发生非法访问。对于++操作来说，数组初始化为0则保证一直小于a[i]。

//while(a[i] <= x)  BUG验证样例
2
2 1   //Infinite loops  
//while(a[i] >= x)  BUG验证样例
2
1 2    //Illegal access to array  

• if(i < j)

这里没什么问题。

• quickSort(a, l, j);quickSort(a, j + 1,r);

这里和分界点的选择关系很大。以下都会导致Infinite Loops。

• quickSort(q, l, j); quickSort(q, j, r);
• quickSort(q, l, i - 1); quickSort(q, i, r); + x = a[l];
• quickSort(q, l, j); quickSort(q, j + 1, r); + x = a[r];
  

//all  BUG验证样例
2
1 2

• 总结

所有和快排边界问题相关的情况，都会卡在类似

2
1 4

这样的测试样例中，所有复习和思考的时候一定想办法过这两个样例。

02-归并排序

void mergeSort(int a[], int l, int r) {

  if(l >= r) return;

  int mid = (l + r) >> 1;
  mergeSort(a, l, mid);
  mergeSort(a, mid + 1, r);

  int i = l, j = mid + 1;
  while(i <= mid && j <= r) {
        if(a[i] < a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
  }

  while(i <= mid) tmp[k++] = a[i++];
  while(j <= mid) tmp[k++] = a[j++];

  for(int i = l, j = 0; i <= r; i ++, j ++) a[i] = tmp[j];
}

归并排序和快排一样都是使用了分治思想。但是从算法流程上完全相反。快排是先调整区间然后递归处理比较大小。归并排序是先递归处理到只剩下一个元素的时候，才比较大小调整区间。

• while(i <= mid && j <= r)

这里的=不能丢掉，因为递归比较两个区间所有元素，而mid和r各占用一个元素。

• if(a[i] < a[j])

这里的=其实是一个if的零和逻辑——如果两边的元素正好相等，则会先后填充到tmp数组中，因为下一个元素一定比这两个元素都大或者都小。

• for(int i = l, j = 0; i <= r; i ++, j ++)

该语句体现了排序的核心逻辑——将递归过程抽象成为二叉树，则每当程序控制流执行到该条语句的时候，一定是树的非叶子节点处。树的每个节点代表一个区间。而整个算法逻辑可以看成是height相同的节点执行区间归并过程并先将结果填充到tmp数组中，再写回到hight + 1位置的节点处的过程。而该语句就是将处理完毕的顺序写回原数组，l代表了height + 1的起始位置。而j:0~(r-l+1)则是整个填充的内容。

03-二分法

void bSearch(int l, int r) {

    int lhs = l, rhs = r;
    while(lhs < rhs) {
        int mid = (lhs + rhs) >> 1;
        if(check(mid)) mid = r;
        else l  = mid - 1;
    }

}

二分的本质是边界，二分的目的是查找。 基础算法中其必要条件是在单调的序列中查找，因为满足条件的数值可能会是一个连续的序列——所以涉及到左右边界的问题。

其次二分的记忆点主要有两个，一个是while中的终止条件，一个就是check(mid)的判定条件。终止条件一般都是lhs < rhs对于浮点数的话是(rhs - lhs) >= 1e-8等。而check(mid)当然是看算法的目的是什么。数的范围同时处理了左右边界。
二分和快排，归并的边界问题甚至可以统一。

2
1 4