算法介绍
桶排
举个例子,一个数组中的数是:4 1 2 3 5,
然后桶排的顺序是:将每个数应该在的下标算出来,咋算呢?这我们就得考虑两种情况:假设我们设现在这个需要找到自己在数组里位置的数是x。
1.比x小的数有多少个
2.和x一样大并且原先就排在自己前面的数有多少个。
如果只考虑第一种情况很简单,但是如果两种情况都考虑呢?
那么我们就需要其他的东西来保证第二个相等的元素不改变位置了。那么这个东西是啥呢?很简单,一个前缀和:如何操作呢?还是举个例子:比如一个数列:3 2 2 1 5。我们求出其前缀和(这里的前缀和是其数字出现的个数的叠加并不是数的叠加),如下图
然后我们从后往前开始,(又因为其数列的数如果自己是x(n-1)那么自己的位置一定是x(n)-1)所以我们每个数的位置就是在其后面那个数的前面,因为我们序列最大的数是5所以从5开始我们发现其s5(序列和)=5并且数组中有这个数所以它应该放在下标为5的位置,然后向前遍历,1应该放在s1的位置=1,所以放在最开始的位置。以此类推。
算法题目
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N], w[N];
int s[N];
void bucket_sort(int n){
for(int i=0;i<n;i++){
s[q[i]]++;
}
for(int i=1;i<N;i++){
s[i] = s[i-1] + s[i];
}
for(int i=n-1;i>=0;i--){
w[--s[q[i]]] = q[i];
}
for(int i=0;i<n;i++){
q[i] = w[i];
}
return;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)scanf("%d",&q[i]);
bucket_sort(n);
for(int i=0;i<n;i++)printf("%d ",q[i]);
return 0;
}
acwing上面这段代码可以过10个数据。
算法复杂度
空间复杂度:O(n + m)
时间复杂度:O(n + m)
稳定性:稳定