0

マージソートを使用して文字列の文字を昇順にソートしようとしていますが、ソートするために文字を正確に比較する場所がわかりません。これはこれまでの私の方法です：

public static String mergeSort(String s)
    {
        String left = "",
               right = "";
        if(s.length() <= 1)
            return s;
        int middle = s.length()/2;
        for(int i = 0; i < middle; i++)
            left = left + s.charAt(i);
        for(int i = middle+1; i < s.length(); i++)
            right = right + s.charAt(i);
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

お役に立てば幸いです よろしくお願いします

4

4 に答える 4

1

まず、ウィキペディアの MergeSort に関するエントリを読むことをお勧めします。

コードに基づいて提案する 2 つのこと

  1. 2 つの文字の実際の比較はmergeSort()ではなく、 で行われmerge()ます。書き方については、ウィキペディアの疑似コードを参照してください。
  2. 一度に1 文字ずつ読み取るleftおよびString オブジェクトを作成することはお勧めしません。right使用する必要はありませんcharAt()。代わりに、String.substring()( http://docs.oracle.com/javase/7/docs/api/java/lang/String.html )を使用してください。

追加情報

これを使用して次のように設定leftしrightます。

String left = s.substring(0, middle);
String right = s.substring(middle);
于 2013-03-16T18:26:12.117 に答える
0

以下に示すように、入力文字列を文字配列に変換し、マージソートの計算を行うことができます。

import java.util.Queue;
import java.util.LinkedList;

public class MergeSort {

    public static void sort(char[] chars, int low, int right) {
        if (low < right) {
            int middle = (low + right) / 2;
            sort(chars, low, middle);
            sort(chars, middle + 1, right);
            merge(chars, low, middle, right);
        }
    }

    public static void merge(char[] chars, int low, int middle, int right) {
        Queue<Character> queue1 = new LinkedList<Character>();
        Queue<Character> queue2 = new LinkedList<Character>();

        for (int i = low; i <= middle; i++) {
            queue1.add(chars[i]);
        } 

        for (int i = middle + 1; i <= right; i++) {
            queue2.add(chars[i]);
        }

        int i = low;

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            if (queue1.peek() <= queue2.peek()) {
                chars[i++] = queue1.poll();
            } else {
                chars[i++] = queue2.poll();
            }
        }

        while (!queue1.isEmpty()) {
            chars[i++] = queue1.poll();
        }

        while (!queue2.isEmpty()) {
            chars[i++] = queue2.poll();
        }
    }

    public static void sort(char[] chars) {
        sort(chars, 0, chars.length - 1);
    }

    public static void sort(String string) {
        sort(string.toCharArray());
    }

    public static void main(String[] args) {
        String string = "sarathkumarsivan";
        char[] chars = string.toCharArray();

        MergeSort.sort(chars);

        for (int i = 0; i < chars.length; i++) {
            if (i > 0) { System.out.print(", "); }
            System.out.print(chars[i]);
        }
    }
}
于 2013-03-16T19:15:31.110 に答える
0

2 文字の減算を使用できます。したがって、2 つの文字aとband がある場合:

  • a - b = 0、文字は等しい
  • a - b > 0、aより大きい
  • a - b < 0、bより大きい

これはまさにCharacter.compareTo()メソッドが実装された方法です。

于 2013-03-16T18:24:19.740 に答える
0
  1. Java では不変であるStringため、計算では使用しないでください。String何千ものオブジェクトを作成することになり、実装が遅くなります。代わりに使用することをお勧めしchar[]ます。
  2. merge()サブルーチンで実際の比較を行います。たとえば、標準の演算子を使用して比較charするのと同じ方法で比較します。int>
于 2013-03-16T18:24:23.757 に答える