写入桶排序在c ++ [英] Writing bucket sort in c++
问题描述
一本书我说:
a)根据值的个位数将一维数组的每个值放入桶数组的一行。例如,97被放置在行7中,3被放置在行3中,并且100被放置在行0中。这被称为分配通行证。
a) Place each value of the one-dimensional array into a row of the bucket array based on the value's ones digit. For example, 97 is placed in row 7, 3 is placed in row 3, and 100 is placed in row 0. This is called a "distribution pass."
b )逐行循环通过桶阵列,并将值复制回原始数组。这被称为收集通行证。一维数组中上述值的新顺序为100,3和97.
b) Loop through the bucket array row by row, and copy the values back to the original array. This is called a "gathering pass." The new order of the preceding values in the one-dimensional array is 100, 3, and 97.
c)对每个后续数字位置重复此过程。
c) Repeat this process for each subsequent digit position.
我有很多麻烦试图理解和实现这个。到目前为止我有:
I am having a lot of trouble trying to understand and implement this. So far I have:
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];
}
我想是为了排序他们, ,etc,我可以使用这个:
I'm thinking that in order to sort them by ones, tens, hundreds, etc, I can use this:
for(int i = 0; i < max; ++i)
insert = (array[i] / x) % 10;
bucket[insert];
其中x = 1,10,100,1000等我完全失去了如何写
where x = 1, 10, 100, 1000, etc. I am totally lost on how to write this now.
推荐答案
这里是根据OP问题中的信息进行桶排序。
Here's a bucket sort based on the info in the OP question.
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;
}
}
}
strong>对于bucket使用2d数组会浪费很多空间...一个队列/列表数组通常更有意义。
Notes Using a 2d array for the bucket wastes a lot of space... an array of queues/lists usually makes more sense.
我通常不编程C ++和上面的代码是写在web浏览器中,所以语法错误可能存在。
I don't normally program in C++ and the above code was written inside the web browser, so syntax errors may exist.
这篇关于写入桶排序在c ++的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!