786. 第k个数
STL nth_element() 求第k小/k大
大佬博客详解

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int a[MAXN];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    nth_element(a+1,a+k,a+1+n);
    printf("%d\n",a[k]);


    return 0;
}

快排o(n)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int a[MAXN];

void quick_sort(int l,int r,int k)
{
    if(l>=r)return;
    int i=l-1,j=r+1,mid=a[l];
    while(i<j)
    {
        do i++; while(a[i]<mid);
        do j--; while(a[j]>mid);
        if(i<j)swap(a[i],a[j]);
        else break;
    }
    if(j>=k)return quick_sort(l,j,k);
    else return quick_sort(j+1,r,k);

}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    quick_sort(1,n,k);
    printf("%d\n",a[k]);

    return 0;
}

归并求逆序对
65. 数组中的逆序对

 class Solution {
public:
    int tmp[100005];
    int merge_sort(vector<int>&nums,int l,int r)
    {

        if(l>=r)return 0;
        int mid=(l+r)>>1;
        int res=0;
        res+=merge_sort(nums,l,mid);
        res+=merge_sort(nums,mid+1,r);
        int k=0,i=l,j=mid+1;
        int cnt=0;
        while(i<=mid&&j<=r)
        {
            if(nums[i]<=nums[j])tmp[k++]=nums[i++];
            else 
            {
                tmp[k++]=nums[j++];
                res+=mid-i+1;
                cnt+=mid-i+1;
            }
        }
        while(i<=mid)tmp[k++]=nums[i++];
        while(j<=r)tmp[k++]=nums[j++];

        for(int i=l,j=0;i<=r;i++,j++)nums[i]=tmp[j];

        return res;
    }
    int inversePairs(vector<int>& nums) {
        int n=nums.size();
        if(n==0)return 0;
        return merge_sort(nums,0,n-1);
    }

};

838. 堆排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int a[MAXN];
int h[MAXN],siz;
int n,m;
int hp[MAXN],ph[MAXN];
/*void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}*/
void down(int u)
{
    int t=u;
    if(u*2<=siz&&h[u*2]<h[t])t=u*2;
    if(u*2+1<=siz&&h[u*2+1]<h[t])t=u*2+1;
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}
/*void up(int u)
{
    while(u/2&&h[u/2]>h[u])
    {
        swap(h[u/2],h[u]);
        u/=2;
    }
}*/
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    siz=n;
    for(int i=n/2;i;i--)down(i);//o(n)建树
    while(m--)
    {
        printf("%d ",h[1]);//取出堆顶元素，最小值
        h[1]=h[siz];//将最后一个数和堆顶的数交换，删掉第一个数
        siz--;
        down(1);//将堆顶数下放
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int a[MAXN];
void bubble_sort(int n)//冒泡排序
{
    for(int i=1;i<n;i++)
    {
        int f=0;
        for(int j=1;j<=n-i;j++)
        {
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
            f=1;
        }
        if(!f)break;
    }
}
void insert_sort(int n)//将新元素插入排好序的数组中
{
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j>1;j--)
        {
            if(a[j]<a[j-1])swap(a[j],a[j-1]);
        }
    }
}

void select_sort(int n)//选择排序
{
    for(int i=1;i<n;i++)
    {
        int tmp=i;
        for(int j=i+1;j<=n;j++)
        {
            if(a[tmp]>a[j])tmp=j;
        }
        swap(a[i],a[tmp]);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    select_sort(n);

    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}