arrays - 调用函数对 n 个数字的数组进行排序时出错

Question

我正在尝试编写一个名为 selection_sort 的函数.这个函数应该，当出现一个由 n 个整数组成的数组时，搜索数组以找到最大的元素，然后将它移动到数组的最后一个位置。完成此操作后，它应递归调用自身以对数组的前 n-1 个元素进行排序。
这是我的代码:

#include <stdio.h>

void selection_sort(int [], int);

int main(void)
{
  int n, a[n];
  printf("How many numbers do you wish to sort? ");
  scanf("%d", &n);

  printf("Well go on, type them in... "); 
  for(int i = 0; i < n; i++)
    scanf("%d", &a[i]);

  selection_sort(a, n); 

  printf("Here is the sorted array: ");
  for(int i = 0; i < n; i++) 
    printf("%d ", a[i]);
  printf("\n");

 return 0;
}

void selection_sort(int a[], int n)
{
  if(n == 1) return;
  
  int temp, largest = 0;
  
  for(int i = 1; i < n; i++) {
    if(a[i] > a[largest])  
      largest = i;
  }

  temp = a[largest];
  a[largest] = a[n-1];
  a[n-1] = temp; 
   
  selection_sort(a, n-1);
}

当我运行这段代码时，我得到了段错误:11。看起来我的代码的任何部分都没有超出数组的边界。我知道长度为 n 的数组的索引从 0 到 n-1。到底是怎么回事？

Answer 1

这个数组的声明

int n, a[n];

具有未定义的行为，因为变量 n用作数组的大小未初始化并且具有不确定的值。
您首先需要为变量 n 分配一个正值然后才声明数组 a .

int n;
 
printf("How many numbers do you wish to sort? ");
scanf("%d", &n);

int a[n]; 

如果用户由于此条件将非正值作为第二个参数传递，则您的函数也可以调用未定义的行为

if(n == 1) return;

按照以下方式更改它

if(n < 2) return;

如果编写一个辅助递归函数来搜索数组中的最大元素，则可以使您的函数更加“递归”。
这是一个演示程序。

#include <stdio.h>

size_t max_element( const int a[], size_t n )
{
    if ( n < 2 ) return 0;
    
    size_t i1 = max_element( a, n / 2 );
    size_t i2 = n / 2 + max_element( a + n / 2, n - n / 2 );
    
    return a[i1] < a[i2] ? i2 : i1;
}

void selection_sort( int a[], size_t n )
{
    if ( !( n < 2 ) )
    {
        size_t largest = max_element( a, n );
        
        if ( largest != n-1 )
        {
            int tmp = a[n-1];
            a[n-1] = a[largest];
            a[largest] = tmp;
        }
        
        selection_sort( a, n - 1 );
    }
}

int main(void) 
{
    size_t n;
    
    do
    {
        printf( "How many numbers do you wish to sort (enter a positive number)?  "  );
    } while ( scanf( "%zu", &n ) != 1 || n < 1 );
    
    int a[n];
    
    printf( "Well go on, type them in... " ); 
    for ( size_t i = 0; i < n; i++ )
    {
        scanf( "%d", a + i );
    }
    
    selection_sort( a, n ); 

    printf( "Here is the sorted array: " );
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d ", a[i] );
    }       
    putchar( '\n' );
    
    return 0;
}

程序输出可能看起来像

How many numbers do you wish to sort (enter a positive number)?  10
Well go on, type them in... 9 8 7 6 5 4 3 2 1 0
Here is the sorted array: 0 1 2 3 4 5 6 7 8 9