c - 插入排序(降序)——我在这里缺少什么？

Question

所以，我在这个插入排序算法上苦苦挣扎，我不明白为什么我会得到这个输出。我已经在纸上浏览过它，当我逐步浏览它时它在那里工作...发生了什么事？

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

Answer 1

当条件错误时:

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

应该是:

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

因为 arrayIn[j]只不过是 arrayIn[i + 1]在 while 循环的第一次迭代中，可以在 arrayIn[i+1] = arrayIn[i]; 中覆盖一会儿。

在插入排序中，你在排序数组中插入一个值，在外循环中，你读取到arrayIn[j]。在 temp .现在你要插入 temp在排序位置，对于每个 arrayIn[i]小于 temp需要轮类 arrayIn[i+1] = arrayIn[i];第一次可以写信给arrayIn[j] = arrayIn[i];如果arrayIn[j] > arrayIn[i];因为j = i + 1 .

编辑，来自@M Oehm :您的外部 for 循环仅针对 i = 1 到 3 运行并且不插入 arrayIn[4]到排序位置，更改 j < 5 - 1;至 j < 5 .