关于插入排序复杂度的疑问及C#基准测试结果困惑

核心问题：基准测试复用已排序数组导致最优复杂度触发 #

你的测试结果呈现线性特征，核心原因是基准测试中复用了已排序的数组，而插入排序在完全有序的数组上的时间复杂度是O(n)（最优情况），而非平均情况的O(n²)。

看你的Benchmark类代码：

public class BE{
public long A { get; set; }   
public long[] arra;
public BE()
{
    arra = RandomUtils.generateArray(100000); // 1,10,100,...
}
[Benchmark]
public void Benchmarka() => sort_insertion.insertsort(arra, arra.Length);
}

如果使用BenchmarkDotNet这类工具，默认会对同一个实例运行多次基准测试迭代。第一次调用Benchmarka时，数组会被排序为有序状态，后续所有迭代都是对已经有序的数组执行插入排序。此时插入排序的内层循环每次仅需一次比较就会退出（item >= data[j]，设置ins=1终止循环），总操作数为O(n)，自然呈现线性耗时特征。

即使你是每次修改generateArray的参数后单独运行程序，若短时间内多次运行，Random实例的种子基于系统时钟生成，可能会重复生成相同的数组；或者你误将排序后的数组重复用于测试，也会导致同样的线性结果。

插入排序代码的冗余问题（不影响复杂度） #

你的插入排序实现逻辑正确，但存在冗余操作：

if (item < data[j])
{
    data[j + 1] = data[j];
    j--;
    data[j + 1] = item; // 每次移动后都赋值item，可优化
}

标准插入排序会先暂存item，将所有大于item的元素后移，最后再将item插入正确位置，这样可以减少赋值次数，但不会改变时间复杂度。你的实现虽然多了几次赋值，但理论上平均情况仍为O(n²)。

大O表示法的理解澄清 #

插入排序的平均情况和最坏情况是O(n²)，但最优情况（数组已完全有序）是O(n)。大O表示法描述的是渐近复杂度，当n足够大时，不同复杂度的差异才会显著。但你的测试中如果是随机数组，n=10000的耗时应该是n=1000的约100倍（因为(10000)²/(1000)²=100），而非你测试中的10倍，这进一步验证了测试数据是基于有序数组。

修正测试的建议 #

• 每次基准测试迭代前重新生成随机数组，确保每次排序的都是未排序的随机数据：

  [Benchmark]
  public void Benchmarka() 
  {
      var arra = RandomUtils.generateArray(10000); // 根据测试n调整参数
      sort_insertion.insertsort(arra, arra.Length);
  }
  

• 重用Random实例避免重复随机序列：

  public static class RandomUtils
  {
      private static readonly Random _random = new Random();
      public static long[] generateArray(int count)
      {
          long[] values = new long[count];
          for (int i = 0; i < count; ++i)
              values[i] = _random.Next();
          return values;
      }
  }
  

• 测试更大的n值（如100000），观察随机数组下的耗时增长是否符合O(n²)特征（n扩大10倍，耗时约扩大100倍）。

内容的提问来源于stack exchange，提问作者user232560