c++ - 用c++写桶排序

Question

我有一本书是这样说的:

a) 根据值的个位将一维数组的每个值放入桶数组的一行中。例如，97放在第7行，3放在第3行，100放在第0行。这称为“分布传递”。

b) 逐行循环遍历桶数组，并将值复制回原始数组。这称为“聚集通行证”。一维数组中前面值的新顺序为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];
}

我在想，为了按个位、十位、百位等对它们进行排序，我可以使用这个:

for(int i = 0; i < max; ++i)
    insert = (array[i] / x) % 10;
    bucket[insert];

其中 x = 1、10、100、1000 等。我现在完全不知道如何写这个。

Answer 1

这是基于 OP 问题中信息的桶排序。

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

注释 为桶使用二维数组会浪费大量空间……队列/列表数组通常更有意义。

我通常不会用 C++ 编程，上面的代码是在网络浏览器中编写的，因此可能存在语法错误。