После завершения метода MergeSort возвращается только 1 число - PullRequest
Новая
       13

После завершения метода MergeSort возвращается только 1 число

0 голосов
/ 17 апреля 2019

После завершения метода MergeSort он возвращает только несколько чисел.В последней рекурсии правый массив не имеет чисел.Есть некоторые "отладки", не обращайте внимания.Пытался что-то сделать со средней переменной.

Пример вывода с массивом из 50 элементов:

Исходный массив: 

914 75 5 811 775 500 611 991 524 306 208 673 427 938 214 789 493 390 
705 140 131 550 346 851 635 957 828 350 612 442 657 795 211 309 119 
368 473 884 364 851 195 276 891 247 462 123 111 975 384 970

Вывод: 

914 427 75

Вот код: 

public static ArrayList<Integer> MergeSort(ArrayList<Integer> str) {
    ArrayList<Integer> left = new ArrayList<>();
    ArrayList<Integer> right = new ArrayList<>();
    if (str.size() <= 1) {
        return str;
    }

    int middle = str.size() / 2;
    System.out.println("Mid: "+ middle);

    for (int i = 0; i < middle; i++) {
        left.add(str.get(i));
    }
    for (int i = middle; i < str.size() - middle; i++) {
        right.add(str.get(i));
    }
    System.out.println("Left start!");
    left = MergeSort(left);
    print(left);
    System.out.println("Left stop!");
    System.out.println("Right start!");
    right = MergeSort(right);
    print(right);
    System.out.println("Right stop!");

    return Merge(left, right);
}

public static ArrayList<Integer> Merge(ArrayList<Integer> left, ArrayList<Integer> right) {
    ArrayList<Integer> result = new ArrayList<>();

    while (right.size() > 0 && left.size() > 0) {
        if (right.get(0) <= left.get(0)) {
            result.add(left.get(0));
            left.remove(0);
        } else {
            result.add(right.get(0));
            right.remove(0);
        }
    }

    while (left.size() > 0) {
        result.add(left.get(0));
        left.remove(0);
    }
    while (right.size() > 0) {
        result.add(right.get(0));
        right.remove(0);
    }
    return result;
}

1 Ответ

1 голос
/ 17 апреля 2019 
for (int i = middle;i<str.size()-middle;i++) {
    right.add(str.get(i));
}

Должно быть 

for (int i = middle;i<str.size();i++) {
    right.add(str.get(i));
}

Фактически, List s имеют subList(), поэтому left и right могут быть созданы как 

List<Integer> left=str.subList(0,middle);
List<Integer> right=str.subList(middle,str.size());

(Хотя это немного нарушило бы цель практики - это цель, которую я предполагаю, поскольку List s также имеют свои sort() в конце концов)

...