Java 基数排序

Question

欢迎。我有一个基数排序方法，它使用一个数组来遍历，但必须有另一个数组（bin）来存储在一个空队列中。我很困惑如何为垃圾箱排队。我还有一个 findPlace 方法，可以在调用时找到每个数字的位置。所以，这就是我得到的。有人可以帮我找到我缺少的东西吗？非常感谢您抽出时间。

public static void radix(int [] list){
       int [] bin = new int[10]; 
      ArrayQueue<Integer> part = new ArrayQueue<Integer>(); // EDIT What would I do with this queue?? 
      int num = 0; 
         for(int i=0;i<list.length;i++)
         {
            bin[i] = 0;  
          }

            for(int pass=0;pass<list.length;pass++)
           {
                for(int num=0;num<list.length;num++)
               {
                       int digit=findPlace(bin[pass], num);
                 }

                  bin[digit].add(list[num]); // add to the bin
            }
              // Put back into list
               for(int h=0; h<10; h++)
               {
                    while(!bin[h].isEmpty())
                    {
                       list[num] = bin[queueNum].remove();
                     num++;
                    }
              }
        }


public static int getPlace (int x, int place)
    {return x/place % 10;}

我还制作了一个方法来查找存储桶，所以我只需要知道如何将其放入数组中，我会这样做吗？部分.add(getPlace(x, 地点));?

Answer 1

您的数组 bin 不会仅仅因为您希望它像队列一样工作:) 数组没有像 add() 和 remove() 这样的方法。关于如何解决此问题，您有两种选择：

• 自行编写正确处理队列的程序：队列由一个数组和两个指向该数组的指针组成，传统上称为 head 和 tail。您必须编写自己的方法来添加和删除，这些方法将与数组和指针一起使用，并处理空队列或溢出队列。

• 使用Java的内置Queue类。它记录在库的 Javadocs 中。不过，不知道您的作业是否打算让您构建自己的队列。

更新另一个细节：

您询问如何从数字中提取单个数字。正如维基百科文章中所建议的，从最低有效数字 (LSD) 开始工作是最简单的。为此：

• 要提取最后一位数字，请执行 digit = number % 10 （这是模运算）。您将得到一个 0 到 9 之间的整数（含 0 和 9）。
• 要去掉最后一位数字，只需除以 10。然后你就可以去掉另一个数字。
• 由于您需要多次查看数字的倒数第 n 个数字，因此最好将此功能放入单独的方法中。

您可以使用 0 到 9 选择正确的队列来放置您的号码。

当您将所有号码排入 10 个存储桶后，您需要将它们从那里复制回单个列表中。然后，只要任何数字中仍有未处理的数字，就重复此操作。