java - 二维桶排序问题

Question

请不要让这篇文章的长度吓到您!好的，这是我当前正在处理的提示:

<小时/>

“编写一个名为 BucketSort 的类，其中包含一个名为 sort 的方法:

a) 根据值的“个”(最右边)数字，将一维数组的每个值放入存储桶数组的一行中。例如，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 之后)。在最后一次聚集之后，原始数组已按排序顺序排列。正在排序中。

这种排序技术比冒泡排序提供更好的性能，但需要更多的内存 - 冒泡排序仅需要一个额外的数据元素的空间。此比较是空间/时间权衡的一个示例:桶排序比冒泡排序使用更多内存，但性能更好。此版本的桶排序需要在每次传递时将所有数据复制回原始数组。另一种可能性是创建第二个二维桶数组并在两个桶数组之间重复交换数据。桶的二维数组是整数数组长度的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] 等处重新开始。 .

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