Java 按字母顺序对 ArrayList 进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2496841/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sort ArrayList alphabetically
提问by relyt
I'm trying to find all permutations of a string and sort them alphabetically.
我试图找到一个字符串的所有排列并按字母顺序排序。
This is what I have so far:
这是我到目前为止：
public class permutations {
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
System.out.print("Enter String: ");
String chars = s.next();
findPerms("", chars);
}
public static void findPerms(String mystr, String chars) {
List<String> permsList = new ArrayList<String>();
if (chars.length() <= 1)
permsList.add(mystr + chars);
//System.out.print(mystr + chars + " ");
else
for (int i = 0; i < chars.length(); i++) {
String newString = chars.substring(0, i) + chars.substring(i + 1);
findPerms(mystr + chars.charAt(i), newString);
}
Collections.sort(permsList);
for(int i=0; i<permsList.size(); i++) {
System.out.print(permsList.get(i) + " ");
}
}
}
IF I enter a string "toys" I get:
如果我输入一个字符串“toys”，我会得到：
toys tosy tyos tyso tsoy tsyo otys otsy oyts oyst osty osyt ytos ytso yots yost ysto ysot stoy styo soty soyt syto syot
玩具甲苯磺酰tyos tyso tsoy tsyo otys otsy oyts oyst osty osyt YTOS YouTube交响乐团yots约斯特ysto ysot斯托伊styo soty soyt SYTO syot
What am I doing wrong. How can I get them in alphabetical order? Thanks!
我究竟做错了什么。我怎样才能按字母顺序得到它们？谢谢！
采纳答案by Amir Afghani
You're calling your sort routine from within the recursive method that finds all permutations of your String, before it's been fully populated
在完全填充之前，您正在从查找字符串的所有排列的递归方法中调用排序例程
import java.util.*;
public class permutations {
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
System.out.print("Enter String: ");
String chars = s.next();
List<String> myList = new ArrayList<String>();
findPerms(myList, "", chars);
Collections.sort(myList);
for(int i=0; i<myList.size(); i++) {
System.out.print(myList.get(i) + " ");
}
}
public static void findPerms(List<String> permsList, String mystr, String chars) {
if (chars.length() <= 1)
permsList.add(mystr + chars);
else
for (int i = 0; i < chars.length(); i++) {
String newString = chars.substring(0, i) + chars.substring(i + 1);
findPerms(permsList, mystr + chars.charAt(i), newString);
}
}
}
回答by DVK
You need to sort the results of the call of findperms, not inside the recusive call.
您需要对 findperms 调用的结果进行排序，而不是在递归调用中。
回答by Gabriel ??erbák
回答by twodayslate
You could put all the permutations that you have already gotten and put them in a TreeSetor PriorityQueuewhich will put them in order. You would then have to put them back into your ArrayList.
你可以把你已经得到的所有排列放在 a TreeSetor 中PriorityQueue，这将使它们有序。然后，您必须将它们放回您的 ArrayList。
Or you could use a Collections Sortwhich sorts your ArrayList.
或者您可以使用集合排序来对您的 ArrayList 进行排序。
I recommend the last option. Here is an exampleif you do not understand it.
我推荐最后一个选项。如果你不明白，这里有一个例子。
回答by Brian
Some of the comments already point out that your recursive routine can't do a sort at the leaf nodes and expect to sort the whole list. You'd have to return the accumulated strings in a collection and then sort and print them once at the end.
一些评论已经指出您的递归例程不能在叶节点上进行排序并期望对整个列表进行排序。您必须返回集合中累积的字符串，然后在最后对它们进行排序和打印。
More importantly, there is a nice algorithm for permuting an array in lexical order. It's used by the next_permutation library function in C++ (which you can look up for explanations), but it's easy enough to translate to java. You extract a char[]array, maybe with getCharArray, sort it with Arrays.sortand run this until it returns false.
更重要的是，有一个很好的算法可以按词法顺序排列数组。它由 C++ 中的 next_permutation 库函数使用（您可以查找解释），但很容易转换为 java。你提取一个char[]数组，也许用getCharArray，对它进行排序Arrays.sort并运行它直到它返回false。
/** Helper function */
void reverse(char[] a, int f, int l)
{
while(l>f)
{
char tmp = a[l];
a[l] = a[f];
a[f] = tmp;
l--; f++;
}
}
/** actual permutation function */
boolean next_permutation(char[] a)
{
if(a.length < 2) return false;
for(int i = a.length-1; i-->0;)
if(a[i] < a[i+1])
{
int j=a.length-1;
while(!(a[i] < a[j]))
j--;
char tmp=a[i];
a[i]=a[j];
a[j]=tmp;
reverse(a, i+1, a.length-1);
return true;
}
reverse(a, 0, a.length-1);
return false;
}
Once you understand what it does, just run while(next_permutation(array)) {println(array);}and you're doing fine. Note that this is very bad for arrays over 13 or so elements.
一旦你理解了它的作用，只要运行while(next_permutation(array)) {println(array);}，你就会做得很好。请注意，这对于超过 13 个左右的元素的数组来说非常糟糕。
