c++ - 快速排序不适用于大型数组

Question

我正在尝试使用 Quicksort 和 Mergesort 对大型数组进行排序以评估性能。

我有一个问题:如果我在数组中加入大量元素，程序不会开始随机生成值。在下面的代码中，如果 N=500000，效果很好。如果 N > 500000，例如 1000000，则不起作用。对于 MergeSort，限制是 200000。我尝试了多种设备，Eclipse IDE 上的 C++。

有人知道如何解决这个问题吗？

#define N 800000
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <chrono>

using namespace std;

void Exchange(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int A[], int p, int r) {
     int x = A[r];
     int i = p - 1;
     for (int j = p; j <= r; j++) {
         if (A[j] < x) {
             i++;
             Exchange(&A[i], &A[j]);
         }

    }
    Exchange(&A[i + 1], &A[r]);
    return i + 1;
}

int RPartition(int A[], int p, int r) {
    srand(time(NULL));
    int i = p + rand() % (p - r);
    Exchange(&A[i], &A[r]);
    return Partition(A, p, r);
}

void QuickSort(int A[], int p, int r) {
    if (p < r) {
        int q = RPartition(A, p, r);
        QuickSort(A, p, q - 1);
        QuickSort(A, q + 1, r);
    }
}

void Stampa(int A[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << "\n";
    }
}

int main() {
    srand(50000);
    int A[N];
    for (int i = 0; i < N; i++) {
        A[i] = rand();
    }

    cout << "Array non ordinato\n";
    Stampa(A, N);
    auto start = std::chrono::system_clock::now();
    QuickSort(A, 0, N - 1);
    auto end = std::chrono::system_clock::now();
    cout << "\nArray ordinato\n";
    Stampa(A, N);
    std::chrono::duration<double> elapsed = end - start;
    cout << "Elapsed time: " << elapsed.count() << "s";
}

Answer 1

解释很简单:您将数组分配为具有自动存储功能的局部变量(又名在堆栈上)，因此如果大小太大，您会堆栈溢出.

您应该从堆中分配数组或将其定义为静态数据。

修改后的版本:

int main() {
    srand(time(NULL));

    int *A = new int[N];
    for (int i = 0; i < N; i++) {
        A[i] = rand();
    }

    cout << "Array non ordinato\n";
    Stampa(A, N);

    auto start = std::chrono::system_clock::now();
    QuickSort(A, 0, N - 1);
    auto end = std::chrono::system_clock::now();

    cout << "\nArray ordinato\n";
    Stampa(A, N);

    std::chrono::duration<double> elapsed = end - start;
    cout << "Elapsed time: " << elapsed.count() << "s";
    delete[] A;
}