XiYuJing|文章:基数排序—

[[ slide_text ]]

[[item.c]]

基数排序——肖神优化

发布时间：2022年09月19日 作者：靖华来源：XiYuJing

算法 C++

## 基础版本
```c++
#include<iostream>
#include<bits/stdc++.h>
#include<unordered_map>
#define x first 
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N =1e6+10;
int main()
{
    ios;
    ll t;
    ll n;
    cin>>n;
    ll a[n],b[n],m[n];
    ll c=1;
    for(int i=0;i<n;i++){
        cin>>a[i];
        m[i]=a[i];
    }
    for(int k=0;k<9;k++)
    {
        int idx=0;
        for(int i=0;i<=9;i++)
        {
            for(int j=0;j<n;j++)
            {
                if((a[j]/c)%10==i){
                      b[idx++]=a[j];
                }
            }
            
        }
        c*=10;
        memcpy(a, b, sizeof a);
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<' ';
    }
}
```
## 二进制优化
```c++
#include<iostream>
#include<bits/stdc++.h>
#include<unordered_map>
#define x first 
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N =1e6+10;
int main()
{
    ios;
    ll n;
    cin>>n;
    ll a[n],b[n];
    ll c=0;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int k=0;k<32;k++)
    {
        int idx=0;
        for(int j=0;j<n;j++)
        {
            if(((a[j]>>c)&1)==0){
                b[idx++]=a[j];
            }
        }
        for(int j=0;j<n;j++)
        {
            if(((a[j]>>c)&1)==1){
                b[idx++]=a[j];
            }
        }
        c++;
        memcpy(a, b, sizeof a);
    }
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}
```
## 二度优化 用一个数组（剪枝）
```c++
#include<iostream>
#include<bits/stdc++.h>
#include<unordered_map>
#define x first 
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N =1e6+10;
int main()
{
    ios;
    ll n;
    cin>>n;
    ll a[n],b[n],bb[n];
    ll c=0;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int k=0;k<32;k++)
    {
        int idx=0;
        int idxx=0;
        for(int j=0;j<n;j++)
        {
            if(((a[j]>>c)&1)==0){
                b[idx++]=a[j];
            }
            else{
                bb[idxx++]=a[j];
            }
        }
        for(int j=0;j<idxx;j++)
        {
            b[idx++]=bb[j];
        }
        c++;
        memcpy(a, b, sizeof a);
    }
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}
```
## 梅开三度 空间换时间
```c++
#include<iostream>
#include<bits/stdc++.h>
#include<unordered_map>
#define x first 
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N =1e6+10;
int main()
{
    ios;
    ll n;
    cin>>n;
    ll a[n],b[10][n];
    ll c=1;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int k=0;k<9;k++)
    {
        int idx[10]={0};
        for(int j=0;j<n;j++)
        {
            int i=(a[j]/c)%10;
              b[i][idx[i]++]=a[j];
        }
        int idxx=0;
        for(int i=0;i<10;i++){
            for(int j=0;j<idx[i];j++){
                a[idxx++]=b[i][j];
            }
        }
        c*=10;
    }
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}
```
## 梅开四度 再次空间换时间
```
#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
#include<unordered_map>
#define x first 
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const ll N =1e6+10;
int main()
{
    ios;
    ll n;
    cin>>n;
    ll a[10][n],b[10][n],d,idx[10]={0},idxx[10]={0};
    ll f=10,x;
    
    for(int i=0;i<n;i++){
        cin>>d;
        x=d%10;
        a[x][idx[x]++]=d;
    }
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<=9;j++){
            for(int k=0;k<idx[j];k++){
                x=(a[j][k]/f)%10;
                b[x][idxx[x]++]=a[j][k];
            }
        }
        f*=10;
        memcpy(a,b,sizeof a);
        memcpy(idx,idxx,sizeof idx);
        memset(idxx,0,sizeof idxx);
    }
    for(int i=0;i<=9;i++)
        for(int j=0;j<idx[i];j++)cout<<a[i][j]<<' ';
}
```

你觉得文章怎么样

已浏览 383 次，7 条评论

段神

666，22年的计算机图灵奖－肖神

2022年9月22日 09:07
点赞 (1) 回复(0)
段神

这就是肖神吗，果然厉害

2022年9月17日 23:05
点赞 (0) 回复(2)

诩回复了段神

都是段神教的好

2022年9月18日 19:20
点赞(0) 回复

诩回复了段神

某等凡夫俗子

2022年9月18日 19:21
点赞(0) 回复
段神

这就是肖神吗，果然厉害

2022年9月17日 23:05
点赞 (0) 回复(0)
段神

肖神牛逼

2022年9月17日 23:00
点赞 (0) 回复(0)
段神

肖神牛逼

2022年9月17日 23:00
点赞 (0) 回复(0)

基数排序——肖神优化

段神

段神

诩 回复了 段神

诩 回复了 段神

段神

段神

段神

诩回复了段神

诩回复了段神