Java数据结构：插入排序（Insertion sort）原语操作中for循环未用求和形式的疑问

嘿，这个问题戳中了算法复杂度分析里一个很容易混淆的点，我来给你拆解清楚～

首先，咱们先把插入排序的核心Java代码摆出来，方便对照分析：

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 原语操作：读取、赋值
        int j = i - 1;
        // 内层嵌套循环（换成for循环逻辑一致）
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 原语操作：读取、赋值
            j--; // 原语操作：自减
        }
        arr[j + 1] = key; // 原语操作：赋值
    }
}

为什么嵌套循环要用求和形式？ #

咱们看插入排序的内层循环：外层循环每执行一轮（对应i从1到n-1），内层循环的执行次数是不一样的——最坏情况下数组完全逆序，内层循环要执行i次（把当前元素key往前挪到最前面）。

这时候计算总原语操作数，就必须把每一轮外层循环对应的内层操作数加起来，也就是求和从i=1到i=n-1的内层操作次数。因为每一轮的次数都有差异，没法用一个固定的乘法来概括，所以必须用求和符号来累加这些不同的数值。

为什么有的for循环不用求和形式？ #

你看到的“未采用求和形式”的for循环，通常是两种情况：

• 单一循环，迭代次数固定且每次操作数相同：比如一个简单的遍历循环：

  for (int i = 0; i < n; i++) {
      System.out.println(arr[i]);
  }
  

  这里每次循环的原语操作数是固定的（读取数组元素、打印），循环总次数是n次。求和的话是Σ（从i=0到n-1）k（k是每次循环的操作数），结果就是n*k，所以大家会直接写n*k而省略求和符号——这本质上是求和的简化表达，不是不用求和，而是结果可以简化成乘法。

• 嵌套循环，但内层循环次数不依赖外层变量：比如二维数组的初始化：

  for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
          arr[i][j] = 0;
      }
  }
  

  内层循环每次都执行m次，和外层的i无关。这时候总操作数是Σ（从i=0到n-1）m，结果就是n*m，同样可以直接用乘法代替求和，看起来就没用到求和形式。

回到插入排序的场景 #

插入排序里，外层循环的非内层操作（比如key = arr[i]、j = i-1这些），每一轮的操作数是固定的，所以这部分的总操作数可以直接算(n-1)*固定数，不用求和；但内层循环因为每轮次数不同，必须用求和来累加。

总结一下：是否用求和形式，核心看循环的执行次数是否随外层变量变化。如果每一轮的次数都不一样，必须用求和来累加；如果次数固定，求和可以简化为乘法，所以会直接写简化后的结果，看起来像是没用求和，但本质上还是求和的一种简化表达。

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