本文共 3543 字，大约阅读时间需要 11 分钟。

quick_sort

基本思想：分治（divide and conquer）

步骤：

1. 确定分界点 q[ l ] , q[ r ] , q[l + r >> 1] 随机 皆可，但是为了防止边界越界的问题，建议选择q[l + r >> 1] 为基准点( pivot ).
2. 调整区间，使得小于基准点的数位于基准点的左边，大于基准点的数位于基准点的右边。
3. 递归处理左右两端
   模版（template）:

#include 
   
    using namespace std;const int maxn = 100 + 5;void quick_sort(int q[],int l,int r){
       if(l >= r) return ;    int x = q[l + r >> 1]; int i = l -1 , j = r + 1;    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);}int main(){
       int arr[maxn]; int n; scanf("%d",&n);    for(int i = 0; i < n;i++) scanf("%d",&arr[i]);    quick_sort(arr,0,n-1);    for(int i = 0;i < n;i++) printf("%d ",arr[i]);    printf("\n");    return 0;}
   

merge_sort

基本思想：分治（divide and conquer）

1. 确定分界点 mid = l + r >> 1;
2. 递归排序 left , right
3. 归并 —— 合二为一

模版（template）:

#include 
   
    using namespace std;const int maxn = 100 + 5;int temp[maxn];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 = l, j = mid + 1;    while(i <= mid && j <= r)        if(q[i] <= q[j]) temp[k++] = q[i++];        else temp[k++] = q[j++];    // 将剩余的元素补到数组的后面    while(i <= mid) temp[k++] = q[i++];    while(j <= r)   temp[k++] = q[j++];    for(int i = l,j = 0;i <= r;i++,j++) q[i] = temp[j];}int main(){
       int arr[maxn]; int n; scanf("%d",&n);    for(int i = 0;i < n;i++) scanf("%d",&arr[i]);    merge_sort(arr,0,n-1);    for(int i = 0;i < n;i++) printf("%d ",arr[i]);    printf("\n");    return 0;}
   

binary_search

二分中需要注意的一点：

整数二分：

需要注意的地方：因为 c/c+++ 是向下取整，当 l == r - 1 的时候 ,if(check(x)) == true 这个时候 l == mid == l + r >> 1 == l 这样就会造成死循环 ，所以此时需要在l + r 的后面加1 防止造成死循环。所以这时需要考虑其边界，只需记住一点，当 l == mid 的时候，此时 L + R >> 1 需要在 L + R 上加上一，防止造成边界死循环的问题。

模版：

#include 
   
    using namespace std;const int maxn = 1e6 + 10; int arr[maxn];int n , m;int main(){
       scanf("%d %d",&n,&m);    for(int i = 0;i < n;i++) scanf("%d",&arr[i]);    while(m--)    {
           int x ; scanf("%d",&x); int ss = 0 , ee = 0;        int l = 0, r = n - 1;        // 找起始位置        while( l < r )        {
               int mid = l + r >> 1;            if(arr[mid] >= x) r = mid;            else l = mid + 1;        }        ss = l;        // 如果没找到该元素 则返回        if(arr[l] != x) {
   cout << "-1 -1" << endl; continue; }        else {
               l = 0, r = n - 1;            // 找终点位置            while(l < r)            {
                   int mid = l + r + 1 >> 1;                if(arr[mid] <= x) l = mid;                else r = mid - 1;            }            ee = l;        }        cout << ss + 1 << " " << ee + 1 << endl;    }    return 0;}
   

浮点数二分：

在c/c++ 中浮点数的除法是精确的，所以对浮点数进行二分时，每次二分都能严格缩小一半，不需要去考虑边界问题。

模版：

Code:

#include 
   
    using namespace std;int main(){
       double x ; cin >> x;    double l = 0, r = x;    // 当小于所需精度时，则一直二分 直到结果小于所需的精度    while( r - l > 1e-6 )    {
           // 注意： 浮点数不能进行位运算操作        double mid = (l + r) / 2;        if(mid * mid >= x) r = mid;        else l = mid;    }    cout << l << endl;    return 0;}
   

转载地址：https://blog.csdn.net/weixin_45877540/article/details/108048667 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！