使用修改的快速排序從陣列中選擇k個最小元素的運行時錯誤

我嘗試了一種修改後的快速排序算法，以從數組中找到k個最小數字。但我得到一個運行時錯誤。我認爲這可能是因爲分段錯誤。我已經使用rand（）函數來選擇pivot元素，因此程序在最壞的情況下也能有效地工作。使用修改的快速排序從陣列中選擇k個最小元素的運行時錯誤

請幫助我

void swap(int &a,int &b){ 
    int temp=a; 
    a=b; 
    b=temp; 
} 
int partition(int arr[],int low,int high){ 
    int left,right,pivot; 
    int r=low+(rand()%(high-low+1)); 
    swap(arr[r],arr[low]); 
    pivot=arr[low]; 
    left=low; 
    right=high; 
    /*very imp: dont confuse between low,high and left,right 
    for traversing and swapping you need left and right*/ 
    while(left<right){ 
     while(arr[left]<=pivot) 
       left++; 
     while(arr[right]>pivot) 
       right--; 
     if(left<right) 
       swap(arr[left],arr[right]); 

    } 
    arr[low]=arr[right]; 
    arr[right]=pivot; 
    return right; 

} 
void quickselect(int arr[],int k){ 
    int low=0; 
    int high=sizeof(arr)/sizeof(int)-1; 
    int index=partition(arr,low,high); 
    while(index!=k-1){ 
     if(index>k-1){ 
      high=index-1; 
      index=partition(arr,low,high); 

     } 
     else{ 
      low=index+1; 
      index=partition(arr,low,high); 
     } 
    } 
    for(int i=0;i<k;i++) 
     cout<<arr[i]<<" "; 
} 
int main(){ 
    int arr[]={34,1,2,89,56,23}; 
    quickselect(arr,3); 

}

來源

2013-06-27 KenAdams

你應該檢查你的數組的邊界 – Regenschein

你知道錯誤發生的地方嗎？你有沒有在調試器中單步執行程序？另外請注意，使用'rand'來選擇主元並不能消除最壞的情況，而只是使它不太可能發生。 –

我quickselect()懷疑sizeof(arr)不返回數組的大小，但指針大小，並假設32位，將置高0，這可能會導致您的問題

來源

2013-06-27 14:35:24

非常感謝！這是問題！ – KenAdams

使用修改的快速排序從陣列中選擇k個最小元素的運行時錯誤

回答

相關問題