あえてLINQで書くのが俺のジャスティス
new string((from c in str let p = new {r = r.Next(), c} orderby p.r select p.c).ToArray());