c - C : only works on first 10000 integers 中的归并排序

Question

我正在学习 Coursera 类(class)，我得到了一个包含 100,000 个整数的文件，要使用合并排序对其进行排序。现在，我的函数恰好适用于前 1000 个整数，但出于某种原因，一旦我达到 10000+，它就会停止工作。是的，我根据要测试的整数数量修改了顶部的 #define。我打算使用我在网上找到的另一个实现，但为什么我的代码不起作用？我想我遗漏了一些非常明显的东西。

哦，对于家庭作业，我需要交出排序所需的反转次数(想象一下冒泡排序，需要将较早/较小的数字移到较晚/较大的数字后面多少次) .因此，全局变量。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define fileLineNumber 1000

void MergeSortL1 ( int arrayIn[], int arraySize );
int inversionCounter = 0;

int main (int argc, const char * argv[])
{
 // Declarations. Whee. Typical counter variable, i, arrayInOrder for boolean logic, a char for the file read type... and the array of so many bits...
 int array[fileLineNumber];
 int i, temp;
 FILE *fp;
 char* filePath = "/Users/TMC/Code/algorithmsCoursera/lesson1/IntegerArray.txt";
 char arrayInOrder = 1, fileOpenType;
 // Here, open a file.
 fileOpenType = 'r';
 fp = fopen( filePath, &fileOpenType);
 // Here, read into an array.
 for ( i = 0; i < fileLineNumber; i ++)
 {
  fscanf(fp,"%d", &temp);
  array[i] = temp;
 }
 fclose(fp);
 MergeSortL1(array, sizeof(array)/sizeof(int*));
 // Maybe check if it is in order.....
 for ( i = 0; i < fileLineNumber - 1; i++)
 {
  if ( array[i] > array[i+1] )
  {
   arrayInOrder = 0;
  }
 }
 /* Shorter, harder to read, have a 2 dimension array, a[2][4]. a[0] == " not" a[1] == ""      *
  * Just would need to printf ( "Array is%s in order.\n", a[arrayInOrder] ); Hard to maintian. */
 printf ("Array is" );
 if ( !arrayInOrder )
 {
  printf ( " not" );
 }
 printf (" in order.\n");
 printf ( "Inversion Counter says: %d\n\n", inversionCounter );
 // Write back to the file.
 fileOpenType = 'w';
 fp = fopen( filePath, &fileOpenType);
 for ( i = 0; i < fileLineNumber; i ++)
 {
  fprintf(fp, "%d", array[i]);
  fputc( '\n', fp );
 }
 fclose ( fp );
 return 0;
}

void MergeSortL1 ( int arrayIn[], int arraySize ) // Arrays are a pointer, so we don't need to capture a return...
{
    printf ( "------------------\nIn MergeSortL1, arraySize = %d\n------------------\n", arraySize );
    if ( arraySize <= 1 ) // Base Case.
    {
     printf ( "Base Case: Returning\n" );
     return;
    }
    else
    {
     int i = 0; // Counter variable
     char loopStillValid = 1, a1HasMore = 1, a2HasMore = 1;
     int temp1 = 0, temp2 = 0;
     int lenArray1 = ( floor(arraySize/2.0) ); // floor() and ceil() are just here in case we have an odd number of variables.
     int lenArray2 = ( ceil(arraySize/2.0) );
     int* array1 = malloc ( lenArray1 * sizeof (int) );
     int* array2 = malloc ( lenArray2 * sizeof (int) );
     for ( i = 0; i < lenArray1; i ++ ) // Assign values.
     {
      array1 [i] = arrayIn[i];
     }
     for ( i = 0; i < lenArray2; i ++ )
     {
      array2 [i] = arrayIn[i+lenArray1];
     }
     MergeSortL1 ( array1, lenArray1 );
     MergeSortL1 ( array2, lenArray2 );
     a1HasMore = lenArray1;
     a2HasMore = lenArray2;
     temp1 = 0;
     temp2 = 0;
     for ( i = 0; i < arraySize; i++)
     {
      loopStillValid = a2HasMore && a1HasMore;
      if ( loopStillValid && (array1[temp1] <= array2[temp2] ) )
      {
       arrayIn[i] = array1[temp1];
       temp1++;
      }
      else if ( loopStillValid && (array1[temp1] > array2[temp2] ) )
      {
       arrayIn[i] = array2[temp2];
       temp2++;
       inversionCounter ++;
      }
      else if (a2HasMore && !a1HasMore /*&& (array1[temp1] <= array2[temp2] )*/)
      {
       arrayIn[i] = array2[temp2];
       temp2++;
      }
      else if (!a2HasMore && a1HasMore /*&& (array1[temp1] > array2[temp2] )*/)
      {
       arrayIn[i] = array1[temp1];
       temp1 ++;
      }
      else
      {
       printf ("\n--------------\nERROR: UNCAUGHT STATUS\ni = %d\narray1[%d] = %d\narray2[%d] = %d\na1HasMore = %d\na2HasMore = %d\n--------------\n\n", i, temp1, array1[temp1], temp2, array2[temp2], a1HasMore, a2HasMore );
      }
      if ( temp1 >= a1HasMore )
      {
       temp1 --;
       a1HasMore = 0;
      }
      if ( temp2 >= a2HasMore )
      {
       temp2 --;
       a2HasMore = 0;
      }
     }
     free(array1);
     free(array2);
    }
}

Answer 1

您的数组正在堆栈上分配，堆栈大小有限制。您需要在堆上分配大型数组。您可以在 c 语言中使用 malloc 执行此操作。