排序双向链表与合并排序 [英] sorting a doubly linked list with merge sort
本文介绍了排序双向链表与合并排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
喜 我发现这个code在互联网上，这是对数组，我想改变它的双向链表（而不是指数，我们应该使用指针）请你帮我，我怎么能更改合并方法（我有我自己改变的排序方法）也是这不是我家的工作，我喜欢和链表的工作！
公共类归并{
私人DoublyLinkedList LocalDoublyLinkedList;
公共归并（DoublyLinkedList名单）{
LocalDoublyLinkedList =清单;
}
公共无效的sort（）{
如果（LocalDoublyLinkedList.size（）＆其中; = 1）{
返回;
}
DoublyLinkedList那么listOne =新DoublyLinkedList（）;
DoublyLinkedList listTwo =新DoublyLinkedList（）;
为（中间体X = 0，X≤（LocalDoublyLinkedList.size（）/ 2）; X ++）{
listOne.add（X，LocalDoublyLinkedList.getValue（X））;
}
为（中间体X =（LocalDoublyLinkedList.size（）/ 2）+ 1; X - 其中; LocalDoublyLinkedList.size`（）; X ++）{`
listTwo.add（X，LocalDoublyLinkedList.getValue（X））;
}
//再次分裂的DoublyLinkedList
归并SORT1 =新归并（那么listOne）;
归并SORT2 =新归并（listTwo）;
sort1.sort（）;
sort2.sort（）;
合并（那么listOne，listTwo）;
}
私人无效合并（DoublyLinkedList一个，DoublyLinkedList B）{
INT X = 0;
INT Y = 0;
INT Z = 0;
而（X＆LT; first.length和放大器;＆安培; Y＆LT; second.length）{
如果（第[X]＆lt;第[Y]）{
一[Z] =第[X]
X ++;
} 其他 {
一[Z] =第二[Y]
ÿ++;
}
ž++;
}
//剩下的元素复制到的[]尾;
的for（int i = X; I＆LT; first.length;我++）{
一[Z] =第[I]
ž++;
}
对于（INT I = Y; I＆LT; second.length;我++）{
一[Z] =第二[I]
ž++;
}
}
}
解决方案
合并排序需要拆分列表经常。是不是迭代的一个链表pretty的中间许多最昂贵的操作，您可以对其执行（当然，短期整理呢）？我能看到合并步骤的工作pretty的好（你向前遍历了两个链接列表），但我不知道这是执行不值得麻烦的的 O（1）的拆分操作。
跟进
至于向我指出，在 O（N）的分割操作并没有真正在增加太多的复杂性，当你已经在做的 O（N）的东西合并阶段。尽管如此，你还是会碰到麻烦做迭代像你这样做（不使用迭代而是使用 GET 在列表不佳的随机访问特性）。
我很无聊在调试一些其他的问题，所以给你写了什么，我认为是一个体面的Java实现了这个算法。我跟着维基百科的伪code逐字记录和洒在一些仿制药和打印报表。如果您有任何问题或疑虑，只问。
进口的java.util.List;
进口java.util.LinkedList中;
/ **
*这个类实现了归并操作，尽量保持
*尽可能接近到对所描述的实施
*维基百科页面的算法。它的目的是工作良好
*即使是与非恒定的随机访问性能列表（即
*链表），但假设{@ code尺寸（）}和{@ code GET（0）}
*都是固定时间。
*
* @author jasonmp85
* @see＆LT; A HREF =http://en.wikipedia.org/wiki/Merge_sort＆GT;合并排序＆LT; / A＆GT;
* /
公共类归并{
/ **
*保持跟踪调用深度的印刷目的
* /
私有静态诠释深度= 0;
/ **
*创建的10个随机多头清单，并对其排序，
*使用{@link #sort（名单）}。
*
*打印出原始列表和的结果。
*
* /
公共静态无效的主要（字串[] args）{
链表＆LT;龙＆GT;名单=新的LinkedList＆LT;龙＆GT;（）;
的for（int i = 0;我小于10;我++）{
list.add（（长）（的Math.random（）* 100））;
}
的System.out.println（原单\ N+
================= \ N+
清单+\ N）;
名单＆LT;龙＆GT;排序=排序（名单）;
的System.out.println（\ nFINAL LIST \ N+
================= \ N+
排序+\ N）;
}
/ **
*执行合并排序的{@ code}列表中的项目，并返回一个
*新的列表。
*
*不作任何调用{@ code List.get（）}或{@ code List.set（）}。
*
*打印出的步骤，缩进基于呼叫深度。
*
*参数列出列表进行排序
* /
公共静态＆LT;吨延伸可比＆LT; T＆GT;＆GT;名单＆LT; T＆GT;排序（表＆LT; T＆GT;列表）{
深度++;
串标签= getTabs（）;
的System.out.println（标签+排序+清单）;
如果（则为list.size（）＆其中; = 1）{
深度 - ;
返回列表;
}
名单＆LT; T＆GT;左=新的LinkedList＆LT; T＆GT;（）;
名单＆LT; T＆GT;右=新的LinkedList＆LT; T＆GT;（）;
名单＆LT; T＆GT;结果=新的LinkedList＆LT; T＆GT;（）;
INT中间=则为list.size（）/ 2;
INT加入= 0;
对于（T项目：名单）{
如果（加入++＆LT;中）
left.add（项目）;
其他
right.add（项目）;
}
左=排序（左）;
右=排序（右）;
结果=合并（左，右）;
的System.out.println（标签+排序为：+结果）;
深度 - ;
返回结果;
}
/ **
*执行的哦，所以，重要的合并步骤。合并{@ code左}
*和{@ code右键}进入一个新的列表，这是返回。
*
*参数留在左边的列表
*参数权名单
返回：两个列表项的排序版本
* /
私有静态＆LT;吨延伸可比＆LT; T＆GT;＆GT;名单＆LT; T＆GT;合并（名单＆LT; T＆GT;左，
名单＆LT; T＆GT;对） {
串标签= getTabs（）;
的System.out.println（标签+合并+左+＆放大器;+右）;
名单＆LT; T＆GT;结果=新的LinkedList＆LT; T＆GT;（）;
而（left.size（）大于0＆安培;＆安培; right.size（）大于0）{
如果（left.get（0）.compareTo（right.get（0））℃的）
result.add（left.remove（0））;
其他
result.add（right.remove（0））;
}
如果（left.size（）大于0）
result.addAll（左）;
其他
result.addAll（右）;
返回结果;
}
/ **
*返回一个数字，基于当前调用深度标签。
*
* /
私有静态字符串getTabs（）{
StringBuffer的SB =新的StringBuffer（）;
的for（int i = 0; I＆LT;深度;我++）
sb.append（'\ t'）;
返回sb.toString（）;
}
}
要运行
- 保存code到指定的文件 MergeSort.java
- 运行
javac的MergeSort.java - 运行
的java归并 - 奇迹
- （可选）执行
的javadoc - 私人MergeSort.java以创建文档。打开它创建index.html文件。
Hi I have found this code in the internet and it was for arrays ,I want to change it for doubly linked list(instead of index we should use pointer) would you please help me that how can i change merge method(I have changed sort method by myself) also this is not my home work ,I love working with linked list!!
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++;
}
}
}
解决方案
Merge sort requires splitting the list quite often. Isn't iterating to the middle of a LinkedList pretty much the most expensive operation you can perform on it (well, short of sorting it)? I could see the merge step working pretty well (you're iterating forwards over two linked lists), but I'm not sure that this implementation is worth the trouble without an O(1) split operation.
Followup
As pointed out to me, the O(n) split operation doesn't really add much to complexity when you're already doing O(n) things during the merge phase. Nevertheless, you're still going to run into trouble doing iteration like you're doing (not using an Iterator but instead using get on a List with poor random-access characteristics).
I was bored while debugging some other issue so wrote you what I consider to be a decent Java implementation of this algorithm. I followed Wikipedia's pseudocode verbatim and sprinkled in some generics and print statements. If you have any questions or concerns, just ask.
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();
}
}
To Run
- Save the code to a file named MergeSort.java
- Run
javac MergeSort.java - Run
java MergeSort - Marvel
- Optionally, run
javadoc -private MergeSort.javato create the documentation. Open the index.html file it creates.
这篇关于排序双向链表与合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
