C++使用Hoare变种快速排序时数组首元素被替换为数组长度问题

问题原因 #

• 首元素被覆盖为长度值的核心原因：main函数中存在多余的赋值操作*randomNumbers = initializeArray(randomNumbers, sizeOfArray);，initializeArray函数已经在内部完成了整个数组的元素赋值，同时该函数声明返回int但实际没有写return语句，属于未定义行为，你的编译器默认将传入的长度相关值作为返回值，赋值给了数组首地址*randomNumbers，直接覆盖了初始化好的第一个元素。
• 数组越界问题：所有遍历数组的循环（initializeArray、printArray内的循环）都用了i <= length的判断，若数组长度为length，合法索引范围是0 ~ length-1，i<=length会访问到数组外的内存，属于越界访问。
• 变量拼写与未定义问题：main函数中printArray(randomNumbers, sizeofArray);的sizeofArray是拼写错误，正确应为sizeOfArray；调用arrayClassification(randomNumbers, length);时length变量未定义，应该传入sizeOfArray；getArraySize中用到的ZERO宏未定义，会导致编译错误。
• 函数返回值不匹配问题：initializeArray不需要返回值，声明为int类型属于错误，应该改为void。
• 快速排序参数越界问题：当前quickSort传入的end参数为length，结合越界的循环判断会访问到数组外的内存，若调整数组索引判断为i < length，则quickSort的初始调用应该传入end = length -1。

修复方案 #

1. 删除main函数中initializeArray调用前的赋值操作，把*randomNumbers = initializeArray(randomNumbers, sizeOfArray);改为initializeArray(randomNumbers, sizeOfArray);
2. 修改initializeArray的返回值类型为void，同时调整循环条件：

// 函数声明改为
void initializeArray(int *array, int length);
// 函数定义改为
void initializeArray(int *array, int length)
{
    srand(time(nullptr));
    for(int i = 0; i < length; i++)
    {
        *(array + i) = 30 + rand() % 21;
    }
    cout<<"The array that was initialized is the one below."<<endl;
    printArray(array, length);
}

3. 修改printArray的循环条件：

void printArray(int *array, int length)
{
    for(int i = 0; i < length; i++)
    {
        cout<<*(array + i)<<" ";
    }
    cout<<endl;
}

4. 修复main函数中的变量错误：

int main()
{
    int sizeOfArray = getArraySize();
    int *randomNumbers = (int *)malloc(sizeOfArray *sizeof(int));
    initializeArray(randomNumbers, sizeOfArray);
    printArray(randomNumbers, sizeOfArray);
    arrayClassification(randomNumbers, sizeOfArray);
    free(randomNumbers);
    return 0;
}

5. 修复getArraySize函数：将ZERO替换为0即可，若需要输入n得到n个元素的数组，把return size-1改为return size。
6. 修复快速排序的初始调用参数，在arrayClassification中修改为：

quickSort(array, 0, length - 1);

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