调用函数对 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 是一种可以有陷阱表示的类型，没有地址，是一个局部范围的自动存储变量并且没有被初始化——因此有一个不确定的值。虽然使用它作为数组大小肯定会产生问题。

为避免这种情况，您可以在成功从用户那里获取值并将其分配给 n 后使用 n。伪代码看起来像

integer n = 0;

if ( scan_from_user_and_check_success (&n) ) //function returns 0 in failure
{
    array a[n];

    // use `a[n]`

}

Answer 2

我认为问题出在这里：

int n, a[n];

您正在尝试动态分配大小为 n 的整数数组。在编译时，n 具有不确定的值。不幸的是你没有分配任何东西。您只声明了一个没有分配的数组。

请阅读this article关于动态分配的内容。

Answer 3

这个数组声明

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

Answer 4

是正确的。但是，我冒昧地对您的代码进行了一些修改，以遵循良好的编程习惯。

selection_sort 原型遗漏了 int 数组名称。

void selection_sort(int a[], int);

Varibale n 没有初始化（但这不是这里的问题）

int n = 0;

数组声明应该包含在第 n 个输入之后（这是问题所在）*。

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

int a[n];

最后，您没有考虑 slection_sort 函数中的空数组情况。

尽管在函数开头声明变量是一种很好的编程习惯，但在本例中您无法避免这样做，因为您是从标准输入获取数组大小。在解决此问题的第二种方法中，您应该尝试为 int 数组使用动态分配的内存。但是，如果您是 C 的新手或刚开始解决此类问题，那么这个程序就很好。

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

Error when calling function to sort array of n numbers

arrays

c

sorting

selection-sort

function-definition