Ищем 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).затем вы можете сделать это в два этапа: сначала подтолкнуть все буквы «А» к началу, а второй - нажать все «С» до конца.