对于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 秒