如何在C#中用双遍历算法按指定顺序排序数组且不使用库排序函数

需求说明 #

• 输入：随机字符串数组 [W, R, B, G, G, R, W, B]
• 期望输出：按R → W → B → G的顺序排序，结果为 [R, R, W, W, B, B, G, G]
• 实现要求：采用双遍历算法（Two-Pass Algorithm），禁止使用内置排序函数

当前问题 #

现有代码可将R移到左侧、G移到右侧，但中间的W和B顺序混乱，运行结果为 [R, R, B, W, W, B, G, G]，无法满足W在前、B在后的中间区域排序要求。

尝试过的代码 #

初始尝试代码 #

using System;
using System.Collections.Generic;
using System.Drawing;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<Color> colors = new List<Color>() { Color.White, Color.Red, Color.Green, Color.Blue }; // 随机数组
            int j = 0;
            int k = colors.Count;
            int i = 0;
            while (j < k)
            {
                if (colors[j] == Color.White)
                {
                    j += 1;
                }
                else if (colors[j] == Color.Blue)
                {
                    swap(colors[j], colors[--k]);
                    Console.WriteLine(colors[j]);
                }
                else
                {
                    swap(colors[j++], colors[i++]);
                }
                i += 1;
            }

            void swap(Color a, Color b)
            {
                Color temp = a;
                a = b;
                b = temp;
            }
        }
    }
}

EDIT 1：成功排序RRWWGG的代码 #

using System;
using System.Collections.Generic;
using System.Drawing;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<String> colors = new List<String>() { "W", "R", "G", "W", "R", "G"}; // 随机数组
            int start = 0;
            int end = colors.Count - 1;
            int current = 0;

            while (current <= end && start < end)
            {
                if(colors[current] == "R")
                {
                    swap(colors, current, start);
                    start++;
                    current++;
                }
                else if (colors[current] == "G")
                {
                    swap(colors, current, end);
                    end--;
                }
                else
                {
                    current++;
                }
            }
            for(int i = 0; i < colors.Count; i++)
            {
                Console.WriteLine(i+colors[i]);
            }
        }
        static void swap(List<String> colors, int a, int b)
        {
            String temp = colors[a];
            colors[a] = colors[b];
            colors[b] = temp;
        }
    }
}

加入B后出现问题的代码 #

using System;
using System.Collections.Generic;
using System.Drawing;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<String> colors = new List<String>() { "W", "R", "G", "W", "R", "G", "B", "B" }; // 随机数组
            int start = 0;
            int end = colors.Count - 1;
            int current = 0;

            while (current <= end && start < end)
            {
                if(colors[current] == "R")
                {
                    swap(colors, current, start);
                    start++;
                    current++;
                }
                else if (colors[current] == "G")
                {
                    swap(colors, current, end);
                    end--;
                }
                else
                {
                    current++;
                }
            }
            for(int i = 0; i < colors.Count; i++)
            {
                Console.WriteLine(i+colors[i]);
            }
        }
        static void swap(List<String> colors, int a, int b)
        {
            String temp = colors[a];
            colors[a] = colors[b];
            colors[b] = temp;
        }
    }
}

解决方案：双遍历算法实现 #

核心思路分两次遍历：

1. 第一次遍历：将所有R移到数组左侧，所有G移到数组右侧，中间区域留下W和B的混合集合
2. 第二次遍历：针对中间的W和B区域，将W移到左侧，B移到右侧，完成最终排序

修改后的代码如下：

using System;
using System.Collections.Generic;

namespace ConsoleApp5
{
    class Program2
    {
        static void Main(string[] args)
        {
            List<String> colors = new List<String>() { "W", "R", "B", "G", "G", "R", "W", "B" }; // 输入数组
            int start = 0;
            int end = colors.Count - 1;
            int current = 0;

            // 第一次遍历：处理R和G，将R放左，G放右，中间留W和B
            while (current <= end && start < end)
            {
                if (colors[current] == "R")
                {
                    swap(colors, current, start);
                    start++;
                    current++;
                }
                else if (colors[current] == "G")
                {
                    swap(colors, current, end);
                    end--;
                }
                else
                {
                    current++;
                }
            }

            // 第二次遍历：处理中间的W和B，将W放左，B放右
            int midStart = start;
            int midCurrent = start;
            while (midCurrent <= end)
            {
                if (colors[midCurrent] == "W")
                {
                    swap(colors, midCurrent, midStart);
                    midStart++;
                }
                midCurrent++;
            }

            // 输出结果
            Console.WriteLine("排序结果：");
            foreach (var color in colors)
            {
                Console.Write($"{color} ");
            }
        }

        static void swap(List<String> colors, int a, int b)
        {
            String temp = colors[a];
            colors[a] = colors[b];
            colors[b] = temp;
        }
    }
}

代码说明 #

• 第一次遍历完成后，数组结构为[R, R, B, W, W, B, G, G]，start指向中间区域的起始位置（索引2），end指向中间区域的结束位置（索引5）
• 第二次遍历仅在start到end的区间内操作，将所有W交换到该区间的左侧，最终得到[R, R, W, W, B, B, G, G]的目标结果

内容的提问来源于stack exchange，提问作者Misanthropia