Общий Mergesort Работает на целых числах, но не заканчивается строками?

Question

По любой причине, несмотря на тот факт, что он полностью универсален и работает с целыми числами всякий раз, когда он тестируется со строками, он, похоже, пропускает последнюю итерацию слияния.Я искал свой код в течение пары часов и не могу понять, почему он не работает должным образом, поэтому любое понимание кого-либо было бы хорошо получено!

import java.util.Iterator;import java.util.LinkedList;

/ ** * * @author paul * / открытый класс MergeSort> {

LinkedList<T> theList;

MergeSort(LinkedList<T> toBeSorted) {
    theList = toBeSorted;
}

public LinkedList<T> sort() {
    return trueSort(theList);
}

private LinkedList<T> trueSort(LinkedList<T> sorting) {
    if (sorting.size() <= 1) {
        return sorting;
    }
    LinkedList<T> left, right, sorted;
    left = new LinkedList<T>();
    right = new LinkedList<T>();
    int middle = sorting.size() / 2;
    Iterator<T> sojourner = sorting.iterator();
    for (int i = 0; sojourner.hasNext(); i++) {
        if (i < middle) {
            left.add(sojourner.next());
        } else {
            right.add(sojourner.next());
        }
    }
    return trueMerge(trueSort(left),

trueSort (справа));}

private LinkedList<T> trueMerge(LinkedList<T> left,

LinkedList right) {LinkedList result = new LinkedList ();while (left.size ()> 0 || right.size ()> 0) {if (left.size ()> 0 && right.size ()> 0) {if (left.getFirst (). compareTo (right).getFirst ()) <0) {result.add (left.pop ());} else {result.add (right.pop ());}} else if (left.size ()> 0) {result.add (left.pop ());} else {result.add (right.pop ());}} вернуть результат;}}

Вот мой основной Java-файл

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

/**
*
* @author paul
*/
public class Main {

    public static Random Rand;

    public static int randomNumber(int min, int max) {
  return min + (int) (Rand.nextDouble() * ((max - min) +

1));}

    public static <T> String getString(LinkedList<T> linkInt) {
  String s = "";
  Iterator<T> interLink = linkInt.iterator();
  for (int i = 0; interLink.hasNext(); i++) {
    s = s + interLink.next().toString();
    if (interLink.hasNext()) {
    s = s + ", ";
    }
    if ((i + 1) % 10 == 0) {
    s = s + "\n";
    }
  }
  return s;
    }

    /**
  * @param args the command line arguments
  */
    public static void main(String[] args) {
  Rand = new Random();

  LinkedList<Integer> numbers = new LinkedList<Integer>();
  for(int i = 0; i< 100;i++){
    numbers.add(randomNumber(1,1000));
  }
  System.out.println(getString(numbers));
  MergeSort m = new MergeSort(numbers); //change this

позже будет чисто статическим числом = m.sort ();System.out.println (getString (numbers));

  LinkedList<String> words = new LinkedList<String>();
  words.add("Hello");
  words.add("MY");
  words.add("name");
  words.add("Is");
  words.add("Barthoal");
  words.add("I");
  words.add("Enjoy");
  words.add("long");
  words.add("beach");
  words.add("walks");
  words.add("would");
  words.add("you");
  words.add("like");
  words.add("to");
  words.add("come");
  words.add("Join");
  words.add("me");
  words.add("in");
  words.add("my");
  words.add("StarDestroyer-MobileHome?

(TM) "); System.out.println (getString (words)); MergeSort mm = new MergeSort (words); words =mm.sort (); System.out.println (getString (words));}}

Это выводит:

304, 842, 342, 794, 574, 99, 250, 885, 408, 387, 899, 73, 391, 883, 771, 848, 968, 504, 129, 370, 994, 897, 649, 345, 983, 326, 688, 547, 541, 567777, 987, 201, 326, 298, 959, 166, 962, 864, 797, 512, 505, 609, 208, 21, 43, 458, 442, 138, 570, 455, 442, 516, 294, 406310, 215, 212, 397, 98, 938, 496, 263, 973, 571, 861, 687, 276, 927, 608, 421, 831, 820, 510, 68, 172, 504, 8, 976, 992, 68, 497, 33, 233, 607, 587, 611, 695, 834, 338, 448, 978, 359, 413, 1, 819, 18, 977, 693, 649

1, 8,18, 21, 33, 43, 68, 68, 73, 98, 99, 129, 138, 166, 172, 201, 208, 212, 215, 233, 250, 263, 276, 294, 298, 304, 310,326, 326, 338, 342, 345, 359, 370, 387, 391, 397, 406, 408, 413, 421, 442, 442, 448, 455, 458, 496, 497, 504, 504, 505, 510,512, 516, 541, 547, 567, 570, 571, 574, 587, 607, 608, 609, 611, 649, 649, 687, 688, 693, 695, 771, 777, 794, 797, 819, 820,831, 834, 842, 848, 861, 864, 883, 885, 897, 899, 927, 938, 959, 962, 968, 973, 976, 977, 978, 983, 987, 992, 994

Здравствуйте, МОЯ, зовут, Бартул, я, Наслаждаюсь, долго, пляж, прогулки, хотел бы, ты, как, прийти, Присоединиться, мне, в, мой, StarDestroyer-MobileHome?(TM)

Barthoal, Наслаждайся, Привет, Я, Есть, Присоединяйся, МОЙ, StarDestroyer-MobileHome?(ТМ), пляж, заходи, вроде бы, долго, я, мое, имя, на прогулку, ты ...

Как видите, числа полностью отсортированы.Кажется, что строки пропустили последнюю итерацию слияния.Так что именно пошло не так?

Answer 1

Сравнение строк чувствительно к регистру.То есть все строчные буквы будут размещены перед строчными.Ваш алгоритм сортировки слиянием должен позволять использовать собственный компаратор, который может быть String.CASE_INSENSITIVE_ORDER для вашего варианта использования.

Answer 2

Ваш код в порядке и он сортируется правильно. Вы должны понимать, что заглавные буквы отличаются от строчных. сравнивая «Мой» с «пляжем», вы получите, что «Мой» должен стоять перед «пляжем» (потому что заглавные буквы идут перед строчными).

Это причина того, что в вашем результате все буквы в верхнем регистре получают все слова, которые начинаются с заглавной буквы, ставятся в начале.

Возможно, вы захотите использовать метод compareToIgnoreCase() (определенный для строк), чтобы сравнить вашу строку, игнорируя регистр букв.

Смотрите подробности этого метода здесь: http://download.oracle.com/javase/1.5.0/docs/api/java/lang/String.html#compareToIgnoreCase(java.lang.String

(И, пожалуйста, переформатируйте ваш код)