二维桶排序问题

Question

请不要让 post 的长度吓到您！好的，这是我目前正在处理的提示：

"编写一个名为 BucketSort 的 class，其中包含一个名为 sort 的方法：

a) 根据值的“ones”（最右边）数字，将一维数组的每个值放入桶数组的一行中。例如，97 放在第 7 行，3 放在第 3 行，100 放在第 0 行。此过程称为分配传递。

b) 逐行循环遍历桶数组，并将值复制回原始数组。此过程称为收集过程。一维数组中前面值的新顺序为100、3、97。

c) 对每个后续数字位置（十位、百位、千位等）重复此过程。在第二次（十位）传递时，100 放在第 0 行，3 放在第 0 行（因为 3没有十位）并且 97 位于第 9 行。在收集通过后，一维数组中值的顺序为 100、3 和 97。在第三次（百位）通过时，100 位于行1、3 放在第 0 行，97 放在第 0 行（在 3 之后）在最后一次收集通过后，原始数组按排序顺序排列。正在排序。

这种排序技术提供了比冒泡排序更好的性能，但需要更多的内存——冒泡排序只需要 space 来处理一个额外的数据元素。此比较是 space/time 权衡的示例：桶排序比冒泡排序使用更多内存，但性能更好。此版本的桶排序需要在每次传递时将所有数据复制回原始数组。另一种可能性是创建第二个二维桶数组并在两个桶数组之间重复交换数据。桶的二维数组是整型数组长度的10倍

我知道有点满嘴。到目前为止，下面是我的代码，但我无法弄清楚为什么它不会以正确的顺序打印，我认为是时候重新审视了。任何想法表示赞赏，谢谢！

import java.util.Arrays;

public class BucketSort_main {

public static void main(String[] args) 
{  
    int[] numbers = new int [5]; 
    int[] tnumbers = new int [500]; 
    int [][] bucket = new int [10][numbers.length]; 
    int [] a = new int [10]; 
    int count = 0;
    int divisor = 1; 
    int cnt = 1; 
    boolean moreDigits = true; 




    for (int s = 0; s < 10; s++)
        {
            a[s] = 0; 
        }

    for (int b = 0; b < numbers.length; b++) 
    { 
        numbers [b] = (int)(Math.random()*2000); 
        tnumbers [b] = numbers [b]; 
    } 

    int[] tmpSort = new int[10]; 


    while (moreDigits)         
    { 
          moreDigits = false; 
          for (int i = 0; i < tmpSort.length; i++) 
          { 
              tmpSort[i]= -1;  // hint hint 
          } 
          for (int i = 0; i < numbers.length; i++) 
          { 
            int tmp = tnumbers[i] / divisor; 

            if (tmp/10 != 0)
                {
                    moreDigits = true; 
                }

            int digit = tmp % 10; 

            tmpSort[digit] = tnumbers[i];  // hint hint 

            System.out.println("Number["+i+"], Digit "+cnt+" is "+digit + ". Full number = " + tnumbers[i]); 

            bucket [digit][a[digit]] = tnumbers[i]; 

            System.out.println ("Digit " + digit + " going to slot " + a[digit] + ". " + bucket[digit][a[digit]]); 
            System.out.println (" "); 

            a[digit]++; 

        }     
        cnt++; 
        divisor *= 10; 

        for (int x = 0; x < 10; x++) 
        { 
            a [x] = 0; 
            for (int y = 0; y < numbers.length; y++) 
            { 
                if (bucket[x][y] != 0) 
                { 
                    tnumbers [y] = 0; 
                    tnumbers [y] = bucket[x][y]; 
                    bucket[x][y] = 0; 
                }                     
            }  
        }  
     }     

            for (int o = 0; o < numbers.length; o++) 
            { 
                System.out.println (tnumbers[o]); 
            }

        } 
 }

Answer 1

问题在这里：

for (int x = 0; x < 10; x++) 
        { 
            a [x] = 0; 
            for (int y = 0; y < numbers.length; y++) 
            { 
                if (bucket[x][y] != 0) 
                { 
                    tnumbers [y] = 0; 
                    tnumbers [y] = bucket[x][y]; 
                    bucket[x][y] = 0; 
                }                     
            }  
        }

您正在使用相同的 y 从存储桶中获取值并将值分配给 tnumbers。因此，当您第二次循环 y 时，您将在 tnumbers[0]、tnumbers[1] 等处重新开始...

解决这个问题，你的代码就可以正常工作了。

二维桶排序问题

2D bucket sort issue

java

bucket-sort