c - 使用修改的快速排序从数组中选择 k 个最小元素时出现运行时错误

Question

我尝试了一种修改后的快速排序算法来从数组中查找 k 个最小数字。 但是我收到运行时错误。我认为这可能是因为段错误。我使用 rand() 函数来选择枢轴元素，因此程序在最坏的情况下也能高效工作。

请帮助我

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);

}

Answer 1

我怀疑 quickselect() 中的 sizeof(arr) 不返回数组大小，而是返回指针大小，并假设 32 位将高设置为 0，这可能会导致您的问题