누적 계산을 사용하는 이유는 무엇입니까?

Question

많은 웹 사이트에서 정렬 계산 코드를 검토했습니다. 그들은 누적 합계를 사용한 다음 배열 인덱싱을 사용하고 있습니다. 일반 배열 인쇄를 사용하지 않는 이유는 무엇입니까?

[count (origArray (i))! = 0]에있는 origArray (i)의 수와 같이 루프 수 (origArray 및 인쇄.

카운팅 정렬을 사용하는 주된 점은 비교가없고 내 코드에서 0과 비교되기 때문입니다.

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Arrays; 

public class CountingSort { 
    public static void main(String... args) throws IOException { 
     new CountingSort().sort(); 
    } 

    private void sort() throws IOException { 
     BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 
     String line; 
     int max = 0; 
     String data = ""; 
     while ((line = reader.readLine()) != null && line.length() != 0) { 
      data += line; 
     } 
     String[] ip = data.split(" "); 
     int[] intArray = new int[ip.length]; 
     for (int i = 0; i < ip.length; i++) { 
      intArray[i] = Integer.parseInt(ip[i]); 
      if (intArray[i] > max) 
       max = intArray[i]; 
     } 
     int[] count = new int[max+1]; 
     Arrays.fill(count, 0); 
     for (int i = 0; i < intArray.length; i++) { 
      ++count[intArray[i]]; 
     } 
     for (int i = 0; i < max; i++) { 
      if (count[i] != 0) { 
       for (int j = 0; j < count[i]; j++) 
        System.out.print(" " + i); 
      } 
     } 
    } 

} 

Answer 1

i이 정렬중인 항목과 다르기 때문에 공유하는 링크의 구현에서 System.out.print(" " + i)을 인쇄하지 않습니다. 캐스트가 필요하기 때문에 char을 정렬하려면 true입니다.

정수를 사용하고 있으므로 구현에 이상이 없습니다. 계산의

각 항목이 분류 자체 정수이고,뿐만 아니라, 키로서 사용되는 경우, 두 번째와 세 번째 루프 : 사실, 당신은 위키 백과에 언급 된 알고리즘의 변화 중 하나 결국 정렬을 결합 할 수 있습니다. 두 번째 루프에서는 i 키가있는 항목을 출력에 배치해야하는 위치를 계산하는 대신 i 복사본의 Count[i] 복사본을 출력에 추가하기 만하면됩니다.

Answer 2

누적 합계가 반복을 계산하는 것입니다 :

이 코드를 참조하십시오 당신이 당신의 배열에 3 배 값 (200)을 가질 수있다. 이 경우 count[200]의 값은 3입니다. 따라서 코드를 세 번 인쇄해야합니다 (코드에 마지막으로 for 루프가 있음).

정렬 알고리즘에서 "비교"는 배열의 값을 서로 비교하는 것을 의미합니다. 이 알고리즘에는 이러한 비교가 없습니다.

O (n)에서이 알고리즘의 복잡성이 있지만 정렬 할 값이 클 경우 많은 저장 공간이 필요합니다.