Looking for a O(N) sort for an array with only 3 possible values

I am trying to extend the following code to sort the array if I added a third value 'C'. Would this be possible to do while retaining only one loop. The following code will sort an array with two possible values 'A' and '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();
    }
}

Here is an attempt. I don't know if I'm on the right track.

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 =开发者_Python百科 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();
        }
    }
}

---

Maybe something like:

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';
    }
}

---

Is the requirement "keep it O(n)", or "keep one loop" ?

Adding a second (non-nested) loop wouldn't change the O(n) quality. then you could do it in two steps: first push all the 'A's to the start and a second one to push all the 'C's to the end.