插入排序的错误输出

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算法比较你实现调试。如果您缩进代码，这样也可以帮助您更轻松地发现这些错误。

Answer 2

对于初学者，程序中既没有使用标题<stdlib.h>的声明。所以指令

#include <stdlib.h> 

可能会被删除。

对#defined名使用大写字母好得多。例如

#define N 6 

这是难以区分低情况下信l和1为代码的读取器。

您应该编写一个通用的排序函数，而不是只能接受固定6个元素的数组的函数。因此函数应该具有两个参数，例如

void isnertionSort(int array[], size_t n); 

这个循环

1）不接触与索引等于0和1的阵列的元件和2）组被声明因为key和array[i]是相同的值，所以大于key的所有元素都大于key。

array[j+1]=array[i]; 
      ^^^^^^^^ 

考虑到所有这些因素的程序可以看看下面的方式

#include <stdio.h> 

#define N 6 

void isnertionSort(int array[], size_t n); 

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

    for (size_t i = 0; i < N; i++) 
    { 
     printf("array[%zu] = %d\n", i, array[i]); 
    } 
    putchar('\n'); 

    isnertionSort(array, N); 

    for (size_t i = 0; i < N; i++) 
    { 
     printf("array[%zu] = %d\n", i, array[i]); 
    } 
    putchar('\n'); 

    return 0; 
} 

void isnertionSort(int array[], size_t n) 
{ 
    for(size_t i = 1; i < n; i++) 
    { 
     size_t j = i; 
     int value = array[i]; 

     for (; j != 0 && value < array[j-1]; --j) 
     { 
      array[j] = array[j-1]; 
     } 

     if (j != i) array[j] = value;   
    } 
} 

程序输出是

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

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