c - 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] 中最少的 Item， ...,a[r]。现在 j 用值 i 初始化，它至少是 ell+2，所以我们有 j > ell 在进入 while 循环时。如果 while 循环不尽早终止，我们最终会得到 j == ell。由于 a[ell] 已经设置为范围内的最小元素，less(v, a[ell]) 必然返回 false，循环将终止那么。

因此 j 永远不会减少到小于 ell 的值。