堆棧溢出錯誤

Question

我有這個功能，確實遞歸選擇排序的數組：

void SelectionSort::RecursiveSort(int ar[] , int flag, int first, int last){ 
    // first - index of first element and last - index of last element 
    if (flag == 1) 
    { 
     if (first < last)    //ascending 
     { 
      for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]); 

      RecursiveSort(ar, flag, first + 1, last); 
     } 
     if (first == last) return; 

    } 
    else 
    { 
     if (first < last)     //desc 
     { 
      for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]); 

      RecursiveSort(ar,flag, (first + 1), last); 
     } 
     if (first == last) return; 

    } 
} 

它工作正常，如果數組大小是3000，但我應該做這項工作的大小> 5000它崩潰給堆棧溢出。

我搜索了很多線程，他們都告訴使用矢量，我有。這是一個賦值問題，所以我應該對數組和向量進行遞歸排序。它爲矢量工作，但不適用於數組。另外我不應該在這個任務中使用指針。

Answer 1

你可以嘗試用尾遞歸，所以編譯器會優化它作爲循環給你：

void AscRecursiveSort(int ar[], int first, int last) { 
    if (first >= last) return; 
    for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]); 
    AscRecursiveSort(ar, first + 1, last); 

} 

void DescRecursiveSort(int ar[], int first, int last) { 
    if (first >= last) return; 
    for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]); 
    DescRecursiveSort(ar, first + 1, last); 
} 

void RecursiveSort(int ar[], int flag, int first, int last) { 
    // first - index of first element and last - index of last element 
    if (flag == 1) 
     AscRecursiveSort(ar, first, last);    //ascending 
    else 
     DescRecursiveSort(ar, first, last); 
} 

Answer 2

如果你的編譯器不優化尾遞歸，該解決方案將無法正常工作，你將需要重寫作爲檢查基本情況的while循環。沒有發佈完整的解決方案，因爲這看起來像功課。