[基础算法](1)排序
快速排序
核心思路：
- 划分左右边界 L 和 R
- 确定轴值 x
- 当前小于轴值得数在轴值左边，大于轴值的数在轴值右边
- 递归轴值左边和右边进行分治处理
模板:
```C++ void Qsort(int *nums,int l,int r){ if(l>=r) return; int x=nums[l+r>>1];//取中间值为轴，反之升/降序数组 int i=l-1,j=r+1; while(i<j){ while(nums[++i]<x);//左边保留小于轴值的数值 while(nums[--j]>x);//右边保留大于轴值得数值 if(i<j) Swap(nums,i,j);//交换 } Qsort(nums,l,j);//分治左边 Qsort(nums,j+1,r);//分治右边 }
### 模板题:[786. 第k个数 - AcWing题库](https://www.acwing.com/problem/content/788/)
### 代码:
```C++
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int nums[N];
int n, m;
//利用快排的思想，一趟下来轴值左边比轴值小，轴值右边比轴值大
int Qselect(int L ,int R,int k) {
if (L == R) return nums[L];
int x = nums[L];
int i = L - 1, j = R + 1;
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) swap(nums[i], nums[j]);
}
if (k > j) return Qselect(j + 1, R,k);//选择区间进行剪枝
return Qselect(L, j, k);
}
int main () {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> nums[i];
cout << Qselect(0, n - 1, m - 1) << endl;
return 0;
}归并排序
核心思路:
- 先递归划分左右区间
- 再利用双指针指向左右区间的头元素进行比较形成新的区间
模板:
```C++
include
include
using namespace std; const int N = 10010; int nums[N]; int n; void merge_sort(int L, int R) { if (L >= R) return; int mid = L + R >> 1;//划分左右区间 merge_sort(L, mid); merge_sort(mid + 1, R);//递归左右区间形成子问题 int l = L, r = mid + 1; int tnums[N], t = 0; //比较左右区间头元素形成新的区间 while (l <= mid && r <= R) { if (nums[l] < nums[r]) tnums[t++] = nums[l++]; else tnums[t++] = nums[r++]; } while (l <= mid) tnums[t++] = nums[l++]; while (r <= R) tnums[t++] = nums[r++];
//将新区间替换原有区间
for (int i = L, j = 0; j < t; i++, j++) nums[i] = tnums[j];
return;} int main() { cin >> n; for (int i = 0; i < n; i++) cin >> nums[i]; merge_sort(0, n - 1); for (int i = 0; i < n; i++) cout << nums[i] << " "; return 0; }
### 模板题:[788. 逆序对的数量 - AcWing题库](https://www.acwing.com/problem/content/790/)
### 思路:
- 利用分治思想将序列对分为三类
- 两个元素都在左边
- 两个元素都在右边
- 两个元素一个在左边一个在右边
- 递归算左边的
- 递归算右边的
- 算一个左边一个右边的
###代码
```C++
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
//左边的相加和右边的相加
LL res = 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]) tmp[k++] = q[i++];
else {
res += mid - i + 1;//计算左右两边的
tmp[k++] = q[j++];
}
}
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
return res;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
cout << merge_sort(a, 0, n - 1) << endl;
return 0;
}树状数组写法
这题还能用树状数组做，统计该数前面有多少个大于他的数即可，代码如下所示：
```C++
include
include
define N 1006000
int nums[N]; int n;
int C[N+1];
int lowbit(int x){//返回x最后一个1所代表的数 return x&-x; } int getsum(int x){//返回[0,x]这个区间的前缀和 int res=0; while(x>0){ res+=C[x]; x-=lowbit(x); } return res; } void updata(int x,int e){//在x的下标上加上e while(x<=N){//N为数组总长度 C[x]+=e; x+=lowbit(x); } return; } int main(){ scanf("%d",&n); long long res=0; for(int i=0;i<n;i++) scanf("%d",&nums[i]); for(int i=0;i<n;i++){ //N为哨兵节点，他计算当前加入所有数的总和，减去小于 i 的数，就是当前加入大于他的数的值 res+=getsum(N)-getsum(nums[i]);//计算前面有多少个大于 nums[i] 的数 updata(nums[i],1); }
printf("%lld",res);
return 0;}