桶排序的思想是把同一种类的数放进一个桶内（可以用int数组或者set等容器表示），然后在排序的时候就可以根据每个桶的不同（在生成桶的时候应该要考虑各个桶的优先级），先进行对桶的排序，再进行桶内元素的排序（当每个桶装的元素之间没有优先级时省略这一步）。
下面有两种形式的桶排序的示意图
单点桶 这种桶直接用int数组就可以实现，用nu[i]来表示 i 出现的次数，每次遇到i，使nu[i]++。最后数列的排序就是按照桶的下标的排序。
区域桶 这种桶就比较复杂了，这里给出两种方法仅供参考。 ①单单用int数组的话，就得用二维数组nu[i][j]了，表示第i个桶的第j个元素，另外可以再用个一维的Conut[i]表示第i个桶的size。分好后如果需要桶内排序就直接sort(nu[i],nu[i+Count[i]],cmp)。 ②也可以用set数组set<int>nu[i]来存，而且set会自动排序。讲到这里，其实你们也差不多知道了，其实桶排序很多时候并不就是用来排序的，如果排序直接sort就行了。你可以把桶理解为一种思想，把相同或相似的元素归为一类，然后在更高的层面处理元素。
原题：Jon Snow and his Favourite Number
题意：给定n个数，要求操作k次，每次先对数组排序，在排序后的数组中奇数位上的数异或x。问k次操作后的最大值和最小值
思路：暴力复杂度为o(knlogn)，会超时。此题的数字范围为0-1000，异或后范围为0-1023比较小，所以我们用单点桶做，复杂度降为O(1000k)。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<set> #include<map> #include<list> #include<vector> #include<stack> #include<queue> #include<functional> #define D long long #define F double #define MAX 0x7fffffff #define MIN -0x7fffffff #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back #define mk make_pair #define fi first #define se second #define pill pair<int, int> #define for1(i,a,b) for(int i=a;i<=b;i++) #define for2(i,a,b) for(int i=a;i>=b;i--) using namespace std; #define N 100100 #define MOD ((int)1e9+7) const string el="\n"; const string elel="\n\n"; const string sp=" "; const string spsp=" "; const string tab="\t"; int CO(int l,int r){//l到r范围内conut 奇数个数 if(l==r){ if(l%2==1)return 1; else return 0; } if(l%2!=r%2)return (r-l+1)>>1; if(l%2==0)return (r-l)>>1; return ((r-l)>>1)+1; } void S(int nu[],int y,int n){ int change[1024];mmm(change,0);//记录异或处理时的变化的数组 int t=0; for1(i,0,1023){ if(nu[i]==0)continue; int nuji=CO(t+1,t+nu[i]);//因为排序好后相同数字一定是连在一起的 change[i]-=nuji;//i的数量减去i在奇数位上的数量 change[i^y]+=nuji; t+=nu[i]; if(t==n)break; } for1(i,0,1023)nu[i]+=change[i]; } int main() { int n,k,y;int nu[1024];mmm(nu,0); scanf("%d%d%d",&n,&k,&y); for1(ijk,1,n){ int mid;scanf("%d",&mid); nu[mid]++; } for1(ijk,1,k){ S(nu,y,n); } int big,sma; for1(i,0,1023){ if(nu[i]){sma=i;break;} } for2(i,1023,0){ if(nu[i]){big=i;break;} } printf("%d %d\n",big,sma); return 0; }