[基础算法](1)排序

快速排序

核心思路:

  1. 划分左右边界 L 和 R
  2. 确定轴值 x
  3. 当前小于轴值得数在轴值左边,大于轴值的数在轴值右边
  4. 递归轴值左边和右边进行分治处理

模板:

```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/)

![image-20210708153209700](https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/image-20210708153209700.png)

### 代码:

```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;
}

归并排序

核心思路:

  1. 先递归划分左右区间
  2. 再利用双指针指向左右区间的头元素进行比较形成新的区间

模板:

```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/)

![image-20210708154008855](https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/image-20210708154008855.png)

### 思路:

- 利用分治思想将序列对分为三类
  - 两个元素都在左边
  - 两个元素都在右边
  - 两个元素一个在左边一个在右边
- 递归算左边的
- 递归算右边的
- 算一个左边一个右边的

###代码

```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;

}

本文链接:

https://nullcode.fun/158.html
1 + 7 =
快来做第一个评论的人吧~