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

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

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

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

В терминах интерфейса List операцию можно реализовать следующим образом:

<T> List<T> merge(List<T> first, List<T> second, List<T> merged) {
  if (first.isEmpty())
    merged.adAll(second);
  else if (second.isEmpty())
    merged.adAll(first);
  else {
    Iterator<T> firstIter = first.iterator();
    Iterator<T> 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());
    }
  }
}

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

Еще пара примечаний:

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

Прежде всего, вы НЕ должны использовать индексы при работе со связанными списками. Делайте это так:

while (i < in.size/2){
  listOne.addLast( in.remove(in.first()) );
  i++
}
while(!in.isEmptly){
  listTwo.addLast( in.remove(in.first()) );
}

И для объединения

merge(a, b, out){
  while(!a.empty && !b.empty){
    if(a.first() >= b.first())
      out.addLast( a.remove(a.first()) );
    else
     out.addLast( b.remove(b.first()) );

  //remember to take care of the remaining elements 
  while(!a.empty)
    out.addLast( a.remove(a.first()) );
  while(!b.empty)
    out.addLast( b.remove(b.first()) );
}

Таким образом, это все равно будет O(n log n)

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

Дополнение

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

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

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 (i.e.
 * LinkedList), but assumes that {@code size()} and {@code get(0)}
 * are both constant-time.
 *
 * @author jasonmp85
 * @see <a href="http://en.wikipedia.org/wiki/Merge_sort">Merge sort</a>
 */
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<Long> list = new LinkedList<Long>();

        for(int i = 0; i < 10; i++) {
            list.add((long)(Math.random() * 100));
        }

        System.out.println("ORIGINAL LIST\n" + 
                           "=================\n" +
                           list + "\n");

        List<Long> 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 <T extends Comparable<T>> List<T> sort(List<T> list) {
        depth++;
        String tabs = getTabs();

        System.out.println(tabs + "Sorting: " + list);

        if(list.size() <= 1) {
            depth--;
            return list;
        }

        List<T> left   = new LinkedList<T>();
        List<T> right  = new LinkedList<T>();
        List<T> result = new LinkedList<T>();

        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 <T extends Comparable<T>> List<T> merge(List<T> left,
                                                           List<T> right) {
        String tabs = getTabs();
        System.out.println(tabs + "Merging: " + left + " & " + right);

        List<T> result = new LinkedList<T>();
        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. Marvel
5. При желании запустите javadoc -private MergeSort.java для создания документации. Откройте созданный им файл index.html.