Quicksort引起堆棧溢出？

這是我實現快速排序的：Quicksort引起堆棧溢出？

int choosePivotIndex(int l, int r) 
{ 
    return l + rand() % (r + 1 - l); 
} 

void swap(int a[], int l, int r) 
{ 
    int tmp = a[l]; 
    a[l] = a[r]; 
    a[r] = tmp; 
} 

int partition(int a[], int l, int r) 
{ 
    int p = choosePivotIndex(l, r); 
    swap(a, p, r); 
    int d = l; 
    for (int i = l ; i < r ; ++i) 
    { 
     if (a[i] < a[r]) 
     { 
      swap(a, i, d); 
      ++d; 
     } 
    } 
    swap(a, d, r); 
    return d; 
} 

void quickSort(int a[], int l, int r) 
{ 
    if (l < r) 
    { 
     int p = partition(a, l, r); 
     quickSort(a, l, p - 1); 
     quickSort(a, p + 1, r); 
    } 
} 

void quickSort(int a[], int len) 
{ 
    srand(static_cast<unsigned int>(time(nullptr))); 

    quickSort(a, 0, len - 1); 
}

我用它像這樣：

int a[10]; 
quickSort(a, 10);

它似乎做工精細的小型陣列，但是當我給它提供一個大的（如300 000元素）我得到一個堆棧溢出錯誤。我試圖通過使用只在小部分遞歸和排序在while循環更大一個補救：

void quickSort(int a[], int l, int r) 
{ 
    while (l < r) 
    { 
     int p = partition(a, l, r); 
     if (p - l < r - p) 
     { 
      quickSort(a, l, p - 1); 
      l = p + 1; 
     } 
     else 
     { 
      quickSort(a, p + 1, r); 
      r = p - 1; 
     } 
    } 
}

，但我得到了相同的結果。我做錯了什麼？我如何才能使它適用於更大的陣列？

來源

2017-10-05 NPS

來在堆上聲明它們：較大陣列的內存是堆棧還是堆？ –

看來你是通過值傳遞數組，而不是通過引用。我不確定這是否是由設計決定的，但是具有30萬個元素的陣列，您將很快耗盡堆棧空間。 – Baldy

@Baldy，你不能通過值傳遞c數組，a []參數總是與相應的指針相同... –

按照評價的討論部分中的代碼看起來是良好和有問題的部分將是堆

int a[10];

如果是這種細爲較小的陣列在陣列的聲明其容易跑到大數組的堆棧溢出，爲了測試這個，你可以聲明一大堆int a[1000000]，如果沒有快速排序代碼，你仍然會得到堆棧溢出。因此，建議通過執行new

來源

2017-10-05 15:55:58

Quicksort引起堆棧溢出？

回答

相關問題