Straight Insertion，如何计算swap？

Question

这听起来可能很愚蠢，但我需要确认。例如我们有一个整数数组：

 [4 2 1 3]

所以当算法启动时，它应该像那样工作

 1. [2 4 1 3] 
 2. [1 2 4 3]  
 3. [1 2 3 4]

谁能帮我算一下每一步的交换次数？从我的角度来看，它可能是 1) 1 次交换，2) 2 次交换，3) 1 次交换。这个对吗？谢谢

算法：

for(i=1; i<N; i++)
{
    x = p[i];
    j = i -1;
    while(x<p[j] && j>=0)
    {
        p[j+1] = p[j];
        j = j-1;
    }
    p[j+1] = x;
}

Answer 1

首先，这个算法是一个新算法（不完全是插入排序，但很接近）

现在，该算法执行的交换次数为 0。它只是在做作业，根本没有交换。如果您将 while 中的作业数称为 swaps，那么是的，您是正确的。如果您想检查一下，只需将您的代码编辑为：

for(i=1; i<N; i++)
{
    x = p[i];
    j = i -1;
    int n=0;
    while(x<p[j] && j>=0)
    {
        p[j+1] = p[j];
        j = j-1;
        n++;
    }
    //output n, looks like c so
    printf("%d\n",n);
    p[j+1] = x;
}

Straight Insertion，如何计算swap？

Straight Insertion, how to count swaps?

algorithm

count

insertion