[基础算法](1)排序

快速排序

核心思路：

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

模板:

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题库

代码:

#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. 再利用双指针指向左右区间的头元素进行比较形成新的区间

模板:

#include<iostream>
#include<algorithm>
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题库

思路:

• 利用分治思想将序列对分为三类

  • 两个元素都在左边
  • 两个元素都在右边
  • 两个元素一个在左边一个在右边
• 递归算左边的
• 递归算右边的
• 算一个左边一个右边的

代码

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

树状数组写法

这题还能用树状数组做，统计该数前面有多少个大于他的数即可，代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#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;
}

本文链接：