对于List<T>元素排序的性能一直想测试一下。例如有一个关于明星的列表list { “黎明”, “张学友” , “周星驰” ….} 我希望第 m 个元素的位置排序到第 n 个位置。
例如 list[0] -> 2, { “张学友” , “周星驰” ,”黎明”, ….}
废话不多说,我采用了两种方法:【直接插入法】、【局部遍历法】
在开始之前,先创建一个 list 用来测试,传入一个num变量用来改变元素多寡。可以测试在元素变化时对效率有何影响。
public static void TestListSetRank(int num) { List<string> list = new List<string>(); for (int i = 0; i < num; i++) list.Add("a" + i); }
第一种 【直接插入法】 ,直接插入法意思是,既然已经知道了 起点 m 和 终点 n。那么我先把m位置的引用给删掉, 再把它插入n的位置。
【 直接插入法 】的代码如下,我把它定义成委托func1:
var func1 = new Action<int, int>((n, m) => { if (n == m) return; var str = list[m]; list.RemoveAt(m); list.Insert(n, str); });
第二种 【局部遍历法】,根据 m、n的位置关系确定局部区域,把每个元素的指向引用更改。
【局部遍历方法】的代码如下 ,我把它定义成委托func2:
var func2 = new Action<int, int>((n, m) => { if (n == m) return; var str = list[m]; int stepnum = n < m ? -1 : 1; for (int i = m; i != n; i = i + stepnum) list[i] = list[i + stepnum]; list[n] = str; });
测试方法:使用一个rodm随机发生器,随机产生在 0~list.Count范围内的两个位置,即 n和m。然后分别调用两个委托方法进行测试。测试结果如下:
创建 10 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3218094 秒
采用【局部遍历】的方法操作元素:共计耗时 0.9492085 秒
创建 100 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3415924 秒
采用【局部遍历】的方法操作元素:共计耗时 3.8234382 秒
创建 1000 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 3.0650181 秒
采用【局部遍历】的方法操作元素:共计耗时 28.1718113 秒
总结:【局部遍历法】对小节点量的排序还可以接受,一旦容量增大,性能损失严重。【直接插入法】相对比较稳定,通过查看List源码可以知道它在后台调用了两次Array Copy方法(插入时调用一次,删除时调用一次)。 以上,对于元素较少的情况,局部遍历法的效率比 调用Copy的开销小,随着元素量增加,则采用直接插入法最好。

完整测试代码:
static void Main(string[] args) { TestListSetRank(10); TestListSetRank(100); TestListSetRank(1000); Console.ReadKey(); } public static void TestListSetRank(int num) { List<string> list = new List<string>(); for (int i = 0; i < num; i++) list.Add("a" + i); var func1 = new Action<int, int>((n, m) => { if (n == m) return; var str = list[m]; list.RemoveAt(m); list.Insert(n, str); }); var func2 = new Action<int, int>((n, m) => { if (n == m) return; var str = list[m]; int stepnum = n < m ? -1 : 1; for (int i = m; i != n; i = i + stepnum) list[i] = list[i + stepnum]; list[n] = str; }); var rodm = new Random(); int total = 10000000; Console.WriteLine("创建 {0} 个节点:", num); Console.Write("使用 Insert 和 RemoveAt 方法操作元素:"); var sw = Stopwatch.StartNew(); for (int i = 0; i < total; i++) { var n = rodm.Next(0, num - 1); var m = rodm.Next(0, num - 1); func1(n, m); } sw.Stop(); Console.WriteLine("共计耗时 {0} 秒", sw.Elapsed.TotalSeconds); Console.Write("采用【局部遍历】的方法操作元素:"); sw.Restart(); for (int i = 0; i < total; i++) { var n = rodm.Next(0, num - 1); var m = rodm.Next(0, num - 1); func2(n, m); } sw.Stop(); Console.WriteLine("共计耗时 {0} 秒", sw.Elapsed.TotalSeconds); }
编辑:经过分析,上文说的元素小的list不太准确,应该是n与m差值小的情况。现在定义一个委托方法func3,它根据差值决定采用哪种方法,我管这个叫混合模式。
【混合模式】的代码如下 ,我把它定义成委托func3:
var func3 = new Action<int, int>((n, m) => { if (n == m) return; if (Math.Abs(n - m) < 10) func2(n, m); else func1(n, m); });
重新测试,结果如下。使用这种模式,list可以根据移动距离选择最佳的排序模式,以实现性能优化。

创建 3 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 0.8282541 秒
采用【局部遍历】的方法操作元素:共计耗时 0.6876499 秒
采用【混合模式】的方法操作元素:共计耗时 0.7015953 秒
创建 5 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 0.902439 秒
采用【局部遍历】的方法操作元素:共计耗时 0.7280125 秒
采用【混合模式】的方法操作元素:共计耗时 0.8775396 秒
创建 7 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 0.9871264 秒
采用【局部遍历】的方法操作元素:共计耗时 0.7870832 秒
采用【混合模式】的方法操作元素:共计耗时 0.9757926 秒
创建 10 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.0613971 秒
采用【局部遍历】的方法操作元素:共计耗时 0.899727 秒
采用【混合模式】的方法操作元素:共计耗时 1.0612489 秒
创建 30 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.2957685 秒
采用【局部遍历】的方法操作元素:共计耗时 1.7546192 秒
采用【混合模式】的方法操作元素:共计耗时 1.3904508 秒
创建 50 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3147112 秒
采用【局部遍历】的方法操作元素:共计耗时 2.0260564 秒
采用【混合模式】的方法操作元素:共计耗时 1.4525724 秒
创建 70 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3862056 秒
采用【局部遍历】的方法操作元素:共计耗时 2.5569355 秒
采用【混合模式】的方法操作元素:共计耗时 1.5220287 秒
创建 100 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.3969189 秒
采用【局部遍历】的方法操作元素:共计耗时 3.4157527 秒
采用【混合模式】的方法操作元素:共计耗时 1.5469496 秒
创建 300 个节点:
使用 Insert 和 RemoveAt 方法操作元素:共计耗时 1.8116123 秒
采用【局部遍历】的方法操作元素:共计耗时 8.974341 秒
采用【混合模式】的方法操作元素:共计耗时 2.0337284 秒