排序三种球的算法

Question

我们有三种不同类型的N球:红色(r),蓝色(b)和白色(w).

我需要对它们进行排序,以便红球出现第一,然后是所有白球,最后是所有蓝球.

例:

在:bwrwrbbrwwrb

string[] arrBalls = { "b", "w", "r", "w", "r", "b", "b", "r", "w", "w", "r", "b" };

输出:rrrrwwwwbbbb

我需要找到一个线性O(n)算法.

更新: C#代码

 string[] arrBalls = { "b", "w", "r", "w", "r", "b", "b", "r", "w", "w", "r", "b" };
 int index_red = 0;
 int index_blue = arrBalls.Length - 1;

 for (int i = 0; i < arrBalls.Length; i++)
            {
                if (arrBalls[i] == "r" && index_red != i)
                {
                    string TempRed = arrBalls[index_red];
                    arrBalls[index_red] = arrBalls[i];
                    arrBalls[i] = TempRed;
                    if (arrBalls[index_red] == "r")
                    {
                        while(arrBalls[index_red] == "r")index_red++;
                    }
                    else
                    {
                        index_red++;
                    }


                }


                if (arrBalls[i] == "b" && index_blue != i)
                {
                    string TempRed = arrBalls[index_blue];
                    arrBalls[index_blue] = arrBalls[i];
                    arrBalls[i] = TempRed;

                    if (arrBalls[index_blue] == "b")
                    {
                        while (arrBalls[index_blue] == "b") index_blue--;
                    }
                    else
                    {
                        index_blue--;
                    }
                }


            }

Answer 1

您将三种类型的球中的每一种计算为3个变量.假设您计算了R红球,B蓝球和W白球.然后,你的输出R "r",随后W "w",其次是B "b".