快速排序选首个大于相邻元素为基准的实现出现死循环排查

伪代码本身存在逻辑缺陷，同时你的C++实现也有额外的错误，两者共同导致了无限循环 #

1. 伪代码本身的逻辑问题 #

• findpivot的循环范围错误：伪代码中写的是for i=0 to j，实际应该是从传入的左边界i遍历到j-1，否则当i等于j时访问a[i+1]会出现数组越界。
• partition的执行顺序错误：进入循环后先执行swap(a[l],a[r])完全不符合快速排序分区逻辑，未筛选不符合条件的元素就直接交换左右指针位置的元素，会打乱数组顺序，也会导致分区边界计算错误。

2. C++实现额外的错误 #

• findpivot的循环边界错误：代码中写的是for(int i = l; i<=r; i++)，当i=r时访问arr[i+1]会越界，属于未定义行为。
• pivot值获取错误：你在partition的do循环内每次都读取arr[idx]作为pivot，但循环内的swap操作很可能已经改变了idx位置的元素，导致pivot值一直在动态变化，分区逻辑完全混乱。
• 递归边界死循环：当子数组为{11,19}时，分区返回的k=0，会导致递归反复调用Quicksort(0,1)，永远无法退出。

修复参考代码 #

修正后的findpivot

int findpivot(int l,int r,int arr[]){
    for(int i = l; i < r; i++){
        if(arr[i] > arr[i+1]){
            return i;
        } 
        else if(arr[i+1] > arr[i]){
            return i+1;
        }
    }
    return -1;
}

修正后的partition

int partition(int l, int r, int pivot, int arr[]){
    while(l <= r){
        while(arr[l] < pivot) l++;
        while(arr[r] >= pivot) r--;
        if(l <= r){
            swap(&arr[l], &arr[r]);
            l++;
            r--;
        }
    }
    return l;
}

修正后的快排递归逻辑

void Quicksort(int l, int r,int arr[]){
    int idx = findpivot(l,r,arr);
    if(idx!=-1){
        int pivot = arr[idx];
        int k = partition(l,r,pivot,arr);
        if(k > l) Quicksort(l,k-1,arr);
        if(k < r) Quicksort(k,r,arr);
    }
}

内容的提问来源于stack exchange，提问作者AxXxelWolf