0

嗨，我需要一些帮助来改进我的代码。我正在尝试使用 Radixsort 按升序对 10 个数字的数组（例如）进行排序。

当我使用大小为 10 的数组运行程序并将 10 个随机 int 数放入 like 70 309 450 279 799 192 586 609 54 657

我明白了：

450 309 192 279 54 192 586 657 54 609

看不到我的错误在代码中的位置。

class IntQueue
{

  static class Hlekkur
  {
    int tala;
    Hlekkur naest;
  }

  Hlekkur fyrsti;
  Hlekkur sidasti;
  int n;

  public IntQueue()
  {
    fyrsti = sidasti = null;
  }


  // First number in queue.
  public int first()
  {
    return fyrsti.tala;
  }


  public int get()
  {
    int res = fyrsti.tala;
    n--;
    if( fyrsti == sidasti )
      fyrsti = sidasti = null;
    else
      fyrsti = fyrsti.naest;
    return res;
  }


  public void put( int i )
  {
    Hlekkur nyr = new Hlekkur();
    n++;
    nyr.tala = i;
    if( sidasti==null )
    f yrsti = sidasti = nyr;
    else
    {
      sidasti.naest = nyr;
      sidasti = nyr;
    }
  }


  public int count()
  {
    return n;
  }

  public static void radixSort(int [] q, int n, int d){
    IntQueue [] queue = new IntQueue[n];

    for (int k = 0; k < n; k++){
      queue[k] = new IntQueue();
    }
    for (int i = d-1; i >=0; i--){
      for (int j = 0; j < n; j++){
        while(queue[j].count() != 0)
        {
          queue[j].get();
        }
      }
      for (int index = 0; index < n; index++){
        // trying to look at one of three digit to sort after.
        int v=1;
        int digit = (q[index]/v)%10;
        v*=10;

        queue[digit].put(q[index]);
      }
      for (int p = 0; p < n; p++){
        while(queue[p].count() != 0) {
          q[p] = (queue[p].get());
        }
      }
    }
  }
}

我也在想我可以让函数将一个队列作为参数，并且在返回时该队列按递增顺序排列吗？如果有怎么办？

请帮忙。抱歉，如果我的英语不好，我的英语不太好。

如果您需要更多详细信息，请告知。

import java.util.Random;
public class RadTest extends IntQueue {

    public static void main(String[] args)
    {
        int [] q = new int[10];
        Random r = new Random();
        int t = 0;
        int size = 10;
        while(t != size)
        {
            q[t] = (r.nextInt(1000));
            t++;
        }

        for(int i = 0; i!= size; i++)
        {
            System.out.println(q[i]);
        }

        System.out.println("Radad: \n");
        radixSort(q,size,3);

        for(int i = 0; i!= size; i++)
        {
            System.out.println(q[i]);
        }

    }
}

希望这就是你所说的......

谢谢你的回答，我会调查的。不是找人帮我解决问题。寻求帮助和想法我如何解决它。

在我的任务中它说：

为使用队列排序的整数实现基数排序函数。该函数应将一个队列作为参数，并在返回时该队列应包含按升序排列的相同值 您可以假设这些值介于 0 和 999 之间。

我可以在我的队列上放 100 个 int 数字并使用 radixsort 函数对其进行排序，还是我需要将数字放入数组中，然后将数组放入使用队列的 radixsort 函数中？

我理解它就像我需要将数字放入 Int 队列并将该队列放入函数中但没有奏效。

但是感谢您的回答会查看它们并尝试解决我的问题。但是，如果您认为可以提供帮助，请发表评论。

4

3 回答 3

1

这适用于我尝试过的测试用例。它没有完全有据可查，但我认为没关系。我会把它留给你阅读，将它与你目前正在做的事情进行比较，并找出为什么你所拥有的在哲学上可能与我的不同。还有其他一些事情被标记在我用“懒惰”的方式做的地方，你应该用更好的方式来做。

import java.util.*;
class Radix {

    static int[] radixSort(int[] arr) {
        // Bucket is only used in this method, so I declare it here
        // I'm not 100% sure I recommend doing this in production code
        // but it turns out, it's perfectly legal to do!
        class Bucket {
            private List<Integer> list = new LinkedList<Integer>();
            int[] sorted;

            public void add(int i) { list.add(i);  sorted = null;}

            public int[] getSortedArray() {
                if(sorted == null) {
                    sorted = new int[list.size()];
                    int i = 0;
                    for(Integer val : list) {
                        sorted[i++] = val.intValue(); // probably could autobox, oh well
                    }
                    Arrays.sort(sorted); // use whatever method you want to sort here... 
                                         // Arrays.sort probably isn't allowed
                }
                return sorted;
            }
        }

        int maxLen = 0;
        for(int i : arr) {
            if(i < 0) throw new IllegalArgumentException("I don't deal with negative numbers");
            int len = numKeys(i);
            if(len > maxLen) maxLen = len;
        }

        Bucket[] buckets = new Bucket[maxLen];

        for(int i = 0; i < buckets.length; i++) buckets[i] = new Bucket();
        for(int i : arr) buckets[numKeys(i)-1].add(i);

        int[] result = new int[arr.length];
        int[] posarr = new int[buckets.length]; // all int to 0

        for(int i = 0; i < result.length; i++) {
            // get the 'best' element, which will be the most appropriate from
            // the set of earliest unused elements from each bucket
            int best = -1;
            int bestpos = -1;
            for(int p = 0; p < posarr.length; p++) {
                if(posarr[p] == buckets[p].getSortedArray().length) continue;
                int oldbest = best;
                best = bestOf(best, buckets[p].getSortedArray()[posarr[p]]);
                if(best != oldbest) {
                    bestpos = p;
                }


            }
            posarr[bestpos]++;
            result[i] = best;
        }

        return result;

    }

    static int bestOf(int a, int b) {
        if(a == -1) return b;
        // you'll have to write this yourself :)
        String as = a+"";
        String bs = b+"";
        if(as.compareTo(bs) < 0) return a;
        return b;
    }

    static int numKeys(int i) {
        if(i < 0) throw new IllegalArgumentException("I don't deal with negative numbers");
        if(i == 0) return 1;
        //return (i+"").length(); // lame method :}
        int len = 0;
        while(i > 0) {
            len++;
            i /= 10;
        }
        return len;
    }

    public static void main(String[] args) {

        int[] test = {1, 6, 31, 65, 143, 316, 93, 736};
        int[] res = radixSort(test);
        for(int i : res) System.out.println(i);
    }
}
于 2011-02-17T23:25:02.833 回答
0

好吧，如果不发布解决方案，我认为我无能为力（只是给出提示更累，我有点累，抱歉），所以我将提供一个不错的小模糊测试，以便您测试您的解决方案。听上去怎么样？:-)

如果您正在实施某种算法，那么提出一个好的模糊测试器总是一个好主意。虽然不能 100% 确定它是否与您的实现一起运行，但它是否会起作用（基数排序没有任何奇怪的边缘情况，我知道这种情况很少发生）

private static void fuzztest() throws Exception{
    Random rnd = new Random();
    int testcnt = 0;
    final int NR_TESTS = 10000;
    // Maximum size of array.
    final int MAX_DATA_LENGTH = 1000;
    // Maximum value allowed for each integer. 
    final int MAX_SIZE = Integer.MAX_VALUE; 

    while(testcnt < NR_TESTS){
     int len = rnd.nextInt(MAX_DATA_LENGTH) + 1;
     Integer[] array = new Integer[len];
     Integer[] radix = new Integer[len];

     for(int i = 0; i < len; i++){
      array[i] = rnd.nextInt(MAX_SIZE);
      radix[i] = new Integer(array[i]);
     }

     Arrays.sort(array);
     sort(radix);  // use your own sort function here.

     for(int i = 0; i < len; i++){
      if(array[i].compareTo(radix[i]) != 0){
       throw new Exception("Not sorted!");
      }
     }
     System.out.println(testcnt);
     testcnt++;
    }
于 2011-02-18T00:05:09.843 回答
0

一件事看起来很奇怪：

  for (int p = 0; p < n; p++){
    while(queue[p].count() != 0) {
      q[p] = (queue[p].get());
    }
  }

p 应该是 q 中的索引，范围从 0 到 n-1，还是队列中的索引，范围从 0 到 9？两者都不太可能...

其他：

  for (int index = 0; index < n; index++){
    // trying to look at one of three digit to sort after.
    int v=1;
    int digit = (q[index]/v)%10;
    v*=10;

    queue[digit].put(q[index]);
  }

为什么你将 v 乘以 10，只是在下一次迭代中用 v = 1 覆盖它？您是否知道 v 将始终为一，因此您将在每次迭代中查看相同的数字？

于 2011-02-17T23:15:13.667 回答