快速排序实现问题排查：我的代码存在哪些错误？

存在的错误点： #

• 分区函数循环逻辑错误：
  你把swap(arr[j], arr[low])和return j写在了while(i<j)的循环体内部，这会导致循环刚执行一次就直接交换并返回，完全没完成整个分区过程，基准元素根本没法放到正确位置。必须把这两行移到while循环外面，等i和j交叉后再执行。

• 数组越界风险：
  内层的两个while循环缺少边界检查：

  • 找大于pivot的i时，没限制i <= high，如果数组中所有元素都小于等于pivot，i会一直递增到超出数组范围，触发越界错误。
  • 找小于等于pivot的j时，没限制j >= low，如果数组中所有元素都大于pivot，j会一直递减到小于0，同样触发越界。

• 递归函数冗余判断：
  QuickSort里已经有if(low >= high ) return;处理递归终止条件，后面的if(high>low)完全多余，直接执行分区和递归即可。

修正后的完整代码： #

#include<iostream>
using namespace std;

int partition(int arr[], int low, int high){
    int pivot = arr[low];
    int i = low + 1;
    int j = high;

    // 改为i<=j，确保所有元素都被遍历判断
    while (i <= j)  
    {
        // 增加i<=high的边界判断，防止越界
        while(i <= high && arr[i] <= pivot) i++;
        // 增加j>=low的边界判断，防止越界
        while(j >= low && arr[j] > pivot) j--;
        if(i < j) {
            swap(arr[i], arr[j]);
        }
    }
    // 交换基准元素到正确位置，放在循环外执行
    swap(arr[j], arr[low]);
    return j;
}

void QuickSort(int arr[], int low , int high){
    if(low >= high ) return;
    // 去掉冗余判断，直接执行分区与递归
    int pivotindx = partition(arr, low, high);
    QuickSort(arr, low, pivotindx - 1);
    QuickSort(arr, pivotindx + 1, high);
}

void printquicksort(int arr[] , int n){
    cout << " Quick SORT IS HERE BROOOO " << endl; 
    for (int i = 0; i < n; i++)
    {
        cout << " " << arr[i] << " " ;
    }
}

int main()
{
    int arr []={3,4,5,1};
    int n= sizeof (arr)/ sizeof (arr[0]);

    QuickSort(arr,0,n-1);
    printquicksort(arr,n);
    
    return 0;
}

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