java - 使用归并排序对双向链表进行排序

Question

我在互联网上找到了这段代码，它是用于数组的，我想将它更改为双向链表(而不是索引，我们应该使用指针)你能帮我看看我该如何更改合并方法(我有我自己更改了排序方法)这也不是我的家庭作业，我喜欢使用链表!!

public class MergeSort {

private DoublyLinkedList LocalDoublyLinkedList;

public MergeSort(DoublyLinkedList list) {
    LocalDoublyLinkedList = list;

}

public void sort() {

    if (LocalDoublyLinkedList.size() <= 1) {
        return;
    }
    DoublyLinkedList listOne = new DoublyLinkedList();
    DoublyLinkedList listTwo = new DoublyLinkedList();
    for (int x = 0; x < (LocalDoublyLinkedList.size() / 2); x++) {
        listOne.add(x, LocalDoublyLinkedList.getValue(x));
}
for (int x = (LocalDoublyLinkedList.size() / 2) + 1; x < LocalDoublyLinkedList.size`(); x++) {`
    listTwo.add(x, LocalDoublyLinkedList.getValue(x));
}
//Split the DoublyLinkedList again
    MergeSort sort1 = new MergeSort(listOne);
    MergeSort sort2 = new MergeSort(listTwo);
    sort1.sort();
    sort2.sort();

    merge(listOne, listTwo);
}

private void merge(DoublyLinkedList a, DoublyLinkedList b) {
    int x = 0;
    int y = 0;
    int z = 0;
    while (x < first.length && y < second.length) {
        if (first[x] < second[y]) {
            a[z] = first[x];
            x++;
        } else {
            a[z] = second[y];
            y++;
        }
        z++;
    }
//copy remaining elements to the tail of a[];
    for (int i = x; i < first.length; i++) {
        a[z] = first[i];
        z++;
    }
    for (int i = y; i < second.length; i++) {
        a[z] = second[i];
        z++;
    }
}
}

Answer 1

合并排序需要经常拆分列表。迭代到 LinkedList 的中间不是您可以对其执行的最昂贵的操作(好吧，除了排序之外)？我可以看到合并步骤工作得很好(您在两个链表上向前迭代)，但我不确定如果没有 O(1) 拆分操作，这个实现是否值得麻烦。

跟进

正如我所指出的，O(n) 拆分操作并没有真正增加复杂性，因为您已经在执行 O(n) 操作合并阶段。尽管如此，您仍然会像现在这样进行迭代时遇到麻烦(不是使用 Iterator 而是在 List 上使用 get > 具有较差的随机访问特性)。

我在调试其他一些问题时感到无聊，所以写给你我认为是该算法的一个不错的 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. 奇迹
5. 可选地，运行 javadoc -private MergeSort.java 来创建文档。打开它创建的 index.html 文件。