java - Java 字符串合并排序

Question

我正在编写一个程序来合并字符串中的排序单词。但是当我运行我的鳕鱼时，它似乎在某些地方丢失了一些数据。我用字符串测试了它:“ Hello World ，猫坐在该死的垫子上”但我得到的只是[血腥，猫，你好，垫]

这是我的代码:

package mergeSort;

import java.util.LinkedList;

public class mergeSort
{
    public static String sort(String userInput)
    {
        if (userInput == null)
        {
            return "";
        }
        LinkedList<String> input = toList(userInput);

        String output = MergeSort(input).toString();

        return output;
    }

    private static LinkedList<String> toList(String input)
    {
        LinkedList<String> output = new LinkedList<String>();
        String[] array = input.split("\\s");

        for (String element : array)
        {
            output.addFirst(element);
        }
        return (output);
    }

    private static LinkedList<String> MergeSort(LinkedList<String> inputstring)
    {
        LinkedList<String> sequence1 = new LinkedList<String>();
        LinkedList<String> sequence2 = new LinkedList<String>();

        if (inputstring.size() <= 1)
        {
            return inputstring;
        }

        for (int index = 0; index <= (inputstring.size() / 2); index++)
        {
            sequence1.addLast(inputstring.removeFirst());
        }
        while (!(inputstring.isEmpty()))
        {
            sequence2.addLast(inputstring.removeFirst());
        }

        sequence1 = MergeSort(sequence1);
        sequence2 = MergeSort(sequence2);

        return merge(sequence1, sequence2);
    }

    private static LinkedList<String> merge(LinkedList<String> sequence1,
            LinkedList<String> sequence2)
    {
        LinkedList<String> merged = new LinkedList<String>();

        while (!(sequence1.isEmpty()) && !(sequence2.isEmpty()))
        {
            if (sequence1.peekFirst().compareTo(sequence2.peekFirst()) < 0)
            {
                merged.addLast(sequence1.removeFirst());
            }
            else
            {
                merged.addLast(sequence2.removeFirst());
            }
        }

        while (!(sequence1.isEmpty()))
        {
            merged.addLast(sequence1.removeFirst());
        }
        while (!(sequence1.isEmpty()))
        {
            merged.addLast(sequence2.removeFirst());
        }

        return (merged);
    }
}

测试者类:

package mergeSort;

public class mainTester
{

    public static void main(String[] args)
    {
        String test = "hello world the cat sat on the bloody mat";

        System.out.println(mergeSort.sort(test));

        System.exit(0);

    }

}

Answer 1

问题出在这里:

    while (!(sequence1.isEmpty()))
    {
        merged.addLast(sequence1.removeFirst());
    }
    while (!(sequence1.isEmpty()))
    {
        merged.addLast(sequence2.removeFirst());
    }

在你的合并函数中。两个循环都会检查 sequence1 是否为空。将循环条件中的第二个 sequence1 替换为 sequence2 ，一切都会好起来的。