C语言 排序大整数时递归选择排序错误 11

Question

我必须使用递归选择排序才能对不同的整数数组进行排序.
这些数组分别由 100、1000、10000、100000、200000、500000 个项目组成，可以由有序数、部分有序数、倒序数和随机数组成。 之后，我必须计算算法对数组进行排序所花费的时间。

我必须使用递归，这是一个家庭作业。

我创建了一个生成数组的函数：

typedef enum {ORINATO, INVERS, PARZ_ORDINATO, RANDOM} Ordine;
int *generaArray(int dimensione, Ordine ordine) {
int i, j, n;
int *array = (int*)malloc(dimensione * sizeof(int));
if (!array){
return NULL;
}
switch (ordine){
case ORINATO:
for (i = 0; i < dimensione; i++){
array[i] = i;  
} break;
case INVERS:
n =0;
for ( i = dimensione-1; i >= 0 ; i--) {
array[i] = n;
n++;
}break;
case PARZ_ORDINATO:
for (i = 0; i < dimensione/2 ; i++) {
array[i] = i;
}
for (j = i+1; j <dimensione; j++){
n = rand();
array[j] = n;
};break;
case RANDOM:
for ( i = 0; i <= dimensione ; i++) {
array[i] = rand();
}break;

default:
break;
}
return array;
}

它像奇迹一样工作.
然后我创建了递归选择排序，如下所示：

void recursiveSelectionSort(int *array, int dim, int start){
int min=0;
if (start >= dim-1){
return;
}
min = findMin(array, start, start+1, dim);
swap(&array[min], &array[start]);
recursiveSelectionSort(array, dim, start+1);
}
int findMin(int *array, int min, int start, int dim){
if(start == dim ){
return min;
}
if (array[start]< array[min]){
min = start;
}
return findMin(array, min, start+1, dim);
}
void swap (int* x, int *y){
int temp = *x;
x =  *y;
y = *temp;
}

现在，这也应该有效，但显然不是。让我们用实现做一个例子，这是我放在我的主语中的内容：

int main() {
int *array;

clock_t start, end;
double t;
array = generaArray(1000, ORINATO);
start = clock();
recursiveSelectionSort(array, 1000, 0);
end = clock();
t = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("nIl tempo impiegato per 1000 elementi è: %lf secondi", t);
return 0;
}

这有效(但它更慢，谢谢它应该是(。但是，如果您尝试将维度从 1000 更改为 200000 或 500000，则会显示错误 11。

是什么原因造成的？我尝试了所有方法，但似乎不起作用。

Answer 1

对于初学者来说，为大型数组调用的递归函数可以调用堆栈溢出。

因此，请使用非递归函数来实现大型数组的方法选择排序。

至于您的实现，例如函数swap有拼写错误。

void swap (int* x, int *y){
int temp = *x;
x =  *y;
y = *temp;
}

我想你的意思是

void swap (int* x, int *y){
int temp = *x;
*x =  *y;
*y = temp;
}

所有其他函数都有太多参数。

例如，函数findMin可以通过以下方式声明

size_t findMin( const int *a, size_t n );

也可以定义为递归函数(如果你决定编写递归函数，那么这个函数也可以是递归的(

这是一个演示程序，展示了如何定义函数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap( int *x, int *y )
{
int temp = *x;
*x =  *y;
*y = temp;
}
size_t findMin( const int a[], size_t n )
{
if ( n < 2 )
{
return 0;
}
else
{
size_t i = findMin( a + 1, n - 1 ) + 1;
return a[i] < a[0] ? i : 0;
}
}
void recursiveSelectionSort( int a[], size_t n )
{
if ( !( n < 2 ) )
{
size_t i = findMin( a + 1, n - 1 ) + 1;

if ( a[i] < a[0] ) swap( &a[0], &a[i] );

recursiveSelectionSort( a + 1, n - 1 );
}
}
int main(void) 
{
enum { N = 15 };
int a[N];

srand( ( unsigned int )time( NULL ) );

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

recursiveSelectionSort( a, N );

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

程序输出可能如下所示

11 9 3 5 6 8 2 4 5 3 7 9 2 0 14 
0 2 2 3 3 4 5 5 6 7 8 9 9 11 14