使用while循环实现QuickSort的split函数时触发Runtime error

你的快速排序代码出现**堆缓冲区溢出（heap-buffer-overflow）**的核心原因是split函数中的两个内层while循环没有添加索引边界检查，导致循环无限制执行，最终访问了数组范围外的内存地址。

具体问题点 #

在split函数的内层循环中：

• 第一个循环while(nums[start] < base);没有限制start的上限（比如start <= end），当数组中所有元素都小于等于基准值base时，start会持续递增，直到超出数组的最大索引upper，触发越界访问。
• 第二个循环while(nums[end] > base);没有限制end的下限（比如end >= start），当数组中所有元素都大于等于基准值base时，end会持续递减，直到低于数组的最小索引lower，同样触发越界。
• 第一个循环的判断条件nums[start] < base会跳过等于基准值的元素，结合无边界检查的逻辑，更容易导致越界。

修复后的代码 #

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        cout << "Running Code" << endl;
        int lower = 0;
        int upper = nums.size() - 1;
        quicksort(lower, upper, nums);
        return nums;
    }

    void quicksort(int lower, int upper, vector<int>& nums )
    {
        if(lower < upper)
        {
            int index = split(lower, upper, nums);
            cout << index << endl;
            quicksort(lower, index-1, nums);
            quicksort(index+1, upper, nums);
        }
    }

    int split(int lower, int upper, vector<int>& nums)
    {
        int base = nums[lower];
        int start = lower;
        int end = upper;

        printf("start: %d end: %d\n", start, end);
        
        while(start < end)
        {
            // 添加start <= end边界，同时修改为<=base，跳过等于基准的元素
            while(start <= end && nums[start] <= base)
                start++;
          
            // 添加end >= start边界，跳过大于基准的元素
            while(end >= start && nums[end] > base)
                end--;

            if(start < end)
                swap(nums[start], nums[end]);
        }

        swap(nums[lower], nums[end]);
        return end;
    }
};

关键修改说明 #

1. 第一个内层while循环：
   • 添加start <= end的边界检查，确保start不会超出当前分区的范围
   • 将判断条件改为nums[start] <= base，跳过所有小于等于基准值的元素，直到找到第一个大于基准值的元素
2. 第二个内层while循环：
   • 添加end >= start的边界检查，确保end不会低于当前分区的范围
   • 保持nums[end] > base的判断，跳过所有大于基准值的元素，直到找到第一个小于等于基准值的元素
3. 移除了原代码中while循环后的空语句（单独的分号），将循环体改为包含递增/递减操作，逻辑更清晰。

这些修改可以确保循环始终在当前分区的索引范围内执行，避免越界访问内存，同时保证快速排序的分区逻辑正确运行。

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