使用類的C++中的快速排序錯誤

我在C++中使用類和對象進行了快速排序的程序。我已經編譯在線編譯器，發現它是超時，因爲這段代碼需要太多的時間和內存。使用類的C++中的快速排序錯誤

當我以後在Visual C++ 2010上編譯它時，它說unhandled exception : stack overflow 我試圖找出在類成員函數void quick sort (a[],l,r)上運行的無限循環。請幫忙。

#include <iostream> 
using namespace std; 

class sort; 

int main() 
{ 
    class sort 
    { 
    public: 
     int split(int a[],int l,int r) 
     { 
      int i,j,p,t; 
      p=a[l]; 
      i=(l+1); 
      j=r; 

      while (l<=r) 
      { 
       while ((a[i]<p)&&(i<j)) 
        r--; 

       while ((a[j]>p)&&(l<r)) 
        l++; 

       if (i<=j) 
       { 
        t=a[i]; 
        a[i]=a[j]; 
        a[j]=t; 
       } 
      } 
      t=p; 
      p=a[j]; 
      a[j]=p; 

      return j; 
     } 


     void quicksort(int a[],int l,int r) 
     { 
      int s; 
      if (l<r) 
      { 
       s=split(a,l,r); 
       quicksort(a,l,(s-1)); 
       quicksort(a,(s+1),l); 
      } 
     } 

    } obj1; 

    int a[30],n,i; 

    cout<<"\nEnter no of elements :\t 5"; 
    n=5; 

    cout<<"\nEnter elements :\n"; 
    a[0]=9; 
    a[1]=6; 
    a[2]=3; 
    a[3]=5; 
    a[4]=1; 

    cout<<"\nElemets before sort :\n"; 
    for(i=0;i<n;i++) 
     cout<<" "<<a[i]; 

    obj1.quicksort(a,0,(n-1)); 

    cout<<"\nElements after sort:\n"; 
    for (i=0;i<n;i++) 
     cout<<" "<<a[i]; 

    return 0; 
}

來源

2013-10-27 lapita

在VC調試器中運行它，它會指向您拋出異常的位置。這應該讓你開始發現錯誤。 – Adam

在調試器中運行它，在發生堆棧溢出時調查堆棧跟蹤 –

並請正確縮進代碼。我正在掃描它，看看是否有東西跳出來，但我厭倦了試圖搭配大括號。如果你不能寫清楚，我不會困擾你試圖幫助你。 – Adam

這裏有幾個問題：

int split(int a[],int l,int r) 
{ 
    int i,j,p,t; 
    p=a[l]; 
    i=(l+1); 
    j=r; 

    // consider what will happen for an array with just 1 or 2 elements? 
    while (l<=r) // should be while i<=j; 
    { 
     while ((a[i]<p)&&(i<j)) 
      r--; //should be j-- 

     while ((a[j]>p)&&(l<r)) 
      l++; // should be i++ 

     if (i<=j) // sadly this will only true when you've got an array with 1 element 
     { 
      t=a[i]; 
      a[i]=a[j]; 
      a[j]=t; 
     } 
    } 
    t=p; 
    p=a[j]; 
    a[j]=p; 

    return j; 
}

的關鍵問題是，快速排序算法是不正確這裏。它的工作原理如下：

0. make i = l+1 and j = r; 

1. while true: 

1.1 while a[i]<a[l] i++ 

1.2 while a[j]>a[l] j-- 

1.3 break if i>= j; 

1.4 exchange a[i] and a[j] 

2. exchange a[l] and a[j]

您在執行過程中正在做不同的事情。

來源

2013-10-27 07:34:08 Ashalynd

使用類的C++中的快速排序錯誤

回答

相關問題