Java comment trier une Liste chaînée?
je dois trier une liste Par Ordre alphabétique. J'ai une liste de noms de passagers et j'ai besoin que le nom des passagers soit classé par ordre alphabétique. Comment pourrait-on le faire? Quelqu'un a des références ou des vidéos?
9 réponses
vous pouvez utiliser Collections#sort pour trier les choses par ordre alphabétique.
pour trier les chaînes par ordre alphabétique, vous devrez utiliser un Collator , comme:
LinkedList<String> list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Collator.getInstance().compare(o1, o2);
}
});
parce que si vous appelez Collections.sort(list) vous aurez des problèmes avec les chaînes qui contiennent des caractères majuscules.
par exemple dans le code que j'ai collé, après le tri la liste sera: [aAb, abc, Bcd] mais si vous appelez simplement Collections.sort(list); vous obtiendrez: [Bcd, aAb, abc]
Note : Lorsqu'on utilise un Collator vous pouvez spécifier la locale Collator.getInstance(Locale.ENGLISH) c'est habituellement assez pratique.
dans java8 vous n'avez plus besoin d'utiliser les Collections.la méthode sort comme LinkedList hérite de la méthode sort de java.util.List, donc adapter la réponse de Fido à Java8:
LinkedList<String>list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");
list.sort( new Comparator<String>(){
@Override
public int compare(String o1,String o2){
return Collator.getInstance().compare(o1,o2);
}
});
, les Références:
http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
http://docs.oracle.com/javase/7/docs/api/java/util/List.html
Voici l'exemple pour trier la liste liée implémentée en java sans utiliser de bibliothèques java standard.
package SelFrDemo;
class NodeeSort {
Object value;
NodeeSort next;
NodeeSort(Object val) {
value = val;
next = null;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public NodeeSort getNext() {
return next;
}
public void setNext(NodeeSort next) {
this.next = next;
}
}
public class SortLinkList {
NodeeSort head;
int size = 0;
NodeeSort add(Object val) {
// TODO Auto-generated method stub
if (head == null) {
NodeeSort nodee = new NodeeSort(val);
head = nodee;
size++;
return head;
}
NodeeSort temp = head;
while (temp.next != null) {
temp = temp.next;
}
NodeeSort newNode = new NodeeSort(val);
temp.setNext(newNode);
newNode.setNext(null);
size++;
return head;
}
NodeeSort sort(NodeeSort nodeSort) {
for (int i = size - 1; i >= 1; i--) {
NodeeSort finalval = nodeSort;
NodeeSort tempNode = nodeSort;
for (int j = 0; j < i; j++) {
int val1 = (int) nodeSort.value;
NodeeSort nextnode = nodeSort.next;
int val2 = (int) nextnode.value;
if (val1 > val2) {
if (nodeSort.next.next != null) {
NodeeSort CurrentNext = nodeSort.next.next;
nextnode.next = nodeSort;
nextnode.next.next = CurrentNext;
if (j == 0) {
finalval = nextnode;
} else
nodeSort = nextnode;
for (int l = 1; l < j; l++) {
tempNode = tempNode.next;
}
if (j != 0) {
tempNode.next = nextnode;
nodeSort = tempNode;
}
} else if (nodeSort.next.next == null) {
nextnode.next = nodeSort;
nextnode.next.next = null;
for (int l = 1; l < j; l++) {
tempNode = tempNode.next;
}
tempNode.next = nextnode;
nextnode = tempNode;
nodeSort = tempNode;
}
} else
nodeSort = tempNode;
nodeSort = finalval;
tempNode = nodeSort;
for (int k = 0; k <= j && j < i - 1; k++) {
nodeSort = nodeSort.next;
}
}
}
return nodeSort;
}
public static void main(String[] args) {
SortLinkList objsort = new SortLinkList();
NodeeSort nl1 = objsort.add(9);
NodeeSort nl2 = objsort.add(71);
NodeeSort nl3 = objsort.add(6);
NodeeSort nl4 = objsort.add(81);
NodeeSort nl5 = objsort.add(2);
NodeeSort NodeSort = nl5;
NodeeSort finalsort = objsort.sort(NodeSort);
while (finalsort != null) {
System.out.println(finalsort.getValue());
finalsort = finalsort.getNext();
}
}
}
solution élégante depuis JAVA 8:
LinkedList<String>list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");
list.sort(String::compareToIgnoreCase);
une autre option serait d'utiliser les expressions lambda:
list.sort((o1, o2) -> o1.compareToIgnoreCase(o2));
Node mergeSort(Node head) {
if(head == null || head.next == null) {
return head;
}
Node middle = middleElement(head);
Node nextofMiddle = middle.next;
middle.next = null;
Node left = mergeSort(head);
Node right = mergeSort(nextofMiddle);
Node sortdList = merge(left, right);
return sortdList;
}
Node merge(Node left, Node right) {
if(left == null) {
return right;
}
if(right == null) {
return left;
}
Node temp = null;
if(left.data < right.data) {
temp = left;
temp.next = merge(left.next, right);
} else {
temp = right;
temp.next = merge(left, right.next);
}
return temp;
}
Node middleElement(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
Je ne le ferais pas. J'utiliserais un ArrayList ou une collection triée avec un comparateur. Le tri D'une liste de liens est la procédure la plus inefficace à laquelle je puisse penser.
si vous voulez savoir comment trier une liste liée sans utiliser les bibliothèques Java standard, je vous suggérerais d'examiner vous-même des algorithmes différents. Exemples ici montrent comment mettre en œuvre un tri d'insertion, un autre poteau de débordement montre un tri de fusion , et ehow donne même quelques exemples sur la façon de créer une fonction de comparaison personnalisée dans le cas où vous voulez personnaliser davantage votre Tri.
vous pouvez le faire par Java 8 lambda expression:
LinkedList<String> list=new LinkedList<String>();
list.add("bgh");
list.add("asd");
list.add("new");
//lambda expression
list.sort((a,b)->a.compareTo(b));