排序算法中需要牢牢掌握的有快速排序和归并排序；而二分又是查找算法中比较快捷的算法了。那么对于上述两种算法，它们的原理是什么？又怎么使用它们呢？
...

大纲

排序：

• 快速排序
• 归并排序

二分：

• 整数二分
• 浮点数二分

学习方法：

• 学习代码的思想
• 理解并记忆代码模板
• 模板题进行熟练，每道题一般重复3-5次即可。

排序

快速排序

基本思想

分治的思想。

1. 确定分界点（指的是数组中的某一个数，而不是该数对应的数组下标）。随便从数组中找一个数，作为我们的分界点。有几种常用的方法：

   • 取左边界，q[l]
   • 取右边界，q[r]
   • 取中间点，q[(l + r) / 2]
   • 随机取

2. 划分区间。根据上述选取的分界点，将整个数组分成两半，把小于等于分界点的值放到数组的左边，把大于等于分界点的值放到数组的右边。注意要求的是两个部分都是小于等于。

3. 递归处理，即：重复上述的操作，递归处理左右两个子区间。

快速排序的难点和重点

在第二个划分区间（调整区间上）。首先要明确目标：通过某一种简单高效的方式，将数组中小于等于分界点的数放到数组的左半边，大于等于分界点的数放到数组的右半边。

输入的数据是数组的左右两个边界下标，是闭区间[lo, hi]

可以暴力处理，额外的开辟两个数组，将大于等于分界点的数放到一个临时数组中，同时将小于等于分界点的数放到另一个临时数组中。让后将这两个数组合并到原来的数组中即可。

较为优雅的方法是双指针法：

1. 将数组虚拟添加两个哨兵节点。最左侧的哨兵节点为负无穷，最右边的哨兵节点为正无穷，两个指针的初始位置分别指向这两个虚拟哨兵节点，即：

int left = lo - 1;
int right = hi + 1;

为什么要这么设置？因为我们在移动的时候不管三七二十一，都是指针先前进一步，然后再进行判断的。所以需要先让出一个位置，避免漏掉需要判断的数据。

2. 左侧的指针先行，当其指向的数组中的值小于分界点时，指针继续向右走（因为此时这个数应该位于数组的左半边，不用进行交换等额外操作）；如果指针指向的数组中的值大于等于分界点，此时左侧的指针停下。

3. 右侧的指针后行，当期指向的数组中的值大于分界点时，指针继续向左走（因为此时这个数应该位于数组的右半边，不用进行交换等额外操作）；如果指针指向的数组中的值小于等于分界点时，此时右侧的指针停下

4. 交换这两个指针指向的数组中的值，并左侧指针和右侧指针分别前进一步，然后继续上述2-3的操作。

为什么上述做法是正确的？假设在任意时刻t，此时观察左侧指针的左半边的数据的情况，其都是小于等于分界点的（因为如果是大于等于分界点的，此时已经交换了；右半边的小于等于分界点的也交换过来了）；同理，右侧指针的右半边的数据都是大于等于分界点的。所以当两个指针相遇或穿过，则满足上述我们的要求。

描述上述操作的关键点是，终止条件是什么？两个指针相遇或步过。

递归处理时的注意要点

在递归处理的时候，只要是对称的进行处理即可，如果写的是right，则右半的起始位置是right + 1 ；如果要用left，则左半边是left-1 ，而右半边的起始位置就是left 了。

但是如果你要用left 来做区间划分的边界下标，则需要注意你取的那个分界点不能是左侧边界点，即：ary[left] ，应该是ary[right] 或者其他选取方法（但是一定要上取整，不能取得左边界left这个位置），否则可能会出现边界死循环的问题。同理，如果选择的是right 来做区间划分的边界下标，则需要注意取的分界点不能是右侧边界点。

为什么会出现死循环呢？举个例子，ary = [1, 2] （递增数列），此时根据上述划分方法，则一个数组是空的，另一个是原数组，问题的规模并没有缩减，从而导致死循环，直到爆栈退出。

快速排序的一种模板

void quick_sort(int A[], int lo, int hi)
{
    // 当数组中只有1个或0个元素时，不需要进行排序，直接返回就好
    if (lo >= hi) 
    {
        return;
    }
    
    // 指向两个哨兵节点，避免漏过数据
    int left = lo - 1, right = hi + 1;
    int pivot = A[(lo + hi) >> 1];
    
    // 两个指针还没有相遇或者穿过
    while (left < right) 
    {
        do 
        {
            left++;
        } while (A[left] < pivot);
        
        do 
        {
            right--;
        } while (A[right] > pivot);
        
        // left和right指针还未相遇
        if (left < right)
        {
            std::swap(A[left], A[right]);
        }
    } 
    quick_sort(A, lo, right);
    quick_sort(A, right + 1, hi);
}

归并排序

基本思想

同快速排序一样，是分治思想。

1. 确定分界点下标。
2. 先递归排序左边和右边。这样得到了一系列的有序数组列。
3. 两两归并为有序数组直到只剩一个数组。

归并排序中的重点和难点

在于归并，即：如何将两个有序的序列合二为一。其实就是比较两个指针指向的两者中的较小者，放到新的一个数组中，直到合并完。

由于左侧的指针只会扫描左半边，右侧的指针只会扫描右半边。故：两两归并的时间复杂度是O(N)的。

对于归并排序，其每次都要两两二分，从而期望划分为 $log_2N$ 次，每次合并的时间复杂度是O(N)，故最终的时间复杂度是：O(NlogN)

归并排序的一种模板

void merge_sort(int A[], int lo, int hi)
{
    // 当数组中只有1个或0个元素时，不需要进行排序，直接返回就好 
    if (lo >= hi)
    {
        return;
    }
    
    // 划分区间
    int mid = (lo + hi) >> 1;
    // 递归排序两边
    merge_sort(A, lo, mid);
    merge_sort(A, mid + 1, hi);
    
    // 合并两个有序数组到临时数组中
    int left = lo, right = mid + 1;
    int tmp_ary_idx = 0;
    while (left <= mid && right <= hi)
    {
        if (A[left] <= A[right])
        {
            tmp_ary[tmp_ary_idx] = A[left];
           	++left;
        }
        else
        {
            tmp_ary[tmp_ary_idx] = A[right];
            ++right;
        }
        ++tmp_ary_idx;
    } 
    
    // 将剩余的部分放到临时数组中
    while (left <= mid)
    {
        tmp_ary[tmp_ary_idx] = A[left];
        ++left;
    }
    
    while (right <= hi)
    {
        tmp_ary[tmp_ary_idx] = A[right];
        ++right;
    }
    
    // 将临时数组中的数据拷贝到原数组
    for (int i = lo, j = 0; i <= hi; ++i, ++j)
    {
        A[i] = tmp_ary[j];
    }
}

二分法

整数二分

问题的本质

二分法与数据的单调性没什么必然的联系，如果要说有的话，那么就是如果数据具有单调性，那么就一定可以二分。但是可以二分的题目，不一定非得要求有单调性。

本质其实是边界。我们定义一个性质，使得在所给数据集上的左半边满足这个性质，另一半不满足这个性质。如果可以找到这个性质的话，可以把数据一分为二，那么二分就可以寻找到这个性质的边界（两个分界点都可以找到）。

寻找左侧部分的边界点（左侧部分的终点）

步骤：

1. 找到其中间点，mid = (left + right + 1) / 2 ，注意要加1
2. 检查这个中间点是否满足所给性质（即：左侧部分数据应该满足的性质）if(check(mid))
   • 如果是true，则mid一定在左侧部分，分界点（答案）应该在右半区间，所以应该将left = mid ，其答案区间应该是：[mid, right]，注意是闭区间。
   • 如果是false，则mid一定在右侧部分，分界点（答案）应该在左半区间，所以应该将right = mid - 1，其答案区间应该是：[left, mid - 1]，注意是闭区间。（为什么是mid-1？因为mid是一定不满足所给性质的，所以可以将mid给排除掉了）

寻找右侧部分的边界点（右侧部分的起始点）

步骤：

1. 找到其中间点，mid = (left + right) / 2
2. 检查中间点是否满足所给性质（即：右侧部分数据应该满足的性质）
   • 如果是true，则mid一定在左侧部分，分界点（答案）应该在左半区间，所以应该将right = mid ，其答案区间应该是：[left, mid]，注意是闭区间。（因为mid满足所给性质，所以其答案还是可能在mid这点上的）
   • 如果是false，则mid一定在右侧部分，分界点（答案）应该在右半区间，所以应该将left = mid + 1，其答案区间应该是：[mid + 1, right]，注意是闭区间。（为什么是mid+1？因为mid是一定不满足所给性质的，所以可以将mid给排除掉了）

如何选择使用哪个方法

步骤：

1. 先写一个check 函数
2. 想一下这个check(mid)函数是true或者false的时候如何更新
3. 如果更新方式是left = mid 和 right = mid - 1，则需要在计算mid时，补上分子的那个1（即：取上整）

其实核心就是看更新区间到底是left = mid 还是right = mid（在check为true的情况下），如果是left = mid ，则需要mid取上整，需要补偿加1，否则不需要补偿加1.

需要注意的是，定义一个性质之后，其二分一定是有解的（即：一定有一个边界），但是题目是不一定有解的。

为什么当check为真时left = mid要补偿加1

当left和right只差1的时候，如果mid不补偿加1的话，那么mid下取整是等于left的，如果此时check为true的，则left还是等于left，此时没有进行更新，从而会出现死循环的情况。

整数二分的模板

// 用来检查var是否符合某一性质
bool check(int var) {}

// 区间[left, right]被划分为[left, mid]和[mid + 1, right]时使用
int binary_search(int left, int right)
{
    while (left < right)
    {
        int mid = (left + right) >> 1;
        if (check(mid) == true)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return left;
}

// 区间[left, right]被划分为[left, mid - 1]和[mid, right]时使用
int binary_search(int left, int right)
{
    while (left < right)
    {
        int mid = (left + right + 1) >> 1;
        if (check(mid) == true)
        {
            left = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
    return left;
}

浮点数二分

这里面就不需要考虑是否需要补偿了，直接就可以二分更新即可。

浮点数二分模板

// 用来检查var是否符合某一性质
bool check(double var) {}

double binary_search(double left, double right)
{
    // 经验值：精度控制比题目所给的精度高-2即可，如：题目要求保留4位，则精度为1e-6即可	
    const double delta = 1e-6;   
    while (right - left > eps)
    {
        double mid = (left + right) / 2;
        if (check(mid)) 
        {
            right = mid;
        }
        else 
        {
            left = mid;
        }
    }
    return left;
}