使用合并排序对双向链表进行排序

我在互联网上找到了这个代码，它是针对数组的，我想把它更改为双链表（而不是索引我们应该使用指针）请你帮我，我怎样才能改变合并方法（我改变了排序方法）我自己）这也不是我的家庭工作，我喜欢使用链表！

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实现。 我按照维基百科的伪代码逐字记录，并在一些generics和打印语句中加入。 如果您有任何问题或疑虑，请询问。

 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文件。

Answer 2

这取决于DoublyLinkedList是什么 – 它是具体的用户定义类型，还是链接列表类型的别名？

在第一种情况下，您应该在其中定义索引的get / set方法和/或迭代器，这使得任务变得简单。

在后一种情况下，为什么不使用标准的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()); } } } 

这个实现比使用数组更加繁琐，主要是因为迭代器被next操作“消耗”，因此必须记住每个列表中的当前项。 使用get ，代码会更简单，与数组解决方案非常相似，但是对于大型列表来说会更慢，正如@ sepp2k指出的那样。

还有几点说明：

• Java的传统是使用小写变量名，因此使用localDoublyLinkedList
• Java没有指针，只有引用。

Answer 3

我昨天遇到了这个问题。 这是一些想法。

对DoublyLinkedList排序与排序Array不同，因为您无法对List中的任何任意项进行基于索引的引用。 相反，您需要在每个递归步骤中记住这些项目，然后将它们传递给合并函数。 对于每个递归步骤，您只需要记住每个列表的第一项。 如果您不记得这些项目，您将很快得到索引，但这会导致您在merge -function中需要使用for -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. 在每个后续递归步骤中，列表部分的数量加倍，长度除以2：

   • 第3递归深度为4 * n/8

   • 第4递归深度为8 * n/16 ，依此类推……

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 

使用的最大内存量也非常低（不包括列表本身）。 如果我错了，请纠正我，但它应该少于400字节（32位）。 在mergeSort上每次调用将是12字节，对于合并变量，log（n）的递归深度加上20字节，因此：12 * log（n）+20字节。

PS Code在100万件物品上测试（需要1200毫秒）。 DoublyLinkedList也是一个存储列表的第一个ListElement的容器。

更新：我已经使用相同的数据结构回答了关于Quicksort的类似问题，但是与此Mergesort实现相比，它运行得慢得多。 以下是一些更新的时间供参考：

归并：

 1.000.000 Items: 466ms 8.300.000 Items: 5144ms 

快速排序：

 1.000.000 Items: 696ms 8.300.000 Items: 8131ms 

请注意，时间特定于我的硬件，您可能会得到不同的结果。

Answer 4

首先，在处理链表时不得使用索引。 像这样做：

 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）

Answer 5

另一个想法是创建一个包含列表中所有元素的数组，对数组进行排序，然后再次将元素插入列表。

Pro：实现起来非常简单，如果列表mergesort的实现很差（也可能比良好的实现更快）

Contra：使用一些额外的空间（O（n））