字元串反轉的9種方法

1. 使用Array.Reverse方法

對于字元串反轉，我們可以使用.NET類庫自帶的Array.Reverse方法

public static string ReverseByArray(string original)

{

char[] c = original.ToCharArray();

Array.Reverse(c);

return new string(c);

}

1. 使用字元緩存

在面試或筆試中，往往要求不用任何類庫方法，那麼有朋友大概會使用類似下面這樣的循環方法

public static string ReverseByCharBuffer(this string original)

{

char[] c = original.ToCharArray();

int l = original.Length;

char[] o = new char[l];

for (int i = 0; i < l ; i++)

{

o[i] = c[l - i - 1];

}

return new string(o);

}

當然，聰明的同學們一定會發現不必對這個字元數組進行完全周遊，通常情況下我們會隻周遊一半

public static string ReverseByCharBuffer2(string original)

{

char[] c = original.ToCharArray();

int l = original.Length;

for (int i = 0; i < l / 2; i++)

{

char t = c[i];

c[i] = c[l - i - 1];

c[l - i - 1] = t;

}

return new string(c);

}

ReverseByCharBuffer使用了一個新的數組，而且周遊了字元數組的所有元素，是以時間和空間的開銷都要大于ReverseByCharBuffer2。

在Array.Reverse内部，調用了非托管方法TrySZReverse，如果TrySZReverse不成功，實際上也是調用了類似ReverseByCharBuffer2的方法。

if (!TrySZReverse(array, index, length))

{

int num = index;

int num2 = (index + length) - 1;

object[] objArray = array as object[];

if (objArray == null)

{

while (num < num2)

{

object obj3 = array.GetValue(num);

array.SetValue(array.GetValue(num2), num);

array.SetValue(obj3, num2);

num++;

num2–;

}

}

else

{

while (num < num2)

{

object obj2 = objArray[num];

objArray[num] = objArray[num2];

objArray[num2] = obj2;

num++;

num2–;

}

}

}

大緻上我能想到的算法就是這麼多了，但是我無意間發現了StackOverflow上的一篇文章，才發現這麼一個看似簡單的反轉算法實作起來真可謂花樣繁多。

3. 使用StringBuilder

使用StringBuilder方法大緻和ReverseByCharBuffer一樣，隻不過不使用字元數組做緩存，而是使用StringBuilder。

public static string ReverseByStringBuilder(this string original)

{

StringBuilder sb = new StringBuilder(original.Length);

for (int i = original.Length - 1; i >= 0; i–)

{

sb.Append(original[i]);

}

return sb.ToString();

}

當然，你可以預見，這種算法的效率不會比ReverseByCharBuffer要高。

我們可以像使用字元緩存那樣，對使用StringBuilder方法進行優化，使其周遊過程也減少一半

public static string ReverseByStringBuilder2(this string original)

{

StringBuilder sb = new StringBuilder(original);

for (int i = 0, j = original.Length - 1; i <= j; i++, j–)

{

sb[i] = original[j];

sb[j] = original[i];

}

return sb.ToString();

}

以上這幾種方法按算法角度來說，其實可以歸結為一類。然而下面的幾種算法就完全不是同一類型的了。

使用棧

1. 棧是一個很神奇的資料結構。我們可以使用它後進先出的特性來對數組進行反轉。先将數組所有元素壓入棧，然後再取出，順序很自然地就與原先相反了。

public static string ReverseByStack(this string original)

{

Stack stack = new Stack();

foreach (char ch in original)

{

stack.Push(ch);

}

char[] c = new char[original.Length];

for (int i = 0; i < original.Length; i++)

{

c[i] = stack.Pop();

}

return new string(c);

}

兩次循環和棧的開銷無疑使這種方法成為目前為止開銷最大的方法。但使用棧這個資料結構的想法還是非常有價值的。

使用XOR

1. 使用邏輯異或也可以進行反轉

public static string ReverseByXor(string original)

{

char[] charArray = original.ToCharArray();

int l = original.Length - 1;

for (int i = 0; i < l; i++, l–)

{

charArray[i] ^= charArray[l];

charArray[l] ^= charArray[i];

charArray[i] ^= charArray[l];

}

return new string(charArray);

}

在C#中，x ^= y相當于x = x ^ y。通過3次異或操作，可以将兩個字元為止互換。對于算法具體的解釋可以參考這篇文章。

6. 使用指針

使用指針可以達到最快的速度，但是unsafe代碼不是微軟所推薦的，在這裡我們就不多做讨論了

public static unsafe string ReverseByPointer(this string original)

{

fixed (char* pText = original)

{

char* pStart = pText;

char* pEnd = pText + original.Length - 1;

for (int i = original.Length / 2; i >= 0; i–)

{

char temp = *pStart;

*pStart++ = *pEnd;

*pEnd– = temp;

}

return original;

}

}

1. 使用遞歸

對于反轉這類算法，都可以使用遞歸方法

public static string ReverseByRecursive(string original)

{

if (original.Length == 1)

return original;

else

return original.Substring(1).ReverseByRecursive() + original[0];

}

1. 使用委托，還可以使代碼變得更加簡潔

public static string ReverseByRecursive2(this string original)

{

Func