在 Java 中反转字符串的最有效算法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2439141/
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
What is the most efficient algorithm for reversing a String in Java?
提问by Hultner
What is the most efficient way to reverse a string in Java? Should I use some sort of xor operator? The easy way would be to put all the chars in a stack and put them back into a string again but I doubt that's a very efficient way to do it.
在 Java 中反转字符串的最有效方法是什么？我应该使用某种异或运算符吗？简单的方法是将所有字符放在一个堆栈中，然后再次将它们放回一个字符串中，但我怀疑这是一种非常有效的方法。
And please do not tell me to use some built in function in Java. I am interested in learning how to do it not to use an efficient function but not knowing why it's efficient or how it's built up.
并且请不要告诉我使用 Java 中的一些内置函数。我有兴趣学习如何做到不使用有效的功能，但不知道它为什么有效或它是如何构建的。
采纳答案by Tom
You say you want to know the most efficient way and you don't want to know some standard built-in way of doing this. Then I say to you: RTSL (read the source, luke):
你说你想知道最有效的方法，但你不想知道一些标准的内置方法来做到这一点。然后我对你说：RTSL（阅读源码，luke）：
Check out the source code for AbstractStringBuilder#reverse, which gets called by StringBuilder#reverse. I bet it does some stuff that you would not have considered for a robust reverse operation.
查看AbstractStringBuilder#reverse的源代码，它被 StringBuilder#reverse 调用。我敢打赌，它会执行一些您在强大的反向操作中不会考虑的事情。
回答by Mark Byers
You said you don't want to do it the easy way, but for those Googling you should use StringBuilder.reverse:
你说你不想用简单的方法来做，但对于那些谷歌搜索你应该使用StringBuilder.reverse：
String reversed = new StringBuilder(s).reverse().toString();
If you need to implement it yourself, then iterate over the characters in reverse order and append them to a StringBuilder. You have to be careful if there are (or can be) surrogate pairs, as these should not be reversed. The method shown above does this for you automatically, which is why you should use it if possible.
如果您需要自己实现它，则以相反的顺序遍历字符并将它们附加到 StringBuilder。如果有（或可能有）代理对，您必须小心，因为这些不应该颠倒。上面显示的方法会自动为您执行此操作，这就是您应该尽可能使用它的原因。
回答by Simon Nickerson
The following does not deal with UTF-16 surrogate pairs.
以下不涉及 UTF-16 代理对。
public static String reverse(String orig)
{
char[] s = orig.toCharArray();
int n = s.length;
int halfLength = n / 2;
for (int i=0; i<halfLength; i++)
{
char temp = s[i];
s[i] = s[n-1-i];
s[n-1-i] = temp;
}
return new String(s);
}
回答by rsp
The fastest way would be to use the reverse()method on the StringBuilderor StringBufferclasses :)
最快的reverse()方法是在StringBuilderorStringBuffer类上使用该方法:)
If you want to implement it yourself, you can get the character array, allocate a second character array and move the chars, in pseudo code this would be like:
如果你想自己实现它，你可以获取字符数组，分配第二个字符数组并移动字符，伪代码如下：
String reverse(String str) {
char[] c = str.getCharArray
char[] r = new char[c.length];
int end = c.length - 1
for (int n = 0; n <= end; n++) {
r[n] = c[end - n];
}
return new String(r);
}
You could also run half the array length and swap the chars, the checks involved slow things down probably.
您也可以运行一半的数组长度并交换字符，所涉及的检查可能会减慢速度。
回答by NomeN
If you do not want to use any built in function, you need to go back with the string to its component parts: an array of chars.
如果不想使用任何内置函数，则需要将字符串返回到其组成部分：字符数组。
Now the question becomes what is the most efficient way to reverse an array? The answer to this question in practice also depends upon memory usage (for very large strings), but in theory efficiency in these cases is measured in array accesses.
现在问题变成了反转数组的最有效方法是什么？这个问题的答案在实践中也取决于内存使用情况（对于非常大的字符串），但理论上这些情况下的效率是通过数组访问来衡量的。
The easiest way is to create a new array and fill it with the values you encounter while reverse iterating over the original array, and returning the new array. (Although with a temporary variable you could also do this without an additional array, as in Simon Nickersons answer).
最简单的方法是创建一个新数组并用您遇到的值填充它，同时反向迭代原始数组，并返回新数组。（尽管使用临时变量，您也可以在没有额外数组的情况下执行此操作，如 Simon Nickersons 的回答）。
In this way you access each element exactly once for an array with n elements. Thus giving an efficiency of O(n).
通过这种方式，您可以为具有 n 个元素的数组访问每个元素一次。从而给出 O(n) 的效率。
回答by MAK
I'm not really sure by what you mean when you say you need an efficientalgorithm.
当你说你需要一个有效的算法时，我不太确定你的意思。
The ways of reversing a string that I can think of are (they are all already mentioned in other answers):
我能想到的反转字符串的方法是（它们都已经在其他答案中提到了）：
Use a stack (your idea).
Create a new reversed String by adding characters one by one in reverse order from the original String to a blank String/StringBuilder/char[].
Exchange all characters in the first half of the String with its corresponding position in the last half (i.e. the ith character gets swapped with the (length-i-1)th character).
使用堆栈（你的想法）。
通过从原始字符串以相反的顺序一个一个地添加字符到一个空白的 String/StringBuilder/char[] 来创建一个新的反向字符串。
将字符串前半部分的所有字符与其后半部分的相应位置交换（即第 i 个字符与第 (length-i-1) 个字符交换）。
The thing is that all of them have the same runtime complexity: O(N). Thus it cannot really be argued that any one is any significantly better than the others for very large values of N (i.e. very large strings).
问题是它们都具有相同的运行时复杂度：O(N)。因此，对于非常大的 N 值（即非常大的字符串），不能真正争论任何一个明显优于其他任何一个。
The third method does have one thing going for it, the other two require O(N) extra space (for the stack or the new String), while it can perform swaps in place. But Strings are immutable in Java so you need to perform swaps on a newly created StringBuilder/char[] anyway and thus end up needing O(N) extra space.
第三种方法确实有一件事要做，另外两种方法需要 O(N) 额外空间（用于堆栈或新字符串），同时它可以执行就地交换。但是字符串在 Java 中是不可变的，因此无论如何您都需要在新创建的 StringBuilder/char[] 上执行交换，因此最终需要 O(N) 额外空间。
回答by abiolaaye
public class ReverseInPlace {
static char[] str=null;
public static void main(String s[]) {
if(s.length==0)
System.exit(-1);
str=s[0].toCharArray();
int begin=0;
int end=str.length-1;
System.out.print("Original string=");
for(int i=0; i<str.length; i++){
System.out.print(str[i]);
}
while(begin<end){
str[begin]= (char) (str[begin]^str[end]);
str[end]= (char) (str[begin]^str[end]);
str[begin]= (char) (str[end]^str[begin]);
begin++;
end--;
}
System.out.print("\n" + "Reversed string=");
for(int i=0; i<str.length; i++){
System.out.print(str[i]);
}
}
}
回答by cocoper
An old post & question, however still did not see answers pertaining to recursion. Recursive method reverse the given string s, without relaying on inbuilt jdk functions
一个旧的帖子和问题，但是仍然没有看到与递归有关的答案。递归方法反转给定的字符串 s，而不依赖内置的 jdk 函数
public static String reverse(String s) {
if (s.length() <= 1) {
return s;
}
return reverse(s.substring(1)) + s.charAt(0);
}
`
`
回答by jags
Using String:
使用字符串：
String abc = "abcd";
int a= abc.length();
String reverse="";
for (int i=a-1;i>=0 ;i--)
{
reverse= reverse + abc.charAt(i);
}
System.out.println("Reverse of String abcd using invert array is :"+reverse);
Using StringBuilder:
使用 StringBuilder：
String abc = "abcd";
int a= abc.length();
StringBuilder sb1 = new StringBuilder();
for (int i=a-1;i>=0 ;i--)
{
sb1= sb1.append(abc.charAt(i));
}
System.out.println("Reverse of String abcd using StringBuilder is :"+sb1);
回答by Naren
One variant can be, swapping the elements.
一种变体可以是交换元素。
int n = length - 1;
char []strArray = str.toCharArray();
for (int j = 0; j < n; j++) {
char temp = strArray[j];
char temp2 = strArray[n];
strArray[j] = temp2;
strArray[n] = temp;
n--;
}
