c++ - 在 C++ 中对 200 万个数字进行排序

Question

我正在尝试编写代码来比较 C++ 中排序算法之间的时间。当整数的数量为 100000 和 500000 时，我的代码完美运行。但是，当我将数字增加到 2000000 时，它崩溃了。谷歌搜索后，我试图通过声明一个数组将我的数字放入堆中:

int* array = new int[N];

我已经测试过，这个数组可以包含 200 万个整数，但是当我尝试将它们放入我的排序算法时，我的代码仍然崩溃。这是代码:

    #include <string>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <iostream>
    #include <fstream>
    #include <iomanip>

    #define N  2000000

 using namespace std;

void HeapDown(int a[] , int k, int N1) 
{ 
 int j; 
 int temp;
 while (2*k <= N1) 
 { 
  j = 2*k; 
  if (j < N1 && (a[j] < a[j+1])) j++; 
    if (!(a[k]<a[j])) break;  
    temp = a[k];
    a[k]=a[j];
    a[j]=temp;
  k = j ; 
 } 
} 

#define pq(A) a[l-1+A] 
void heapsort(int a[], int l, int r) 
{ 
 int temp;
  int k, N2 = r-l+1; 
 for (k = N2/2; k >= 1; k--) 
   HeapDown(&pq(0), k, N2); 
 while (N2 > 1) 
  { 

    temp = pq(1);
    pq(1)=pq(N2);
    pq(N2)=temp; 
    HeapDown(&pq(0), 1,--N2); 
  } 
  cout << "The sequence was sorted by heap sort" << endl; 
} 

int main(){

    int i;
    static int a[N];
    clock_t start;
    clock_t end;
    int* array = new int[N];

/* Generate random numbers and put them in the text file  */
//  ofstream myfile;
//      myfile.open ("2000000.txt");
//      
//  for (i=0; i < N; i++){
//      a[i] = 1000*(1.0*rand()/RAND_MAX);
//  //  printf("%3d ",a[i]);
//      myfile << a[i] << endl;
//      
//      }
//      cout << "done!" << endl;
//  myfile.close();
/*                                                      */


/******************* Open file and add the numbers into array **************************/   
    string line;
  ifstream myfile2 ("2000000.txt");
  if (myfile2.is_open())
  {
    i = 0;
    while ( getline (myfile2,line) )
    {
 //     a[i] = atoi(line.c_str());
        array[i] = atoi(line.c_str());
//      cout << a[i] << endl;
//          cout << line << '\n';
        i++;
    }
    myfile2.close();
  }

  else cout << "Unable to open file"; 
/*                                                                                      */  

//for (i=0; i< N; i++){
//      printf("%3d ",array[i]);
//  }

/* Chose the sorting algorithms and calculate the time */

    start = clock();

//  insertionSort(array, 0, N-1);
//  selectionSort(array, 0 , N-1);  
//  bubbleSort (array, N);
//  shellSort (array, N);
//  quicksort (array , 0, N-1);
//  usequicksort (array , 0, N-1);
    heapsort (array , 0 , N-1);
//  radixsort (array , N);

    end = clock();
    double rs = end - start;
    delete[] array;

// print out the sorted sequence and time consuming

//      printf("\n The sequence after sorted \n");  
    for (i=0; i< N; i++){
        printf("%3d ",a[i]);
    }

    cout << "Time consuming: " <<  rs << endl;

    return 0;
}

我认为问题出在我将数组放入排序函数时。不幸的是，我找不到解决方案。如果你们能帮助我，那就太好了，非常感谢

Answer 1

你的代码很好(没有检查算法 - 很好'崩溃明智'，除了一件事 -您不检查您的 new 是否成功。
正如@jonathan-potter 所说，如果您没有足够的内存，它会抛出异常。