ソートをソートする理由累積を使用する理由

Question

多くのWebサイトでソートカウントのコードを調べました。 彼らは、累計のカウントを使用しており、さらに配列のインデックス付けを行っています。 通常の配列印刷を使用していないのはなぜですか？

[count（origArray（i））！= 0]の[origArray（i）の数]と同様に、ループスルーカウント（origArray（i））印刷してください。

これは、カウントソートを使用する主な点はNO COMPARISONであり、私のコードでは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をソートする場合は、キャストが必要なため、これは当てはまります。

整数を使用しているため、実装に間違いはありません。実際には、Wikipediaで言及されているアルゴリズムのバリエーションの1つで終わった：

ソートする各アイテム自体が整数で、キーとしても使用されている場合、カウントの2番目と3番目のループ並べ替えを組み合わせることができます。 2番目のループでは、キーの項目を出力に配置する位置を計算する代わりに、数字iのCount[i]のコピーを出力に追加するだけです。

Answer 2

累積合計は、繰り返しを数えることである：あなたは、アレイ内の3倍の値200を有することができます。この場合、count[200]の値は3になります。したがって、3回印刷する必要があります（最後のコードはforです）。

ソートアルゴリズムでは、「比較」とは配列の値を互いに比較することを意味します。このアルゴリズムにはそのような比較はありません。

O（n）ではこのアルゴリズムが複雑ですが、ソートする値が大きい場合は大量のストレージが必要です。