слияние списка сортировки java

Question

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

public class MergeSort { 
    public static List<Integer> Sort(List<Integer> list) { 
     if (list.size() <= 1) { 
      return list; 
     } 
     List<Integer> aList = new ArrayList<Integer>(); 
     aList = list.subList(0, list.size()/2); 

     List<Integer> bList = new ArrayList<Integer>(); 
     bList = list.subList(list.size()/2, list.size()); 

     Sort(aList); 
     Sort(bList); 

     merge(aList, bList, list); 
     return list; 
    } 

    private static List<Integer> merge(List<Integer> alist, 
     List<Integer> blist, List<Integer> list) { 
     int alistIndex = 0, blistIndex = 0, listIndex = 0; 
     while (alistIndex < alist.size() && blistIndex < blist.size()) { 
      if (alist.get(alistIndex) < blist.get(blistIndex)) { 
       list.set(listIndex, alist.get(alistIndex)); 
       alistIndex++; 
      } else { 
       list.set(listIndex, blist.get(blistIndex)); 
       blistIndex++; 
      } 
      listIndex++; 
     } 
     List<Integer> rest; 
     if (alistIndex == alist.size()) { 
      rest = blist.subList(blistIndex, blist.size()); 
      for(int c = blistIndex; c < rest.size(); c++){ 
       list.set(listIndex, blist.get(c)); 
       listIndex++; 
      } 
     } else { 
      rest = alist.subList(alistIndex, alist.size()); 
      for(int c = alistIndex; c < rest.size(); c++){ 
       list.set(listIndex, alist.get(c)); 
       listIndex++; 
      } 
     } 
     return list; 
    } 
} 

Входной тест 5, 4, 3, 2, 1. Но выход 1, 1, 1, 1, 1. Таким образом, необходимо иметь некоторые неправильно с этим методом слияния

Answer 1

Быстрое исправление вашей проблемы замены:

List<Integer> aList = new ArrayList<Integer>(); 
aList = list.subList(0, list.size()/2); 

List<Integer> bList = new ArrayList<Integer>(); 
bList = list.subList(list.size()/2, list.size()); 

с:

List<Integer> aList = new ArrayList<Integer>(list.subList(0, list.size()/2)); 
List<Integer> bList = new ArrayList<Integer>(list.subList(list.size()/2, list.size())); 

создаются новые ArrayList сек для разделов, то немедленно изменить ссылка на представление вашего первоначального списка.

---

Разделение списка делается правильно, однако, потому что вы используете вид вместо мелких экземпляров, в процессе слияния изменяемого разделов.

Обычно, если вы делаете то, что мутирует первоначальный список, вы ничего не вернуть из этого метода, так что-то вроде:

public class MergeSort { 
    public static void sort(List<Integer> list) { 
    if (list.size() < 2) { 
     return; 
    } 
    int mid = list.size()/2; 
    List<Integer> left = new ArrayList<Integer>(list.subList(0, mid)); 
    List<Integer> right = new ArrayList<Integer>(mid, list.size())); 

    sort(left); 
    sort(right); 
    merge(left, right, list); 
    } 

    private static void merge(
     List<Integer> left, List<Integer> right, List<Integer> list) { 
    int leftIndex = 0; 
    int rightIndex = 0; 
    int listIndex = 0; 

    while (leftIndex < left.size() && rightIndex < right.size()) { 
     if (left.get(leftIndex) < right.get(rightIndex)) { 
     list.set(listIndex++, left.get(leftIndex++)); 
     } else { 
     list.set(listIndex++, right.get(rightIndex++)); 
     } 
    } 
    while (leftIndex < left.size()) { 
     list.set(listIndex++, left.get(leftIndex++)); 
    } 
    while (rightIndex < right.size()) { 
     list.set(listIndex++, right.get(rightIndex++)); 
    } 
    } 
} 

---

Альтернативой где первоначальный список не является мутантным может быть:

public class MergeSort { 
    public static List<Integer> sorted(List<Integer> list) { 
    if (list.size() < 2) { 
     return list; 
    } 
    int mid = list.size()/2; 
    return merged(
     sorted(list.subList(0, mid)), 
     sorted(list.subList(mid, list.size()))); 
    } 

    private static List<Integer> merged(List<Integer> left, List<Integer> right) { 
    int leftIndex = 0; 
    int rightIndex = 0; 
    List<Integer> merged = new ArrayList<Integer>(); 

    while (leftIndex < left.size() && rightIndex < right.size()) { 
     if (left.get(leftIndex) < right.get(rightIndex)) { 
     merged.add(left.get(leftIndex++)); 
     } else { 
     merged.add(right.get(rightIndex++)); 
     } 
    } 
    merged.addAll(left.subList(leftIndex, left.size())); 
    merged.addAll(right.subList(rightIndex, right.size())); 
    return merged; 
    } 
} 

Answer 2

Метод subList создает новый список из исходного, но все же содержит ссылку на исходные элементы, так что любое изменение, сделанное в первом, повлияет на второе и наоборот. В методе слияния вы переписываете свой первоначальный список и в то же время изменяете большие элементы в подсписке, которые не передают ваше условие if. Пожалуйста, обратитесь к для this post получения дополнительной информации по этому вопросу