java - java帮助中的基数排序

Question

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

当我运行大小为 10 的数组的程序并放入 10 个随机 int 数字时 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]);
        }

    }
}

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

<小时/>

谢谢你的回答，我会研究一下。不是找人来帮我解决问题。寻求帮助和想法如何解决它。

在我的任务中它说:

Implement a radix sort function for integers that sorts with queues. The function should take one queue as an argument and on return that queue should contain the same values in ascending order You may assume that the values are between 0 and 999.

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

我理解它就像我需要将数字放入 Int 队列中并将该队列放入函数中，但这并没有起作用。

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

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