这种插入排序在C中有什么问题？

Question

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <stddef.h>

void insertionSort(int ar_size, int* ar) {
    int i, j;
    int temp = 0;
    for (i = 1; i < ar_size; i++) {
        j = i;
        while (j > 0 && ar[i - 1] > ar[i]) {
            temp = ar[i - 1];
            ar[i - 1] = ar[i];
            ar[i] = temp;
            j--;
        }
    }
    for (j = 0; j < ar_size; j++) {
        printf("%d", ar[j]);
        printf(" ");
    }
}
int main(void) {
    int _ar_size;
    scanf("%d", &_ar_size);
    int _ar[_ar_size], _ar_i;
    for (_ar_i = 0; _ar_i < _ar_size; _ar_i++) {
        scanf("%d", &_ar[_ar_i]);
    }

    insertionSort(_ar_size, _ar);

    return 0;
}

我一直在寻找错误。我什么也看不见。这个代码有什么问题？

对于作为6和4 1 3 5 6 2的输入，它以1 3 4 5 2 6的形式给出输出。循环的迭代次数少了一次，但我不明白为什么？请帮帮忙。谢谢。

Answer 1

在函数的内部循环中，使用的是索引i而不是索引j。

    while(j>0 && ar[i-1]>ar[i])
    {
        temp = ar[i-1];
        ar[i-1] = ar[i];
        ar[i] = temp;
        j--;
    }

在这里，到处都必须使用索引j。

此外，函数还输出排序数组是个坏主意。它应该只做排序。另一个坏主意是使用以解核开头的标识符。当第一个参数是数组，第二个参数是数组的大小时，情况会更好。

代码可以如下所示

#include <stdio.h>

void InsertionSort( int *a, int n ) 
{    
    int i;

    for ( i = 1; i < n; i++ )
    {
        int j = i;
        while ( j > 0 && a[j-1] > a[j] )
        {
            int tmp = a[j-1];
            a[j-1]  = a[j];
            a[j]    = tmp;
            --j;
        }
    }
}



int main(void) 
{
    int size;
    scanf( "%d", &size );

    int a[size]; 
    int i;

    for ( i = 0; i < size; i++ ) scanf( "%d", &a[i] );

    for ( i = 0; i < size; i++ )
    {
        printf( "%d ", a[i] );
    }       
    puts( "" );

    InsertionSort( a, size );

    for ( i = 0; i < size; i++ )
    {
        printf( "%d ", a[i] );
    }       
    puts( "" );

    return 0;
}

如果输入是

10
 2 7 5 4 9 1 4 8 3 5

那么输出是

2 7 5 4 9 1 4 8 3 5 
1 2 3 4 4 5 5 7 8 9 

Answer 2

当将值推到前面时，您似乎使用了错误的迭代器。

while(j>0 && ar[j-1]>ar[j]) {
  temp = ar[j-1];
  ar[j-1] = ar[j];
  ar[j] = temp;
  j--;
}

Answer 3

试着在一张纸上做一次试运行，很容易发现问题所在。

for (i = 1; i < ar_size; i++) {
   j = i;
   while (j > 0 && ar[i-1] > ar[i]) {  // problem begins here
      temp = ar[i-1];
      ar[i-1] = ar[i];
      ar[i] = temp;
      j--;
   }
}

i在内部循环中不会改变。

在某个时候，您的程序将6与2交换，您的示例输入列表变为1 3 4 5 2 6，a[i-1]为2，a[i]为6，并且由于ar[i-1] > ar[i]条件，程序的流不会进入内环。

试试这个修复方法：

for (i = 1; i < ar_size; i++) {
   j = i;
   while (j > 0 && ar[j-1] > ar[j]) {
      temp = ar[j-1];
      ar[j-1] = ar[j];
      ar[j] = temp;
      j--;
   }
}