Radix 정렬 재귀 적으로 구현 - 끝에 요소를 인쇄하는 방법?

Question

참고 :

나는 이미이 programm에 before에 특정 질문을하지만, 지금은 매우 마지막 단계에서 붙어있어 나는 그것을 위해 새 스레드를 엽니 다 좋을 것 같아요.

설명 : 나는 0에서 반복적으로 99999까지의 숫자를 정렬합니다을 programm을 구현하는 데 필요한거야

(이 기본적으로 기수의 일종이다). 프로세스 자체는 일종의 단순한 것입니다 : 사용자가 main 메소드에있는 숫자를 포함하는 배열을 입력합니다. 그런 다음 main 메소드는 sort-method를 호출합니다. 여기서는 10 행과 1 열의 'space'라는 2 차원 배열을 만듭니다. 그런 다음 배열의 모든 숫자를 첫 번째 실행에서 10.000이 될 숫자로 나눕니다. 예를 들어, 23456/10000 = 2,3456 = 2 (java)이므로, 프로그램은이 숫자를 [2] [0] 공백에 두 번째 행에 넣습니다. 그런 다음이 전체 행을 가져 와서 확장합니다.이 작업은 putInBucket 메서드에서 수행됩니다. 다른 번호를 같은 행에 넣을 수 있도록하기 위해이 작업을 수행합니다.

'numbers'배열 안에있는 모든 숫자에 대해이 작업을 수행합니다. 그런 다음이 행을 사용하여 같은 원리로 다시 정렬하기를 원하지만 두 번째 자릿수를 살펴 보겠습니다. 우리는 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로이 작업을 수행하려고합니다. 그래서, 우리의 두 번째 행과 같을 것이다 경우이

[23456, 24567],

우리는 3, 그렇게하기 위해 4, 우리는 각각의 순환에 자리/10를 계산 비교하려는 것 요구. 숫자가 0이면 더 이상 정렬 할 항목이 없습니다.

재귀 호출 자체는 0에서 9까지의 행을 사용하여 이전과는 다른 숫자로 입력하고 다른 행에 다시 입력하여 다시 정렬합니다.

질문 :

나는 programm에 어떻게해야 무엇 않습니다 생각합니다. 불행히도 결과를 올바르게 인쇄하는 방법을 모르겠습니다. 예를 들어, 아래 코드에서 main 메소드의 버킷을 출력하려했지만 방금 입력 한 배열 만 제공하므로 옳을 수는 없습니다.

행 9에있는 모든 요소로 시작해야합니다.이 행에 둘 이상의 숫자가 포함되어 있으면 재귀 호출에서 얻은 결과로 정렬해야합니다.

누구나 올바르게 구현하는 방법을 알고 있습니까? 미리 감사드립니다!

public static int[] sort(int[] numbers, int digit) { 

    if (numbers.length <= 1 || digits == 0) 
    return numbers; 

    int[][]space = new int[10][1]; 
    int i, j = 0; 

    for (j = 0; j < numbers.length; j++) { 
    i = numbers[j]/digit % 10; 
    space[i][0] = numbers[j]; 
    space[i] = putInBucket(space[i], numbers[j]); 
    } 

    digit = digit/10; 

    for (i = 0; i < 9; i++) { 
    sort(space[i], digit); 
    } 

    return numbers 

} 

private static int[] putInBucket(int[] bucket, int number) { 

    int[] bucket_new = new int[bucket.length+1]; 

    for (int i = 1; i < bucket_new.length; i++) { 
    bucket_new[i] = bucket[i-1]; 
    } 

    return bucket_new; 

} 

public static void main (String [] argv) { 

    int[] numbers = IO.readInts("Numbers: "); 
    int digit = 10000; 
    int[] bucket = sort(numbers, digit); 

    for (int i = 0; i < bucket.length; i++) { 
    System.out.println(bucket[i]); 

} 

Answer 1

내가 이전 질문에 내 answer에서 알 수 있듯이, 당신은 정렬 된 numbers를 반환해야합니다. 가장 작은 숫자에서 가장 큰 숫자까지 space을 통해 정렬 된 숫자를 얻습니다. 이를 위해

int k = 0; 

    for (i = 0; i < 10; i++) { 
     for (j = 0; j < len[i]; j++) { 
      numbers[k] = space[i][j]; 
      k++; 
     } 
    } 

, 당신은 아마 각 숫자합니다 (len[i] 변수)의 버킷의 길이를 추적해야합니다.

전체 솔루션은 다음과 같습니다

public static int[] sort(int[] numbers, int digit) { 

    if (numbers.length == 0 || digit <= 0) 
      return numbers; 

    int[][]space = new int[10][1]; 
    int[] len = new int[10]; 
    int i, j = 0; 

     for (j = 0; j < numbers.length; j++) { 
      i = (numbers[j]/digit) % 10; 
      len[i]++; 
      space[i] = putInBucket(space[i], numbers[j]); 
     } 


     for (i = 0; i < 10; i++) { 
      int[] bucket = new int[len[i]]; 
      for (int k = 0; k < len[i]; k++) 
       bucket[k] = space[i][k]; 
      space[i] = sort(bucket, digit/10); 
     } 

     int k = 0; 

     for (i = 0; i < 10; i++) { 
      for (j = 0; j < len[i]; j++) { 
       numbers[k] = space[i][j]; 
       k++; 
      } 
     } 

     return numbers; 

} 

private static int[] putInBucket(int[] bucket, int number) { 

    int[] bucket_new = new int[bucket.length+1]; 


    for (int i = 1; i < bucket_new.length; i++) { 
     bucket_new[i] = bucket[i-1]; 
    } 
    bucket_new[0] = number; 

    return bucket_new; 

} 

Answer 2

정렬 할 때 공간의 로컬 인스턴스가 업데이트되고 있지만 업데이트되지 않는 입력 매개 변수 번호가 반환됩니다.

스페이스가 하나 이상의 행에 데이터가 없을 수 있으므로 스페이스를 스페이스 [10] [0]로 초기화해야한다고 생각합니다.

이 항목이 오른쪽에서 왼쪽 자리 (기수가 가장 작은 자리) 기수 정렬일까요? 일반적으로 반복을 통해 이루어집니다 (각 외부 루프의 숫자로 다시 공간을 복사하십시오). 왼쪽에서 오른쪽으로의 기수 정렬 (가장 중요한 자리부터)은 종종 재귀를 사용하여 수행됩니다.

Bijay Gurung의 sort()는 다소 단순화 될 수 있습니다.댓글에서 언급 한 변경 :

public static int[] sort(int[] numbers, int digit) { 
    if (numbers.length == 0 || digit <= 0) 
     return numbers; 
    int[][]space = new int[10][0]; // [1] => [0] 
    int[] len = new int[10]; 
    int i, j; 
    for (j = 0; j < numbers.length; j++) { 
     i = (numbers[j]/digit) % 10; 
     len[i]++; 
     space[i] = putInBucket(space[i], numbers[j]); 
    } 
    for (i = 0; i < 10; i++) { 
    // int[] bucket = new int[len[i]];  // deleted 
    // for (int k = 0; k < len[i]; k++)  // deleted 
    //  bucket[k] = space[i][k];   // deleted 
     space[i] = sort(space[i], digit/10); // bucket => space[i] 
    } 
    int k = 0; 
    for (i = 0; i < 10; i++) { 
     for (j = 0; j < len[i]; j++) { 
      numbers[k] = space[i][j]; 
      k++; 
     } 
    } 
    return numbers; 
}