基础算法（1）

快速排序（O(NlogN)）

思路：确定分界点（序列里随机一个数都可以）：左边界、右边界、中值；调整范围；递归处理左、右两段

核心：每次j指针落在i指针前面位置时，将q[i]、q[j]进行swap操作（先分两边，再递归左右）

y总讲解的图示：

代码模板：

#include <iostream>
using namespace std;

// 快速排序 
const int N = 1e6+10;

int n,q[N]; // 规模 开辟空间大小 

void quick_sort(int q[], int left, int right)
{
    if (left >= right) return;   //判断边界 
    
    int x=q[left+right >> 1]; //x是判定条件 
    int i=left-1, j=right+1 ; 
    while(i<j) //每次移动并交换 
    {
        do i++; while( q[i]<x); //对比目标，希望将i移到x右边
        do j--; while( q[j]>x); //对比目标，希望将j移到x左边
        if (i<j) swap(q[i], q[j]);    //出现问题，那就交换
    }    
    
    quick_sort(q, left, j);  //递归左半部分 
    quick_sort(q, j+1, right);//递归右半部分 
}

int main() {
    
    scanf("%d", &n);
    
    for(int i=0; i<n ; i++)
        scanf("%d", &q[i]);
    
    quick_sort(q, 0, n-1);
    
    for(int i=0; i<n; i++)
        printf("%d ", q[i]);
    
    return 0;
}

归并排序（O(NlogN)）

思路：确定分界点（中值）；递归排序左右边；将有序数组合并成有序数组（归并）；

核心：分界点为中心点，也是双指针算法i、j（先递归左右，再分左右）

代码模板：

#include <iostream>
using namespace std;

// 归并排序 
const int N = 1e6+10;
int n,q[N]; // 规模 开辟空间大小 

// 图示 l_____mid______r
//        l_____mid
//         mid_____r

void merge_sort(int q[], int left, int right)
{
    if (left >= right) return; 
    
    int mid = left+right >> 1 ;  
    merge_sort(q, left, mid);  //递归左半部分 
    merge_sort(q, mid+1, right);//递归右半部分 
    
    int k=0, i=left, j=mid+1;
    while( i<=mid && j<=right)
        if (q[i]<=q[j]) newarray[k++]=q[i++]; //上 > 下，上面的放到新数组
        else newarray[k++]=q[j++];    //否则下面的放到新数组 
    
    while( i<=mid) newarray[k++]=q[i++];//剩余没排序完的直接加入新数组 
    while( j<=mid) newarray[k++]=q[j++];
    
    for (i=left, j=0; i<=r; i++,j++)
        q[i] = newarray[j];        //把新数组copy到原数组里面 
}

int main() {
    
    scanf("%d", &n);
    
    for(int i=0; i<n ; i++)
        scanf("%d", &q[i]);
    
    merge_sort(q, 0, n-1);
    
    for(int i=0; i<n; i++)
        printf("%d ", q[i]);
    
    return 0;
}

二分

整数二分：设定中值；左、右边界点与中值比较；

（1）mid = （left + right + 1）/ 2  ； true后面是l=mid，此时必须+1，防止当left=right-1时，程序发生死循环

（2）mid = （left + right）/ 2        ；

思路：在一个区间内部，每次选择一个答案所在的区间进行处理，每次都要保证区间内有答案。当区间长度为1时，区间内的数一定是答案。

图示：

模板代码：

#include <iostream>
using namespace std;
const int N = 100010 ;
int n, q[N];  
// 二分查找 有序数列中某数的始末坐标
// 1 1 2 2 3 3 4 中 3的输出为 4 5 

int main() {
    
    cin<<n<<m ; 
    
    for(int i=0; i<n; i++ ) cin>>q[i]; 
    
    while(m--)
    {
        int x; cin>>x; 
        int left=0, rigth=n-1; 
        
        while(left<right)
        {
            int mid=left+right>>1;
            if(q[mid] >= x) r=mid;
            else l=mid+1;
        }
        
        if (q[left] != x ) cout<<"-1 -1"<<endl;//没找到 
        else
        {
            cout<<left<<' '; 
            
            int left = 0, right = n-1; 
            while(l<r)
            {
                int mid = left+right+1 >> 1 ;
                if (q[mid] <= x) l=mid; 
                else r=mid-1 ; 
            }
            cout<<left<<endl;
        }
    }
    
    return 0;
}

浮点数二分：本质与整数二分相同，不需要处理边界，相对来说更简单

模板代码

#include <iostream>
using namespace std;
const int N = 100010 ;
int n, q[N];  
// 二分查找 有序数列中某数的始末坐标
// 1 1 2 2 3 3 4 中 3的输出为 4 5 

int main() {
    
    double l, r; 
    double x; 
    cin >> x;
    
    while(r-l > 1e-8) //浮点数切忌 == 
    {
        double mid = (l+r)/2 ; 
        if ( mid*mid >= x ) r=mid ;
        else l = mid ; 
    } 
    
    printf("%1f\n", l);
    return 0;
}