c - 通过插入排序对数组进行排序

Question

我正在尝试使用插入排序对数组进行排序。
我没有更改和重新排列数组本身的元素，而是使用另一个名为Rank的数组来映射以指向原始数组。
这是我的代码

int i,j;
int ar[] = {50,14,51,25,10};
int rank[] = {0,1,2,3,4};
for(i=1 ; i< 5 ; ++i)  // second element onwards
{
    int temp = rank[i];  // stores current value in temp variable      

    /**
     * temp = 1
     * j = 0 
     */
    j = rank[i] - 1;
    while ( ar[temp] < ar[ rank[j] ] && j > -1)
    {
        rank[j+1] = rank[j];      // move elemnts in map forward
        j--;
    } // end loop

    // insert temp at proper place
    rank[j+1] = temp;    

}

for(i=0 ; i< 5 ; ++i)
    printf("Rank : %d, Number : %d \n",rank[i],ar[i]);

但是，它没有给出预期的输出。谁能指出逻辑上的错误是什么？

Answer 1

你的逻辑缺陷如下: 在此代码部分

   while ( ar[temp] < ar[ rank[j] ] && j > -1)
    {
        rank[j+1] = rank[j];      // move elemnts in map forward
        j--;
    } // end loop

rank[j]表示 ar[j] 处的值的排名。

当你使用ar[rank[j]]时，您正在比较ar[temp]到索引为 "the rank of the value at ar[ j ]" 的值，这意味着您没有与 rank[] 的排序部分中的最大值进行比较.

因此，即使 ar[temp] 你也可能不会进入这个循环。是第二小的

例如:

到目前为止，在loop#2期间(i = 2)

ar[] : {50,14,51,25,10};

rank[] : {1,0,2,3,4}; ({1,0} is the sorted portion of rank[])

0仅意味着14是 {50,14} 中的最小值( ar[] 的扫描部分) 和 ar[rank[2]] ( ar[0] ) 恰好是 {50,14} 中的最大值(ar[] 的扫描部分)巧合

如果这个值( ar[rank[2]] )不是最大的，并且恰好小于 ar[temp] ，您的程序将跳过循环。即使ar[temp]小于 ar[] 中的所有其他值