C中的插入排序算法

Question

我对以下插入排序代码有疑问：

void insertion(Item a[], int ell, int r)                
{               
    int i;          
        for (i=ell+1; i<=r; i++)            
           compexch(a[ell], a[i]);          
    {           
        for (i=ell+2; i<=r; i++)        
        {       
            int j=i;    
            Item v=a[i];    
            while(less (v, a[j-1])) 
            {   
                a[j]=a[j-1];
                j--;
            }   
            a[j]=v;
        }       

    }           
}

好的，所以我的问题具体是关于 while 循环部分——我看到 j 递减，想知道当 j=0 和 a[-1] 发生时会发生什么。我不明白我们怎么可以允许负索引——如果我们比较的信息恰好解决了并且 while 循环继续到运行怎么办？谢谢。

Answer 1

我假设 compexch(x,y) 做了类似 if (less(y,x)) { Item t = x; x=y; y=t } 的事情。因此，在第一个 for 循环完成后，a[ell] 包含 a[ell+1],...,a[r] 中最少的 Item。现在 j 被初始化为值 i，它至少是 ell+2，所以我们在进入 while 循环时有 j > ell。如果 while 循环不尽早终止，我们最终会下降到 j == ell。由于 a[ell] 已经设置为范围中的最小元素，因此 less(v, a[ell]) 必然会 return 为假，然后循环将终止。

所以j永远不会减少到小于ell的值。

C中的插入排序算法

Insertion Sort Algorithm in C

c

algorithm

sorting

selection