尋找一個O（N）排序爲僅具有3個可能值

Question

我試圖延長以下代碼來對數組進行排序，如果我添加了一個第三值「C」的陣列。這將有可能做，而只保留一個循環。以下代碼將使用兩個可能的值「A」和「B」對數組進行排序。

public class TestSort 
{ 
    public static void main(String args[]) 
    { 
     char f[] = {'A','B','B','A','B','B','A','B','A','A','B'}; 
     int k = 0, t = f.length-1; 

     while(k < t) 
     { 
      if(f[k] == 'A') 
       k = k + 1; 
      else if(f[k] == 'B') 
      { 
       char m = f[t]; 
       f[t] = f[k]; 
       f[k] = m; 
       t = t - 1; 
      } 
     } 

     System.out.print("\nSorted List\n"); 
     for(char i : f) 
      System.out.print(i + ", "); 

     System.out.println(); 
    } 
} 

這是一種嘗試。我不知道我是否在正確的軌道上。

public class TestSort 
{ 
    static char f[] = {'C','A','B','A','C','B','A','B','C','C','B','A','B'}; 
    //static char f[] = {'A','A','A','A','A','C','A','C','A','A','C','A','C'}; 
    //static char f[] = {'C','B','B','B','C','B','B','B','C','C','B','C','B'}; 
    //static char f[] = {'A','B','B','B','A','B','C','B','A','A','B','A','B'}; 
    public static void main(String args[]) 
    { 
     int j = 0, k = 0, t = f.length-1, l = f.length-1; 

     while(t >= 0) 
     { 
      if(f[k] == 'A') 
       k = k + 1; 
      else if(f[k] == 'B') 
      { 
       char m = f[j]; 
       f[j] = f[k]; 
       f[k] = m; 
       j = j + 1; 
      } 
      else if(f[k] == 'C') 
      { 
       char m = f[l]; 
       f[l] = f[k]; 
       f[k] = m; 
       l = l - 1; 
      } 

     for(char i : f) 
      System.out.print(i + ", "); 

     System.out.println(); 
     } 
    } 
} 

Answer 1

也許是這樣的：

public sort(char[] array) { 
    int[] frequencies = new int[3]; 
    for(char c : array) { 
     if (c == 'A') 
      frequencies[0]++; 
     if (c == 'B') 
      frequencies[1]++; 
     if (c == 'C') 
      frequencies[2]++; 
    } 
    int index = 0; 
    for (int i = 0; i < frequencies[0]; i++) { 
     array[index++] = 'A'; 
    } 
    for (int i = 0; i < frequencies[1]; i++) { 
     array[index++] = 'B'; 
    } 
    for (int i = 0; i < frequencies[2]; i++) { 
     array[index++] = 'C'; 
    } 
} 

Answer 2

是要求 「保持O（N）」，或者 「保持一個循環」？

添加第二（非嵌套）循環不會改變爲O（n）的質量。那麼你可以分兩步進行：首先將所有的'A'推到第一位，然後第二個推'C'直到最後。