这段插入排序代码有什么问题？

Question

我使用嵌套 for 创建了一个插入排序代码。只是因为我在 for 循环内的 if 部分中单独编写条件，所以它给了我不同的答案。请告诉我我的方法有什么问题。

我尝试在网上搜索但没有得到结果 这是我的代码：

#include <stdio.h>

int main() {
    int i, j;
    int arr[] = {32, 5, 45, 8, 17, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("Before Sorting: ");
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    for (i = 1; i < size; i++) {
        int key = arr[i];
        for (j = i - 1; j >= 0; j--) 
        {
            if(arr[j] > key)
                arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
    
    printf("\nAfter Sorting: ");
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Answer 1

嵌套for循环的问题

for (i = 1; i < size; i++) {
    int key = arr[i];
    for (j = i - 1; j >= 0; j--) 
    {
        if(arr[j] > key)
            arr[j + 1] = arr[j];
    }
    arr[j + 1] = key;
}

是

arr[0]

始终设置为

key

，因为在内部 for 循环之后

j

等于

-1

。

您可以重写它们，例如

for (i = 1; i < size; i++) {
    int key = arr[i];
    j = i - 1;

    for ( ; j >= 0 && key < arr[j]; --j )
    {
        arr[j+1] = arr[j];
    }    

    arr[j+1] = key;
}

注意 sizeof 运算符产生的值的类型为

size_t

类型。这样写会比较正确

size_t size = sizeof(arr) / sizeof(arr[0]);

此外，您还应该在使用变量的最小范围内声明变量。

我会按以下方式编写程序

#include <stdio.h>

int main( void )
{
    int arr[] = { 32, 5, 45, 8, 17, 82, 10 };
    size_t size = sizeof( arr ) / sizeof( arr[0] );

    printf( "Before Sorting: " );
    for ( size_t i = 0; i < size; i++)
    {
        printf( "%d ", arr[i] );
    }
    putchar( '\n' );

    for ( size_t i = 1; i < size; i++ )
    {
        if (arr[i] < arr[i - 1])
        {
            int key = arr[i];

            size_t j = i;

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

            arr[j] = key;
        }
    }

    printf( "\nAfter Sorting: " );
    for ( size_t i = 0; i < size; i++)
    {
        printf( "%d ", arr[i] );
    }
    putchar( '\n' );
}