使用合并排序对双向链表进行排序
我在互联网上找到了这个代码，它是用于数组的，我想将它改为双向链表（而不是索引，我们应该使用指针），请你帮我一下，我该如何改变合并方法（我改变了排序方法由我自己）也这不是我的家庭工作，我喜欢与链接列表工作！
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++;
}
}
}
合并排序需要经常分割列表。 是不是迭代到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 LISTn" +
"=================n" +
list + "n");
List<Long> sorted = sort(list);
System.out.println("nFINAL LISTn" +
"=================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();
}
}
跑步
javac MergeSort.java java MergeSort javadoc -private MergeSort.java创建文档。 打开它创建的index.html文件。 它取决于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指出的那样。
还有一些注意事项：
localDoublyLinkedList 我昨天遇到了这个问题。 这里有一些想法。
对DoublyLinkedList进行排序与对Array排序不同，因为您无法对列表中的任何项目进行基于索引的引用。 相反，您需要记住每个递归步骤中的项目，然后将它们传递给合并函数。 对于每个递归步骤，您只需记住每个列表的第一项。 如果你不记得这些项目，你会很快结束了索引，但是这会导致你在你的问题merge -function你需要遍历与整个列表for -loops找到的项目进行合并。 这反过来意味着你得到O(n^2)的复杂性。
另一个重要的问题是递归到列表中并将列表分成两半。 您可以使用for -loops在递归部分中执行此步骤。 与此步骤中的merge part相反， for -loops只会产生O(log(n) * n/2)的复杂度，并且仍然低于整体O(n*log(n))复杂度。 这是为什么：
你总是需要找到列表部分的每一半的第一项。
在第一个递归步骤中，您需要传递第first项目和位置n/2处的项目。 这需要n/2步找到。
在接下来的每个步骤中，您需要为列表的两半中的每一半找到中间项目，它使我们有n/4找到第一个半部分中的项目和另一个半部分中的n/4 。 总共是n/2 。
在下面的每个递归步骤中，列表部分的数量都是两倍，长度除以二：
4 * n/8在第三递归深度
8 * n/16在第四递归深度中，依此类推...
递归深度是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<length/2; i++) {
second = second.next;
}
first = mergesort(first, length/2);
second = mergesort(second, (length+1)/2);
return merge(first, second, length);
} else {
return first;
}
}
并合并：
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<length; i++) {
if(first.getKey() <= second.getKey()) {
if(first.next == second) break; //end of first list and all items in the second list are already sorted, thus break
first = first.next;
} else {
if(right==(length+1)/2)
break; //we have merged all elements of the right list into the first list, thus break
if(second == result) result = result.prev; //special case that we are mergin the last element then the result element moves one step back.
ListElement nextSecond = second.next;
//remove second
second.prev.next = second.next;
second.next.prev = second.prev;
//insert second behind first.prev
second.prev = first.prev;
first.prev.next = second;
//insert second before first
second.next = first;
first.prev = second;
//move on to the next item in the second list
second = nextSecond;
right++;
}
}
return result.next; //return the beginning of the merged list
}
使用的最大内存量也很低（不包括列表本身）。 纠正我，如果我错了，但它应该小于400字节（在32位）。 mergeSort乘以log（n）的递归深度加上合并变量的20个字节：12 * log（n）+20字节。
在100万个物品上测试PS码（需要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
注意时间是特定于我的硬件，你可能会得到不同的结果。
链接地址: http://www.djcxy.com/p/31577.html