我有一本书这样说:
a) 根据值的一位数,将一维数组的每个值放入bucket数组的一行中。例如,97被放置在行7中,3被放置在行3中,100被放置在行0中。这被称为"分配通行证"
b) 逐行循环遍历bucket数组,并将值复制回原始数组。这被称为"聚集过程"。一维数组中前面的值的新顺序是100、3和97。
c) 对后面的每个数字位置重复此过程。
我在理解和实现这一点时遇到了很多困难。到目前为止,我有:
void b_sort(int sarray[], int array_size) {
const int max = array_size;
for(int i = 0; i < max; ++i)
int array[i] = sarray[i];
int bucket[10][max - 1];
}
我想,为了按1、10、数百等对它们进行排序,我可以使用以下方法:
for(int i = 0; i < max; ++i)
insert = (array[i] / x) % 10;
bucket[insert];
其中x=1、10、100、1000等。我现在完全不知道该怎么写。
这里有一个基于OP问题中的信息的bucket排序。
void b_sort(int sarray[], int array_size) {
const int max = array_size;
// use bucket[x][max] to hold the current count
int bucket[10][max+1];
// init bucket counters
for(var x=0;x<10;x++) bucket[x][max] = 0;
// main loop for each digit position
for(int digit = 1; digit <= 1000000000; digit *= 10) {
// array to bucket
for(int i = 0; i < max; i++) {
// get the digit 0-9
int dig = (sarray[i] / digit) % 10;
// add to bucket and increment count
bucket[dig][bucket[dig][max]++] = sarray[i];
}
// bucket to array
int idx = 0;
for(var x = 0; x < 10; x++) {
for(var y = 0; y < bucket[x][max]; y++) {
sarray[idx++] = bucket[x][y];
}
// reset the internal bucket counters
bucket[x][max] = 0;
}
}
}
注意对bucket使用2d数组会浪费大量空间。。。队列/列表的数组通常更有意义。
我通常不使用C++编程,而且上面的代码是在web浏览器中编写的,所以可能存在语法错误。
以下代码使用十六进制数字进行bucket排序(用于BITS_PER_BUCKET=4
)。当然,它是为了具有指导意义,而不是富有成效。
#include <assert.h>
#include <stdio.h>
#define TEST_COUNT 100
#define BITS_PER_BUCKET 4
#define BUCKET_COUNT (1 << BITS_PER_BUCKET)
#define BUCKET_MASK (BUCKET_COUNT-1)
#define PASS_COUNT (8*sizeof(int)/BITS_PER_BUCKET)
int main(int argc, char** argv) {
printf("Starting up ...");
assert((PASS_COUNT*BITS_PER_BUCKET) == (8*sizeof(int)));
printf("... OKn");
printf("Creating repeatable very-pseudo random test data ...");
int data[TEST_COUNT];
int x=13;
int i;
for (i=0;i<TEST_COUNT;i++) {
x=(x*x+i*i) % (2*x+i);
data[i]=x;
}
printf("... OKnData is ");
for (i=0;i<TEST_COUNT;i++) printf("%02x, ",data[i]);
printf("n");
printf("Creating bucket arrays ...");
int buckets[BUCKET_COUNT][TEST_COUNT];
int bucketlevel[BUCKET_COUNT];
for (i=0;i<BUCKET_COUNT;i++) bucketlevel[i]=0;
printf("... OKn");
for (i=0;i<PASS_COUNT;i++) {
int j,k,l;
printf("Running distribution pass #%d/%d ...",i,PASS_COUNT);
l=0;
for (j=0;j<TEST_COUNT;j++) {
k=(data[j]>>(BITS_PER_BUCKET*i)) & BUCKET_MASK;
buckets[k][bucketlevel[k]++]=data[j];
l|=k;
}
printf("... OKn");
if (!l) {
printf("Only zero digits found, sort completed earlyn");
break;
}
printf("Running gathering pass #%d/%d ...",i,PASS_COUNT);
l=0;
for (j=0;j<BUCKET_COUNT;j++) {
for (k=0;k<bucketlevel[j];k++) {
data[l++]=buckets[j][k];
}
bucketlevel[j]=0;
}
printf("... OKnData is ");
for (l=0;l<TEST_COUNT;l++) printf("%02x, ",data[l]);
printf("n");
}
}
用STL队列重写C++11中Louis的代码。
void bucket_sort(vector<int>& arr){
queue<int> buckets[10];
for(int digit = 1; digit <= 1e9; digit *= 10){
for(int elem : arr){
buckets[(elem/digit)%10].push(elem);
}
int idx = 0;
for(queue<int>& bucket : buckets){
while(!bucket.empty()){
arr[idx++] = bucket.front();
bucket.pop();
}
}
}
}