Radix сортировать в справке Java

Question

Привет, мне нужна помощь, чтобы улучшить мой код.Я пытаюсь использовать Radixsort для сортировки массива из 10 чисел (например) в порядке возрастания.

Когда я запускаю программу с массивом размером 10 и помещаю 10 случайных чисел типа как 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 и поместить эту очередь в функцию, но это не сработало.

Но спасибо за ваши ответы, посмотрю на них и попробую решить мою проблему.Но если вы думаете, что можете помочь, пожалуйста, оставьте комментарий.

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

Answer 2

Ну, я не думаю, что смогу помочь, почти не опубликовав решение (просто давать подсказки более утомительно, и я немного устал, извините), так что я просто добавлю хороший небольшой нечеткий тест, чтобы вы могли проверить ваше решение. Как это звучит? : -)

Если вы реализуете какой-то алгоритм, всегда неплохо придумать хороший fuzztester. Хотя нет 100% уверенности, если это работает с вашими шансами на реализацию, это сработает (у radix-сортировки нет никаких странных крайних случаев, я знаю, что это случается крайне редко)

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++;
    }        

Answer 3

Одна вещь, которая выглядит странно:

  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 всегда будет одним, и поэтому вы будете смотреть на одну и ту же цифру в каждой итерации?