算法三十：基数排序

小鱼儿 2022-05-21 09:08 197阅读 0赞

### **问题描述** ###

给定 n 个 \[0,2^k) 之间的整数，请你将它们**升序**排序。

由于 n 可能很大，为了避免过大的输入、输出规模，我们会在程序内部生成数据，并要求你输出排序后序列的哈希值。具体方法如下（用c++代码展示）：

typedef unsigned int u32;

u32 nextInt(u32 x){
    	x^=x<<13;
    	x^=x>>17;
    	x^=x<<5;
    	return x;
    }

void initData(u32 *a,int n,int k,u32 seed){
    	for (int i=0;i<n;++i){
    		seed=nextInt(seed);
    		a[i]=seed>>(32-k);
    	}
    }

u32 hashArr(u32 *a,int n){
    	u32 x=998244353,ret=0;
    	for (int i=0;i<n;++i){
    		ret^=(a[i]+x);
    		x=nextInt(x);
    	}
    	return ret;
    }

输入将会给定 n,k,seed。

你可以调用 initData(a,n,k,seed) 来获得需要排序的 a 数组。

排序后，你可以调用函数 hashArr(a,n) 来获得我们希望你输出的哈希值。

### **输入格式** ###

一行 3 个用空格隔开的整数 n,k,seed，意义见题目描述。

### **输出格式** ###

一行一个整数，表示我们希望你输出的哈希值。

### **样例输入** ###

5 4 233333

### **样例输出** ###

740640512

### **样例解释** ###

生成的序列应为 4 10 13 9 4，排序后的结果应为 4 4 9 10 13。

### **提示** ###

\[对于 k=16 的数据，使用基数排序即可。\]

\[对于 k=32 的数据，不妨考虑两次基数排序哦！（即先排二进制下后 16 位，再排二进制下前 16 位）\]

### **Source** ###

\[改编自：「WC2017」挑战（\[\[https://loj.ac/problem/2286\]\]）\]

### **一. 伪代码** ###

![70][]

### **二. 具体实现** ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
typedef unsigned int u32;  
// 以下代码不需要解释，你只需要知道这是用于生成数据的就行了  
u32 nextInt(u32 x) \{  
x ^= x << 13;  
x ^= x >> 17;  
x ^= x << 5;  
return x;  
\}  
void initData(u32\* a, int n, int k, u32 seed) \{  
for (int i = 0; i < n; ++i) \{  
seed = nextInt(seed);  
a\[i\] = seed >> (32 - k);  
\}  
\}  
u32 hashArr(u32\* a, int n) \{  
u32 x = 998244353, ret = 0;  
for (int i = 0; i < n; ++i) \{  
ret ^= (a\[i\] + x);  
x = nextInt(x);  
\}  
return ret;  
\}  
// 以上代码不需要解释，你只需要知道这是用于生成数据的就行了  
const int N = 100000000;  
u32 a\[N + 1\];  
u32 \_a\[N + 1\];  
const int m = 16;  
const int B = 1 << m;  
const int b = B - 1;  
int sum\[B + 1\];  
// 这是你的排序函数，你需要将全局变量中的 a 数组进行排序  
// n, k：意义与题目描述相符  
// 返回值：本函数需不要返回值（你只需要确保 a 被排序即可）  
void sorting(int n, int k) \{  
memset(sum, 0, sizeof(sum));  
for(int i = 0; i < n; ++i)  
\++sum\[a\[i\] & b\];  
for(int i = 1; i < B; ++i)  
sum\[i\] += sum\[i - 1\];  
for(int i = n - 1; i >= 0; --i)  
\_a\[--sum\[a\[i\] & b\]\] = a\[i\];  
memset(sum, 0, sizeof(sum));  
for(int i = 0; i < n; ++i)  
\++sum\[(\_a\[i\] >> m) & b\];  
for(int i =1; i < B; ++i)  
sum\[i\] += sum\[i - 1\];  
for(int i = n - 1; i >= 0; --i)  
a\[--sum\[(\_a\[i\] >> m) & b\]\] = \_a\[i\];  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220521/d3836c14f49447c5a9547bb07fe724a1.png