C# 中的各种字符串反转算法
2.61/5 (13投票s)
C# 中各种字符串反转算法的代码示例
引言
本文阐述了用 C# 实现的不同字符串反转算法，并从时间和空间使用考虑了它们的性能和效率。
背景
FCL（Framework Class Library）不提供任何内置的字符串反转方法。我一直在研究 C# 中各种可能的字符串反转算法，这些算法可以在空间和时间约束方面进行比较。
使用代码
首先，让我们看看一个非常基础和简单的反转 C# 中给定字符串的方法。这使用交换机制来反转字符串。将输入字符串传递给方法并转换为 CharArray。然后对字符数组逐个字符地执行交换，然后将其转换为字符串并作为反转的字符串返回。这是一种相当平庸但最常用的反转技术，因为它具有平均性能，并且需要两次复制的开销（一个到字符数组，另一个到原始字符串，因为字符串是不可变的）。
/// <summary>
/// String Reversal with Swap algorithm - trivial one.. average performance and the overhead of copying twice
/// (one to char array and other to original as strings are immutable)
/// Extra variable is used as temp unnecessarily
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWithSwapAlgo(string source)
{
char[] inputstream = source.ToCharArray();
for (int i = 0, j = inputstream.Length - 1; i < j; i++, j--)
{
char temp = inputstream[i];
inputstream[i] = inputstream[j];
inputstream[j] = temp;
}
return new string(inputstream);
}
这个使用 CopyTo Char 数组。同样，一个平凡的方法，性能一般。注意“注释”部分。与之前的技术唯一的区别在于此处使用原地交换，而没有任何临时变量。内存效率高，但与之前的性能相比，差异不大。
/// <summary>
/// String Reversal with Copy to Char Array - trivial one.. average performance and the overhead of copying twice
/// (one to char array and other to original as strings are immutable)
/// No use of temp variable so memory efficient normal reversal
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWithCharArray(string source)
{
char[] inputstream = source.ToCharArray();
for (int i = 0, j = inputstream.Length - 1; i < j; i++, j--)
{
inputstream[j] = source[i];
inputstream[i] = source[j];
}
return new string(inputstream);
}
现在让我们尝试一些不同的方法。这次使用递归。这可能是你能找到的最简单的递归反转方法，而且就在字符串反转中！尽管在这里我使用 C# 中的 SubString 函数来实现分割/交换。
/// <summary>
/// String Reversal with Recursion - no extra memory usage although it uses stack internally.
/// Perf wise works well for smaller strings but average for large strings
/// </summary>
/// <param name="source"></param>
/// <param name="len"></param>
/// <returns></returns>
private static string ReverseWithRecursion(string source, int len)
{
if (len == 1)
return source;
else
return ReverseWithRecursion(source.Substring(1, source.Length-1),--len) + source[0].ToString();
}
跳出思维定式！使用堆栈作为数据结构的字符串反转。FILO 实际上是反转字符数组背后的概念。首先将字符串中的字符推入堆栈，然后弹出它们，这样得到的字符串就会自动反转。性能几乎与普通反转相同。请注意，使用了两个循环。
/// <summary>
/// String Reversal with Stack - uses FILO structure for string reversal.
/// Performance is almost equal to the normal reversals.
/// Note that two loops are being used
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWithStack(string source)
{
Stack<string> inputStack = new Stack<string>();
for (int i = 0; i < source.Length; i++)
inputStack.Push(source.Substring(i, 1));
string resultstring = string.Empty;
for (int i = 0; i < source.Length; i++)
resultstring += inputStack.Pop();
return resultstring;
}
让我们使用 Char 数组使用复制重新审视我们最初的平凡方法，这次优化它们，而没有两次复制的开销。我们避免了 CopyTo Char 数组，而是使用了一个新的 char[] 缓冲区。如果你已经注意到 for 循环中的条件。它是 i<=j。为什么我们需要额外的迭代？那是因为如果字符串中的字符数为奇数，我们需要恢复中间的字符。有效，因为它不使用复制到字符数组，并且字符串是不可变的，因此在新 char[] 和原始字符串状态在整个反转过程中分别维护。
/// <summary>
/// String Reversal without Copy to Char Array -
/// efficient because it doesnt use copying to char array and
/// strings are immutable so new char[] and original string states are maintained separately throughout reversal
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWithCharArrayWithoutCopy(string source)
{
char[] inputstream = new char[source.Length];
for (int i = 0, j = inputstream.Length - 1; i <= j; i++, j--)
{
inputstream[j] = source[i];
inputstream[i] = source[j];
}
return new string(inputstream);
}
另一种反转字符串的创新方法。你知道这可以通过数组反转来实现吗！数组反转是 FCL 提供的一个内置方法。这非常快，因为它使用原生代码来实际执行反转。目前最有效！
/// <summary>
/// String Reversal without Copy to Char Array -
/// most efficient as it uses TrySZReverse of ArrayHelpers in native code
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWithArrayReversal(string source)
{
char[] inputstream = source.ToCharArray();
Array.Reverse(inputstream);
return new string(inputstream);
}
还有很酷的一个。使用 BitWise XOR！它是如何工作的？
XOR 表示 [0 XOR 0 = 0]，[0 XOR 1 = 1]，[1 XOR 0 = 1]，[1 XOR 1 = 0]。
现在假设我们有两个二进制值 A = 1 0 0 和 B = 1 1 1，我们想使用 XOR 来交换它们。我们该怎么做？在纸上试试，你会感到惊讶！
/// <summary>
/// String Reversal with Bitwise XORing.. cool stuff and quick one too without extra memory usage!!
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWithBitwiseXOR(string source)
{
char[] inputstream = source.ToCharArray();
int length = source.Length - 1;
for (int i = 0; i < length; i++, length--)
{
inputstream[i] ^= inputstream[length];
inputstream[length] ^= inputstream[i];
inputstream[i] ^= inputstream[length];
}
return new string(inputstream);
}
这个方法是由我的朋友 Murli Krishna 建议的。
public static string StringReversal(string str)
{
char[] revStr = new char[str.Length];
GCHandle handle = GCHandle.Alloc(str, GCHandleType.Pinned);
IntPtr pointer = handle.AddrOfPinnedObject();
for (int i = str.Length-1,j=0; i >= 0; --i,++j)
{
revStr[j] =(char) Marshal.ReadByte(pointer, 2 * i);
}
handle.Free();
return new string(revStr);
}
欢迎提出更多此类方法的建议！
本文的另一个更新在这里。我添加了一种算法来原地反转语句中的所有单词。想法是首先将语句（一组字符串）转换为字符数组流，然后反转该流。之后，提取单个单词（现在已反转），然后逐个反转它们，最终得到一个反转的语句。在下面找到代码。
/// <summary>
/// Operation to reverse the sequence of words in a statement (string). This is an in-place strings reversal algorithm (words reversal)
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
private static string ReverseWordsInString(string source)
{
char[] reversedCharArray = ReverseWithArrayReversal(source).ToCharArray();
int wordStart = 0;
while (wordStart < reversedCharArray.Length)
{
while(wordStart < reversedCharArray.Length - 1 && !char.IsLetter(reversedCharArray[wordStart]))
{
wordStart++;
}
int wordEnd = wordStart;
while(wordEnd < reversedCharArray.Length - 1 && char.IsLetter(reversedCharArray[wordEnd +1]))
{
wordEnd++;
}
if(wordEnd > wordStart)
{
int start = wordStart;
int end = wordEnd;
while (start < end)
{
char temp = reversedCharArray[start];
reversedCharArray[start] = reversedCharArray[end];
reversedCharArray[end] = temp;
start++;
end--;
}
}
wordStart = wordEnd + 1;
}
return new string(reversedCharArray);
}