quicksort - 快速排序算法的堆缓冲区溢出错误

Question

我为快速排序算法编写了以下代码。我在第一次快速排序调用后收到堆缓冲区溢出警告，但我无法弄清楚原因。

输入是数字：{5, 2, 3, 1}

错误是：

==================================================== ================30==错误：AddressSanitizer：地址 0x6020000000a0 上的堆缓冲区溢出在 pc 0x000000344bbc bp 0x7ffcc3526f20 sp 0x7ffcc3526f18 在 0x6020000007a0 线程 T701000000a0 处读取大小 4 47 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 0x6020000000a0 位于 16 字节区域 [0x602000000090,0x6020000000a0) 右侧的 0 字节处，由线程 T0 分配：#6 0x7fc6707d10b2 (/lib/x86_64 -linux-gnu/libc.so.6+0x270b2) 错误地址周围的影子字节： 0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000C047FFF7FE0：00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00乘fd fa fa fa fd fa fa fa fd fa =>0x0c047fff8010: 发发 00 00[发]发发发发发发发发发发发发发发 0x0c047fff8020:发发发发发发发发发发发发发发发发发发发发发发 0x0c047fff8030发发发发发发发发发发fa fa fa fa fa 0x0c047fff8040：fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8050：fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8060 fa fa fa fa fa fa fa fa fa fa 影子字节图例（一个影子字节代表 8 个应用程序字节）： 可寻址：00 部分可寻址：01 02 03 04 05 06 07 堆左 redzone：fa 已释放堆区域：fd 堆栈左 redzone： f1 堆栈中间 redzone：f2 堆栈右 redzone：f3 返回后堆栈：f5 范围后堆栈使用：f8 全局 redzone：f9 全局初始化顺序：f6 用户中毒：f7 容器溢出：fc 数组 cookie：ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==30==ABORTING

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        int a=0, length;
        length = nums.size();
        
        quicksort(nums, a, length-1);
        
        return nums;  
        
    }
    
    void quicksort(vector<int>& nums, int low, int high)
    {
        if(low<high)
        {
            int pt = 0;
            pt = partition(nums,low,high);
            quicksort(nums, low, pt-1);
            quicksort(nums, pt+1, high);
        }
    }
    
    int partition(vector<int>& nums, int low, int high)
    {
        int pt = 0, pivot = nums[high];
        int i = low-1;
        for(int j=0;j<high;j++)
        {
            if(nums[j]<=pivot)
            {
                i++;
                swap(&nums[i],&nums[j]);
            }
        }
        swap(&nums[i+1],&nums[high]);
        return i+1;
    }
    
    void swap(int* a, int* b)
    {
        int t;
        t = *a;
        *a = *b;
        *b = t;
    }
};

标签： quicksortheap-corruption