我的Insertion Sort实现可运行但迭代次数过高，是否存在逻辑错误？

核心问题 #

你代码的最大问题是在内层循环中修改了外层for循环的迭代变量i，这是导致迭代次数远超标准实现的根本原因：

• 标准插入排序的逻辑是：外层循环遍历未排序区间的每个元素，内层循环单次找到该元素在已排序区间的插入位置，一次插入完成后直接处理下一个未排序元素。
• 你的实现中，每次交换后执行i--，会让外层循环的迭代变量回退，外层for循环每次执行到末尾又会自动i++，等于同一个元素的插入过程会触发多次外层循环的执行，多出来非常多不必要的循环初始化、变量赋值操作。
• 你设计的flag优化逻辑完全没有发挥预期作用：只有当前元素本来就处于正确位置时才会触发break，一旦发生交换flag被设为0，后续内层循环的这个判断就完全是多余的开销。

直观示例验证 #

假设数组是[4,3,2,1]，处理最后一个元素1（初始i=3）：

• 标准实现内层循环j从2降到0，3次比较移动就完成插入，外层i直接跳到4结束循环。
• 你的实现中i会从3降到0，然后外层循环又把i加回1，等于要多执行3次外层循环的全部初始化流程（重新定义flag、val，重新初始化内层j变量），迭代次数直接翻了数倍。

正确实现参考 #

void InsertionSort(int arr[], int size)
{
    for (int i = 1; i < size; i++)
    {
        int val = arr[i];
        int j = i - 1;
        // 内层循环单独完成插入逻辑，不修改外层迭代变量i
        while (j >= 0 && arr[j] > val)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = val;
    }
}

这个实现和你的逻辑本质都是向前比较找插入位置，但是没有修改外层迭代变量，所有插入操作在单次内层循环中完成，没有额外的迭代开销，即使是最坏情况的常数项也远小于你的实现。

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