tri d'une liste doublement chaînée avec fusion de tri
J'ai trouvé ce code sur internet et c'était pour les tableaux ,je veux la changer pour une liste doublement chaînée(au lieu de l'index qui doit nous servir de pointeur), pourriez-vous svp m'aider à comment puis-je changer de méthode de fusion(j'ai changé de méthode de tri par moi-même), aussi ce n'est pas mon travail à la maison ,j'aime travailler avec une liste chaînée!!
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++;
}
}
}
OriginalL'auteur user329820 | 2010-05-30
Vous devez vous connecter pour publier un commentaire.
De fusion de tri nécessite le fractionnement de la liste assez souvent. N'est-ce pas de l'itération au milieu d'une LinkedList assez bien le plus cher de l'opération que vous pouvez effectuer sur elle (ainsi, à court de tri)? J'ai pu voir l'étape de fusion et publipostage de travail assez bien (vous êtes une itération vers le haut sur les deux listes chaînées), mais je ne suis pas sûr que cette mise en œuvre est en vaut la peine, sans O(1) opération de scission.
De suivi
Comme me l'a fait remarquer, le O(n) opération de séparation n'est pas vraiment ajouter beaucoup à la complexité lorsque vous êtes déjà en train de le O(n) choses au cours de la fusion de la phase. Néanmoins, vous êtes toujours va avoir des ennuis de faire itération comme vous êtes en train de faire (pas à l'aide d'un
Iterator
mais au lieu d'utiliserget
sur unList
avec les pauvres d'accès aléatoire caractéristiques).Je me suis ennuyé pendant le débogage d'un autre problème, donc il vous a écrit ce que je considère être un décent Java mise en œuvre de cet algorithme. J'ai suivi la page Wikipedia de pseudo-mot à mot et saupoudré dans certains médicaments génériques et des instructions d'impression. Si vous avez des questions ou des préoccupations, il suffit de demander.
Pour Exécuter
MergeSort.java
javac MergeSort.java
java MergeSort
javadoc -private MergeSort.java
pour créer de la documentation. Ouvrez le index.html fichier qu'il crée.OriginalL'auteur jasonmp85
Cela dépend de ce que
DoublyLinkedList
est - est-ce un béton de type défini par l'utilisateur, ou tout simplement un nom d'alias pour une liste liée de type?Dans le premier cas, vous devriez avoir indexé méthodes get/set et/ou un itérateur qui y sont définis, ce qui rend la tâche simple.
Dans ce dernier cas, pourquoi ne pas utiliser la norme
java.util.LinkedList
?En termes de
List
interface, l'opération peut être mis en œuvre comme ceci:Cette mise en œuvre est un peu plus fastidieux qu'avec les tableaux, surtout depuis les itérateurs sont "consommés" par les
next
opération, et l'on doit donc tenir compte de l'élément courant dans chaque liste. Avecget
, le code serait plus simple, assez similaire à la solution de matrice, cependant, il serait beaucoup plus lent pour les grandes listes, comme @sepp2k souligné.Un couple plus de notes:
localDoublyLinkedList
OriginalL'auteur Péter Török
Je suis tombé sur ce problème hier. Voici quelques pensées.
Tri d'une
DoublyLinkedList
est différente de tri d'unArray
que vous ne peut pas faire l'index de références à n'importe quel élément dans la Liste. Au lieu de cela, vous devez vous rappeler les éléments au cours de chaque étape récursive, puis de les transmettre à la fonction de fusion. Pour chaque étape de la récursion vous avez seulement besoin de se rappeler le premier élément de chaque liste de moitié. Si vous ne vous souvenez pas de ces éléments, vous serez rapidement à la fin avec l'index, mais cela conduit au problème que dans votremerge
-fonction, vous devez parcourir la liste entière avecfor
-boucles de trouver les éléments à fusionner. Qui à son tour signifie que vous obtenez une complexité deO(n^2)
.Un autre point important est l'étape de recursing dans la liste et diviser la liste en deux moitiés. Vous pouvez faire cette étape dans la partie récursive en utilisant
for
-boucles. Contrairement à lamerge
-partie à cette étape lefor
-boucle de céder le passage à une complexité de laO(log(n) * n/2)
et c'est encore au-dessous de l'ensemble de laO(n*log(n))
complexité. Voici pourquoi:Vous avez toujours besoin de trouver le premier élément de chaque moitié de la liste.
Dans la première étape de la récursion vous avez besoin pour passer le
first
élément et l'élément à la positionn/2
. Cela prendn/2
étapes à trouver.Dans chaque étape suivante, vous devez trouver le moyen de l'élément pour chacune des deux moitiés de la liste qui nous donne
n/4
pour trouver l'élément dans la première moitié etn/4
dans l'autre moitié. Au total, c'estn/2
.Dans chaque récursive étape le montant de la liste de pièces de double et de la longueur est divisée par deux:
4 * n/8
dans le 3ème profondeur de récursion8 * n/16
dans le 4ème profondeur de récursion, et ainsi de suite...La profondeur de récursivité est
log(n)
et, à chaque étape, nous effectuonsn/2
étapes. Cela correspond àO(log(n)*n/2)
Enfin, voici un peu de code:
mergeSort:
et de fusion:
La quantité de mémoire maximale utilisée est également assez faible (pas y compris la liste elle-même). Corrigez-moi si je me trompe, mais il doit être inférieure à 400 octets (32 bits). Il serait de 12 octets par appel sur mergeSort fois la profondeur de récursion de log(n), plus de 20 octets pour les variables de fusion ainsi: 12*log(n)+20 octets.
P. S. du Code testé sur 1 millions d'articles (prend 1200ms). Aussi
DoublyLinkedList
est un conteneur qui stocke la premièreListElement
de la liste.Mise à jour:
J'ai répondu à une question similaire à propos de Quicksort en utilisant les mêmes structures de données, toutefois, par rapport à ce Mergesort mise en œuvre, il fonctionne beaucoup plus lentement. Voici quelques mises à jour les horaires pour référence:
Mergesort:
Quicksort:
Noter les horaires sont spécifiques à mon matériel et vous pourriez obtenir des résultats différents.
OriginalL'auteur lanoxx
Tout d'abord, vous ne devez PAS utiliser les index lorsque vous traitez avec les listes chaînées. De faire comme ceci:
Et pour la fusion des
De cette façon, il sera toujours en O(n log n)
OriginalL'auteur gwohpq9
Une autre idée est de créer un tableau avec tous les éléments de la liste, trier le tableau puis insérer les éléments de la liste.
Pro: très simple à mettre en œuvre, plus rapidement si des problèmes de mise en œuvre de la liste mergesort (peut-être même plus vite que les bonnes implémentations)
Contra: utilise un peu plus d'espace (O(n))
OriginalL'auteur George