插入排序（降序） - 我在这里错过了什么？

所以，我在这个插入排序算法上很努力，我不明白为什么我会得到这个输出。我已经在纸上读过它，并且在我逐步浏览它的时候在那里工作......发生了什么？插入排序（降序） - 我在这里错过了什么？

int main(int argc, char * argv[]){ 

    int arrayIn[5]; 


    /* Insertion func */ 

    printf("==============================\n"); 

    for(int k=0; k<5; k++){ 
     arrayIn[k] = k + 1; 
    } 

    for(int y = 0; y < 5; y++){ 
     printf("array[%d]: %d \n", y, arrayIn[y]); 
    } 

    //insertion 

    for (int j = 1; j < 5 - 1; j++) { 
     int i = j - 1; 
     int temp = arrayIn[j]; 

     while (i >= 0 && arrayIn[i] < arrayIn[j] /* Aj < Ai */) { 
     arrayIn[i+1] = arrayIn[i]; 
     i--; 
     } 
     arrayIn[i+1] = temp; 

    } 

    for(int p = 0; p < 5; p++){ 
     printf("array[%d]: %d \n", p, arrayIn[p]); 
    } 



    return(0); 
}

这是我得到的输出：

插入排序前：

array[0]: 1 
array[1]: 2 
array[2]: 3 
array[3]: 4 
array[4]: 5

插入排序后：

array[0]: 2 
array[1]: 3 
array[2]: 4 
array[3]: 1 
array[4]: 5

来源

2014-01-26 marcello

虽然条件是错误的：

while (i >= 0 && arrayIn[i] < arrayIn[j])

应该是：

while (i >= 0 && arrayIn[i] < temp)

因为arrayIn[j]不过arrayIn[i + 1]在第一次迭代中while循环，可以在同时在编写中arrayIn[i+1] = arrayIn[i];。

在插入排序中，您将在排序数组中插入一个值，在外部循环中，您读取temp中的arrayIn[j]。现在您要在排序位置插入temp，并且对于小于temp的每个arrayIn[i]需要一个班次arrayIn[i+1] = arrayIn[i];如果arrayIn[j] > arrayIn[i];因为j = i + 1而首次可以写入arrayIn[j] = arrayIn[i];。

编辑，从@M Oehm：此致外的只是对于i循环运行= 1至3和不插入到arrayIn[4]排序位置，更改j < 5 - 1;到j < 5。

来源

2014-01-26 12:23:06

是的，我只是意识到自己。但是，我的输出仍然不太正确... – marcello

您还必须调整外循环以从[[1：5]'：'for（int j = 1; j <5 - 1; j ++）'运行。 –

@MOehm你是对的谢谢！ –

插入排序（降序） - 我在这里错过了什么？

回答

相关问题