csp/j排序代码

• 导航页

• GF2025csp/j计算机发展史

• GF2025csp/j计算机系统

• GF2025csp/j进制转换

• GF2025csp/jASCLL码&原码、反码、补码

• GF2025csp/j网络&HTML

• GF2025csp/j排序算法&类(class)

……

前言

先放链接

原题链接：点我跳转，右键复制地址

这题用快速排序(quicksort)代码如下:

#include <bits/stdc++.h>
#define ll long long//防止越界
using namespace std;
const int MAXN=1000005;//定义数组范围
ll a[MAXN],n;
ll qs(ll l,ll r,ll k){
	ll m=a[l+(r-l)/2];
	ll i=l,j=r-1;
	while(i<=j){
		while(a[i]<m) ++i;
		while(a[j]>m) --j;
		if(i<=j){
			swap(a[i],a[j]);
			++i,--j;
		}
	}
	if(l<=j && k<=j) return qs(l,j+1,k);
	if(i<r && k>=i) return qs(i,r,k);
	return a[n-k];//如果是求第k小数那么改为a[k]即可
}
int main(){
	ll k;
	cin>>n>>k;
	for(ll i=0;i<n;i++) cin>>a[i];
	cout<<qs(0,n,k);
	return 0;
} 

先放链接

原题链接：点我跳转，右键复制地址

再加一个归并排序吧。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll me(vector<int> &a,int l,int m,int r){
    vector<int> t(r-l+1);
    int i=l,j=m+1,k=0;
    ll out=0;
    while(i<=m && j<=r){
        if(a[i]<=a[j]){
            t[k++]=a[i++];
        }else{
            t[k++]=a[j++];
            out+=(m-i+1);
        }
    }
    while(i<=m) t[k++]=a[i++];
        while(j<=r) t[k++]=a[j++];
            for(i=l,k=0;i<=r;i++,k++){
                a[i]=t[k];
    }
    return out;
}
ll mer(vector<int> &a,int l,int r){
    ll out=0;
    if(l<r){
        int m=l+(r-l)/2;
        out+=mer(a,l,m);
        out+=mer(a,m+1,r);
        out+=me(a,l,m,r);
    }
    return out;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    cout<<mer(a,0,n-1)<<endl;
    return 0;
}

计数排序的标准代码如下。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=10005;
int a[105],cnt[MAXN],b[MAXN];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    for(int i=1;i<=10000;i++) cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++){
        b[cnt[a[i]]]=a[i];
        cnt[a[i]]--;
    }
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";
    return 0;
}