归并排序：(nlog(n) 小->大)
1.将数组分成两部分
2.将两部分分别排序
3.将排完序的两部分合为一部分
void merge_sort(int x,int y){ if(y-x <= 1) return; int m = x + (y-x)/2; int p = x,q = m,i = x; merge_sort(x,m); merge_sort(m,y); while(p < m || q < y){ if(q >= y || (p < m&&a[p] <= a[q])) t[i++] = a[p++]; else t[i++] = a[q++]; } for(int i = x;i < y;i++) a[i] = t[i]; return; }
求逆序对问题：（nlog(n)，归并排序变种）
1.将问题分为两部分进行
2.分别对两部分的逆序对进行计算
3.对两部分右边比左边小的逆序对进行计算
4.相加
PS：由于之前归并排序是从小到大，在进行复制时将右边较小的复制到临时数组时，左边已剩下的个数就是比右边大的逆序数
int merge_sort(int x,int y){ if(y-x <= 1) return 0; int m = x + (y-x)/2; int p = x,q = m,i = x; int L = merge_sort(x,m); int R = merge_sort(m,y); int cntt = 0; while(p < m || q < y){ if(q >= y || (p < m&&a[p] <= a[q])) t[i++] = a[p++]; else{ t[i++] = a[q++]; ///将右边复制到临时数组，而左边剩下没复制的就是比右边大的 cntt += (m-p); } } for(int i = x;i < y;i++) a[i] = t[i]; return (R+L+cntt); }
快速排序：
1.在元素中找一个基准
2.将把基准大的数字放在基准右边，把比基准小的数字放在基准左边
3.对基准的左边和右边进行排序
void q_sort(int x,int y){ if(x >= y) return; int k = a[x]; int first = x; int last = y; while(first < last){ while(first < last && a[last] >= k) last--; a[first] = a[last]; while(first < last && a[first] <= k) first++; a[last] = a[first]; } a[first] = k; q_sort(x,first-1); q_sort(first+1,y); }
二分查找
int b_search(int x,int y,int v){ int m; while(x < y){ m = x + (y-x)/2; if(a[m] == v) return m; if(a[m] > v) y = m; else x = m+1; } return -1; } int _lower_bound(int x,int y,int v){ int m; while(x < y){ m = x + (y-x)/2; if(a[m] >= v) y = m; else x = m+1; } return x; } int _upper_bound(int x,int y,int v){ int m; while(x < y){ m = x + (y-x)/2; if(a[m] <= v) x = m; else y = m+1; } return y; }