Я столкнулся с этой проблемой вчера. Вот несколько мыслей.
Сортировка DoublyLinkedList отличается от сортировки Array тем, что вы не можете делать индексные ссылки на любой произвольный элемент в списке. Вместо этого вам нужно помнить элементы во время каждого рекурсивного шага, а затем передавать их функции слияния. Для каждого шага рекурсии вам нужно запомнить только первый элемент каждой половины списка. Если вы не помните эти элементы, вы быстро получите индексы, но это приведет вас к проблеме, заключающейся в том, что в вашей merge -функции вам нужно пройти весь список с помощью for -loops, чтобы найти элементы для слияния. Это, в свою очередь, означает, что вы получаете сложность O(n^2).
Другим важным моментом является повторение списка и разделение списка на две половины. Вы можете сделать этот шаг в рекурсивной части, используя for -loops. В отличие от части merge на этом шаге, циклы for приведут только к сложности O(log(n) * n/2), и это все еще ниже общей сложности O(n*log(n)). Вот почему:
Всегда нужно найти первый элемент каждой половины части списка.
На первом шаге рекурсии вам нужно передать элемент first и элемент в позиции n/2. Это займет n/2 шагов, чтобы найти.
На каждом следующем шаге вам нужно найти средний элемент для каждой из двух половин списка, что дает нам n/4 для поиска элемента в первой половине и n/4 в другой половине. Всего это n/2.
На каждом последующем рекурсивном шаге количество частей списка удваивается, а длины делятся на два:
Глубина рекурсии составляет 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 это будет 12 байт на вызов, умноженный на глубину рекурсии log (n) плюс 20 байт для переменных слияния, таким образом: 12 * log (n) +20 байт.
P.S. Код проверен на 1 млн. Элементов (занимает 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
Обратите внимание, что время зависит от моего оборудования, и вы можете получить другие результаты.