使用修改的快速排序从阵列中选择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个最小元素的运行时错误

回答

相关问题