сортировка двусвязного списка с сортировкой слияния

Сортировка сортировки требует довольно часто разбивать список. Не повторяется ли в середине LinkedList довольно дорогостоящая операция, которую вы можете выполнить на нем (ну, не сортируя ее)? Я мог видеть, что шаг слияния работает очень хорошо (вы повторяете переходы по двум связанным спискам), но я не уверен, что эта реализация стоит проблем без операции O (1) split.

Следовать за

Как указывалось выше, операция разделения O (n) на самом деле не усложняет задачу, когда вы уже выполняете O (n) вещи во время фазы слияния. Тем не менее, вы по-прежнему сталкиваетесь с трудностями при выполнении итераций, как вы делаете (не используя Iterator а вместо этого используйте get в List со слабыми характеристиками произвольного доступа).

Мне было скучно при отладке какой-то другой проблемы, поэтому написал вам то, что я считаю достойной реализацией Java этого алгоритма. Я следовал за псевдокодом Wikipedia дословно и посыпался некоторыми родовыми и печатными заявлениями. Если у вас есть какие-либо вопросы или проблемы, просто спросите.

 import java.util.List; import java.util.LinkedList; /** * This class implements the mergesort operation, trying to stay * as close as possible to the implementation described on the * Wikipedia page for the algorithm. It is meant to work well * even on lists with non-constant random-access performance (ie * LinkedList), but assumes that {@code size()} and {@code get(0)} * are both constant-time. * * @author jasonmp85 * @see Merge sort */ public class MergeSort { /** * Keeps track of the call depth for printing purposes */ private static int depth = 0; /** * Creates a list of 10 random Longs and sorts it * using {@link #sort(List)}. * * Prints out the original list and the result. * */ public static void main(String[] args) { LinkedList list = new LinkedList(); for(int i = 0; i < 10; i++) { list.add((long)(Math.random() * 100)); } System.out.println("ORIGINAL LIST\n" + "=================\n" + list + "\n"); List sorted = sort(list); System.out.println("\nFINAL LIST\n" + "=================\n" + sorted + "\n"); } /** * Performs a merge sort of the items in {@code list} and returns a * new List. * * Does not make any calls to {@code List.get()} or {@code List.set()}. * * Prints out the steps, indented based on call depth. * * @param list the list to sort */ public static > List sort(List list) { depth++; String tabs = getTabs(); System.out.println(tabs + "Sorting: " + list); if(list.size() <= 1) { depth--; return list; } List left = new LinkedList(); List right = new LinkedList(); List result = new LinkedList(); int middle = list.size() / 2; int added = 0; for(T item: list) { if(added++ < middle) left.add(item); else right.add(item); } left = sort(left); right = sort(right); result = merge(left, right); System.out.println(tabs + "Sorted to: " + result); depth--; return result; } /** * Performs the oh-so-important merge step. Merges {@code left} * and {@code right} into a new list, which is returned. * * @param left the left list * @param right the right list * @return a sorted version of the two lists' items */ private static > List merge(List left, List right) { String tabs = getTabs(); System.out.println(tabs + "Merging: " + left + " & " + right); List result = new LinkedList(); while(left.size() > 0 && right.size() > 0) { if(left.get(0).compareTo(right.get(0)) < 0) result.add(left.remove(0)); else result.add(right.remove(0)); } if(left.size() > 0) result.addAll(left); else result.addAll(right); return result; } /** * Returns a number of tabs based on the current call depth. * */ private static String getTabs() { StringBuffer sb = new StringBuffer(""); for(int i = 0; i < depth; i++) sb.append('\t'); return sb.toString(); } } 

Бежать

1. Сохраните код в файл с именем MergeSort.java
2. Запустить javac MergeSort.java
3. Запустить java MergeSort
4. диво
5. При необходимости запустите javadoc -private MergeSort.java чтобы создать документацию. Откройте файл index.html, который он создает.

Это зависит от того, что DoublyLinkedList – это конкретный пользовательский тип или просто псевдоним для связанного типа списка?

В первом случае вы должны иметь индексированные методы get / set и / или iterator, определенные в нем, что делает задачу простой.

В последнем случае, почему бы не использовать стандартный java.util.LinkedList ?

С точки зрения интерфейса List эта операция может быть реализована следующим образом:

  List merge(List first, List second, List merged) { if (first.isEmpty()) merged.adAll(second); else if (second.isEmpty()) merged.adAll(first); else { Iterator firstIter = first.iterator(); Iterator secondIter = second.iterator(); T firstElem = firstIter.next(); T secondElem = secondIter.next(); do { if (firstElem < secondElem) { merged.add(firstElem); firstElem = firstIter.hasNext() ? firstIter.next() : null; } else { merged.add(secondElem); secondElem = secondIter.hasNext() ? secondIter.next() : null; } } while (firstIter.hasNext() && secondIter.hasNext()); //copy remaining elements to the tail of merged if (firstElem != null) merged.add(firstElem); if (secondElem != null) merged.add(secondElem); while (firstIter.hasNext()) { merged.add(firstIter.next()); } while (secondIter.hasNext()) { merged.add(secondIter.next()); } } } 

Эта реализация является немного более утомительной, чем при использовании массивов, главным образом, поскольку iteratorы «потребляются» next операцией, поэтому необходимо вести учет текущего элемента в каждом списке. С get , код будет проще, очень похож на решение массива, однако для больших списков он будет медленнее, как отметил @ sepp2k.

Еще несколько заметок:

• традиция Java - использовать имена переменных нижнего регистра, поэтому localDoublyLinkedList
• У Java нет указателей, только ссылок.

Вчера я столкнулся с этой проблемой. Вот несколько мыслей.

Сортировка DoublyLinkedList отличается от сортировки Array поскольку вы не можете ссылаться на индексные ссылки на любой произвольный элемент в списке. Вместо этого вам нужно запомнить элементы во время каждого рекурсивного шага, а затем передать их функции слияния. Для каждого этапа рекурсии вам нужно запомнить только первый элемент из каждой половины списка. Если вы не помните эти элементы, вы быстро получите индексы, но это приведет вас к проблеме, которая в вашей функции merge вам нужно пройти весь список с помощью -loops, чтобы найти элементы для слияния. Это, в свою очередь, означает, что вы получаете сложность O(n^2) .

Другим важным моментом является шаг рекурсии в список и разделение списка на две половины. Вы можете сделать этот шаг в рекурсивной части, используя for -loops. В отличие от merge на этом этапе for -loops приведет только к сложности O(log(n) * n/2) и это все еще ниже общей сложности O(n*log(n)) . Вот почему:

1. Вам всегда нужно найти первый элемент каждой половины части списка.

2. На первом этапе рекурсии вам необходимо передать first элемент и элемент в позиции n/2 . Для этого требуется n/2 шага.

3. На каждом следующем шаге вам нужно найти средний элемент для каждой из двух половин списка, который дает нам n/4 чтобы найти элемент в первой половине и n/4 в другой половине. В общей сложности это n/2 .

4. В каждом последующем рекурсивном шаге количество частей списка удваивается, а длины разделяются на два:

   • 4 * n/8 на 3-й глубине рекурсии

   • 8 * n/16 на 4-й глубине рекурсии и т. Д. …

5. Глубина рекурсии – log(n) и на каждом шаге мы выполняем n/2 шага. Это равно O(log(n)*n/2)

Наконец, вот какой код:

 public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) { in.first = mergesort(in.first, numOfElements); return in; } 

Сортировка слиянием:

 public ListElement mergesort(ListElement first, int length) { if(length > 1) { ListElement second = first; for(int i=0; i 

 public ListElement merge(ListElement first, ListElement second, int length) { ListElement result = first.prev; //remember the beginning of the new list will begin after its merged int right = 0; for(int i=0; i 

 1.000.000 Items: 466ms 8.300.000 Items: 5144ms 

 1.000.000 Items: 696ms 8.300.000 Items: 8131ms