Я нашел этот код в Интернете, и это было для массивов, я хочу изменить его для двунаправленного связанного списка (вместо индекса, мы должны использовать указатель), помогите мне, что, как может, я изменяю метод слияния (я изменил метод сортировки один), также это не моя домашняя работа, я люблю работать со связанным списком!!
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++;
}
}
}
Это зависит от того, что такое 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
Прежде всего, вы НЕ должны использовать индексы при работе со связанными списками. Делайте это так:
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();
}
}
javac MergeSort.java
java MergeSort
javadoc -private MergeSort.java
для создания документации. Откройте созданный им файл index.html.