如何在 C# 中对 characters/string 输入实现归并排序？

Question

更新：感谢@AdrianHHH 的提示和@steveOh 对我的正确阵列的修复以及大家的建议。现在是运行，但它给了我一个不同的答案。例如，冒泡排序会将“程序”排序为“agmoprr”，但我的合并排序会将其排序为“gpramro”。冒泡排序已经作为示例给出，我测试了 java 程序的输入：“程序”输出：“程序”，这不是我想要的，但如果你在它们之间放置空格，它将排序为“agmoprr”这与冒泡排序相同。

我目前正在调试，但我真的需要帮助，这是我第二次调试，因为我们很少进行算法实现。也谢谢大家的检查和指正。

我正在尝试转换为 C# 的 Java 中的字符串合并排序：

    public static void mergeSort(List<String> list){
    // need base case - should be a single if statement
    if (list.size() > 1){
        List<String> left = new LinkedList<>(list.subList(0, list.size() / 2));
        List<String> right = new LinkedList<>(list.subList(list.size() / 2, list.size()));

        // recursively sort the two halves
        mergeSort(left);
        mergeSort(right);

        // merge the sorted left and right subLists together
        merge(list, left, right);
    }
}

public static void merge(List<String> result, List<String> left, List<String> right){
    int i1 = 0; // index for left
    int i2 = 0; // index for right

    for (int i = 0; i < result.size(); i++) {
        if (i2 >= right.size() || (i1 < left.size() && left.get(i1).compareToIgnoreCase(right.get(i2)) < 0)){
            result.remove(i);
            result.add(i, left.get(i1));
            i1++;
        } else {
            result.remove(i);
            result.add(i, right.get(i2));
            i2++;
        }
    }

C# 中转换的字符串合并排序：（给出不同的输出“gpramro”）

public class MergeSort : ISortStrategy
{
    public string Sort(string input)
    {
        var result = "";

        int size = (input.Length % 2 == 0) ? input.Length / 2 : (input.Length + 1) / 2;

        if (input.Length > 1)
        {
            char[] left = input.Substring(0, input.Length / 2).ToCharArray();
            char[] right = input.Substring(input.Length / 2,input.Length - (input.Length / 2)).ToCharArray();

            // recursively sort the two halves
            Sort(left.Length.ToString());
            Sort(right.Length.ToString());

            // merge the sorted left and right subLists together
            result = merge(input, left, right);
        }

        return result;
    }

    public string merge(string result, char[] left, char[] right)
    {
        int i1 = 0; // index for left
        int i2 = 0; // index for right

        var theString = result;
        var aStringBuilder = new StringBuilder(theString);

        for (int i = 0; i < aStringBuilder.Length; i++)
        {
            if (i2 >= right.Length || (i1 < left.Length && left.GetValue(i1).ToString().CompareTo(right.GetValue(i2).ToString()) < 0))
            {
                aStringBuilder.Remove(i, 1);
                aStringBuilder.Insert(i, left.GetValue(i1).ToString());
                i1++;
            }
            else
            {
                aStringBuilder.Remove(i, 1);
                aStringBuilder.Insert(i, right.GetValue(i2).ToString());
                i2++;
            }
        }

        theString = aStringBuilder.ToString();
        return theString;

    }
}

接口 - 接口和冒泡排序已经给出，所以如果我更改接口，那么我必须更改冒泡排序和快速排序，但两者都已经实现了。

    public interface ISortStrategy
{
    string Sort(string input);
}

冒泡排序 - 作为样本给出

    public string Sort(string input)
    {
        var result = "";
        var arr = input.ToCharArray();
        char temp;

        for (int write = 0; write < arr.Length; write++)
        {
            for (int sort = 0; sort < arr.Length - 1; sort++)
            {
                if (arr[sort] > arr[sort + 1])
                {
                    temp = arr[sort + 1];
                    arr[sort + 1] = arr[sort];
                    arr[sort] = temp;
                }
            }
        }

        for (int i = 0; i < arr.Length; i++)
            result += arr[i];

        return result;
    }

快速排序 - 使用给定接口完成

        public string Sort(string input)
    {
        char[] charactersToSort = input.ToCharArray();
        int low = 0;
        int high = charactersToSort.Length - 1;
        quickSort(charactersToSort, low, high);
        return new string(charactersToSort);
    }

Answer 1

让我们以您提供的“程序”输入字符串为例。

我做的第一个改变是从字符数组和字符串的混合体切换到纯粹的字符列表。您面临的问题之一是当您再次调用 Sort 时，您传入了左右数组的长度，而不是数组本身。这已在提供的代码中得到纠正。

找到了这段代码的大体结构here，我简单地把它转换成字符串版本。

新ISortStrategy.cs:

public interface ISortStrategy
{
    List<char> Sort(List<char> input);
}

新MergeSort.cs:

public class MergeSort : ISortStrategy
{
    public List<char> Sort(List<char> unsorted)
    {
        if (unsorted.Count <= 1)
            return unsorted;

        List<char> left = new();
        List<char> right = new();

        int middle = unsorted.Count / 2;
        for (int i = 0; i < middle; i++)
            left.Add(unsorted[i]);
        for (int i = middle; i < unsorted.Count; i++)
            right.Add(unsorted[i]);

        left = Sort(left);
        right = Sort(right);
        return Merge(left, right);
    }
    
    private List<char> Merge(ICollection<char> left, ICollection<char> right)
    {
        List<char> result = new();

        while (left.Count > 0 || right.Count > 0)
        {
            switch (left.Count)
            {
                case > 0 when right.Count > 0:
                {
                    if ((left.First() % 32) <= (right.First() % 32))
                    {
                        result.Add(left.First());
                        left.Remove(left.First());
                    }
                    else
                    {
                        result.Add(right.First());
                        right.Remove(right.First());
                    }

                    break;
                }
                case > 0:
                    result.Add(left.First());
                    left.Remove(left.First());
                    break;
                default:
                {
                    if (right.Count > 0)
                    {
                        result.Add(right.First());

                        right.Remove(right.First());    
                    }

                    break;
                }
            }
        }
        return result;
    }
}

排序系统的新实现：

string result = new(new MergeSort().Sort("program".ToList()).ToArray());
Console.WriteLine(result);

将此代码与输入字符串“program”一起使用时，输出应为“agmoprr”

如何在 C# 中对 characters/string 输入实现归并排序？

How to implement merge sort on characters/string input in C#?

c#

sorting

algorithm

mergesort