計數排序，爲什麼要使用累計

我經歷了許多網站的計數排序代碼。他們正在使用count的累加和，然後進一步數組索引。我打算問爲什麼他們不使用正常的數組打印：計數排序，爲什麼要使用累計

如果[count（origArray（i））！= 0]中的origArray（i）的計數，循環計數（origArray（i））並打印我。

這是因爲使用Counting排序的要點是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); 
      } 
     } 
    } 

}

來源

2016-05-31 Nikhil Verma

「無比較」意味着密鑰不會相互比較以確定它們的相對順序。除了少許冗餘之外，你認爲你的代碼有什麼問題？ – dasblinkenlight

沒什麼錯，在其他網站上他們使用了總和的概念，所以我認爲這個實現可能有問題。 –

什麼冗餘？ –

您共享的鏈接上的實現不打印System.out.print(" " + i)，因爲它們認爲i與正在排序的項目不同。如果你想對char進行排序，這將是真實的，因爲你需要一個演員陣容。

由於您使用的是整數，因此您的實現沒有任何問題。事實上，您最終得到了Wikipedia上提到的算法的其中一種變體：

如果要排序的每個項目本身都是一個整數，並且也用作鍵，那麼第二個和第三個循環的計數排序可以合併;在第二個循環中，不要計算應在輸出中放置密鑰爲i的項目的位置，只需在輸出中附加Count[i]i的副本。

來源

2016-05-31 09:17:34 dasblinkenlight

中累積計數的重複：你可能有3倍，價值200的陣列英寸在這種情況下，count[200]將具有值3.因此，您需要打印它三次（代碼中的最後一個for循環）。

在排序算法中，「比較」意味着比較數組的值彼此。這種算法沒有這種比較。

該算法在O（n）中的複雜度，但如果要排序的值可能很大，則需要大量存儲。

來源

2016-05-31 08:53:26 AhmadWabbi

計數排序，爲什麼要使用累計

回答

相關問題