Как Java Collections.sort перезаписывает список для сортировки

Question

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

Вызывающий код выглядит следующим образом:

List<Integer> l = new LinkedList<Integer>();
l.add(new Integer(10));
l.add(new Integer(28));
l.add(new Integer(4));
l.add(new Integer(35));
l.add(new Integer(9));

ArraySort.sort(l);
System.out.println(l);

Collections.sort(l);
System.out.println(l);

Позже я добавлю код для нашей сортировки, но вопрос в следующем: почему Collections.sort перезаписывает список новым отсортированным списком?а у нас нет?

Метод sort работает нормально, но просто не обновляет значения списка l в вызывающем классе.Мне просто любопытно, как Collections делает это, решение было бы просто вернуть List из ArraySort.sort и сделать l = ArraySort.sort, но это выглядит не так хорошо!

Вот код для фактической сортировки:

public static void sort(List l) {
    mergeSort(l);
}

private static List mergeSort(List l) {
    if (l.size() <= 1) {
        return l;
    }
    List left = new LinkedList();
    List right = new LinkedList();
    int middle = l.size() / 2;
    for (int i = 0; i < middle; i++) {
        left.add(l.get(i));
    }
    for (int i = middle; i < l.size(); i++) {
        right.add(l.get(i));
    }

    left = mergeSort(left);
    right = mergeSort(right);

    l = merge(left, right);
    return l;
}

private static List merge(List left, List right) {
    List result = new LinkedList();
    while (left.size() > 0 || right.size() > 0) {
        if (left.size() > 0 && right.size() > 0) {
            if ((int) left.get(0) <= (int) right.get(0)) {
                result.add(left.get(0));
                left.remove(0);
            } else {
                result.add(right.get(0));
                right.remove(0);
            }
        } else if (left.size() > 0) {
            result.add(left.get(0));
            left.remove(0);
        } else if (right.size() > 0) {
            result.add(right.get(0));
            right.remove(0);
        }
    }
    return result;
}

Надеюсь, что кто-то может прояснить это для меня.

Answer 1

Вам не нужно возвращать объект List, но это не делает его неправильным.

Обратите внимание, что вы присваиваете новый список аргументу списка

l = merge(left, right);

Java передается по значению, а не по ссылке, следовательно, это не оказывает никакого влияния, когда вы возвращаетесь из своего метода.Вы должны фактически изменить объект списка, переданный методу, а не назначать ему новое значение.

---

Рассматривали ли вы для сравнения реализацию в Java?

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Collections.java#Collections.sort%28java.util.List%29

Answer 2

Идея была бы изменить это:

l = merge(left, right);
return l;

в это (не уверен, если порядок сохранен - ​​я полагаю, что это так):

l.clear();
l.addAll(merge(left, right)); //no need to return the list, it is the same

Answer 3

Это не так, это только изменяет содержимое списка.

Из источника :

 public static <T extends Comparable<? super T>> void sort(List<T> list) {
     Object[] a = list.toArray();
     Arrays.sort(a);
     ListIterator<T> i = list.listIterator();
     for (int j=0; j<a.length; j++) {
         i.next();
         i.set((T)a[j]);
     }
 }