写作桶排序的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）将通过斗阵行按行循环，并返回的值复制到原来的数组。这就是所谓的聚集通。在preceding值的一维数组中的新订单为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];
}

我在想，为了用的，几十，几百，等对它们进行排序，我可以用这样的：

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;
        }
    }
}

备注使用二维数组桶浪费了大量的空间......队列的数组/列表，通常会更有意义。

Notes Using a 2d array for the bucket wastes a lot of space... an array of queues/lists usually makes more sense.

我不正常的程序在C ++和上面的code写的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屋！