一些蒟蒻的模板

快速排序

平时写题用sort就行了，但是如果要求排序就中间结果诸类的题，还是有点用！

听说long long ago，高中组的比赛只要会打sort代码就能得分（当时不允许用STL）

我也想比赛考这样的题……

快排主要还是边界问题

为了防止快排退化为冒泡，可以采用随机数（不过平时我还是习惯取中间值……） 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+5;
 4 int n,q[N];
 5 void quick_sort(int q[],int l,int r){
 6     if(l>=r) return;
 7     int x=q[l+r>>1];
 8     int i=l-1,j=r+1;
 9     while(i<j){
10         do i++; while(q[i]<x);
11         do j--; while(q[j]>x);
12         if(i<j) swap(q[i],q[j]);
13     }
14     quick_sort(q,l,j);
15     quick_sort(q,j+1,r);
16 }
17 
18 int main(){
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cin>>n;
22     for(int i=0;i<n;i++)
23         cin>>q[i];
24     quick_sort(q,0,n-1);
25     for(int i=0;i<n;i++)
26         cout<<q[i]<<' ';
27     return 0;
28 }

归并排序

同上，也可以用STL提供的merge

但是这个相对还是用处多一点的

且归并排序的重点不在于边界

合并的过程很重要（要开辅助空间）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+5;
 4 int n,q[N],tmp[N];
 5 void merge_sort(int q[],int l,int r){
 6     if(l>=r) return;
 7     int mid=l+r>>1;
 8     int k=0,i=l,j=mid+1;
 9     merge_sort(q,l,mid);
10     merge_sort(q,mid+1,r);
11     while(i<=mid&&j<=r){
12         if(q[i]<q[j]) tmp[k++]=q[i++];
13         else tmp[k++]=q[j++]; 
14     } 
15     while(i<=mid)
16         tmp[k++]=q[i++];
17     while(j<=r)
18         tmp[k++]=q[j++];
19     for(int i=l,j=0;i<=r;i++,j++)
20         q[i]=tmp[j]; 
21 }
22 int main(){
23     ios::sync_with_stdio(false);
24     cin.tie(0);
25     cin>>n;
26     for(int i=0;i<n;i++)
27         cin>>q[i];
28     merge_sort(q,0,n-1);
29     for(int i=0;i<n;i++)
30         cout<<q[i]<<' ';
31     return 0;
32 }

二分查找

整数二分查找重点还是边界问题

浮点二分就无所谓啦~