c - 插入排序的错误输出

Question

我在执行我的程序时得到了错误的输出，我不知道是什么导致了它。

正如您在下面看到的，我有一个数组。但是，在执行程序时，我得到了输出:

array[0]=3
array[1]=1
array[2]=1
array[3]=5
array[4]=5
array[5]=8

显然这不是我预期的输出 {1,3,4,5,7,8}。我做错了什么？

#include <stdio.h>
#include <stdlib.h>
#define l 6

void isnertionSort(int array[]);

int main(void)
{
  int array[l]={3,4,1,7,5,8};

  for(int i=0; i<l;i++) {
    printf("array[%d]=%d\n", i, array[i]);
  }
  printf("\n");

  isnertionSort(array);

  for(int i=0; i<l; i++){
    printf("array[%d]=%d\n", i, array[i]);
  }

  return 0;
}


void isnertionSort(int array[])
{
  int j,key;
  for(int i =1;i<l;i++){
    key = array[i];

    j = i -1;

    while(j>0 && array[j]>key){
      array[j+1]=array[i];
      j--;//j=j-1                                                                                                  

    }
    array[j+1]= key;
  }
}

Answer 1

您的内部循环有两个小错误。

while(j >= 0 && array[j]>key) { /* j> 0 changed to j>=0 */
    array[j+1]=array[j];  /* changed from i to j */
    j--;
}

如果将您的实现与 insertion sort 进行比较，调试起来相当简单算法。如果您缩进代码以便更容易发现此类错误，这也会有所帮助。