使用递归快速排序分而治之算法时，如何对枢轴的右侧进行分区？

Question

我有以下问题，我正在尝试实现快速排序算法中的第一个分区步骤，我只需要使用 fastSortDivide 函数的两个参数（数组和大小）。我已经能够对数组的左侧进行排序并返回递归调用的枢轴索引。但是，我的问题是，在枢轴的右侧，我无法对该分区进行排序，因为我无法从返回的索引中找到最右边的墙。我希望这是有道理的，请找到下面的代码：

void quickSort(int arr[], int size) {


    if (size > 1) {
        
        int index = quickSortDivide(arr, size);
        std::cout << "in recursion:  " <<index <<endl;
        quickSort(arr, index-1);
        quickSort(arr, index +1);
        
    }
 

}



int quickSortDivide(int* arr, int size)
{
    

    int pivot = arr[size - 1], current, index = 0;
    cout << " piv: " << pivot <<  endl;

    for (int i = index; i < size; i++)
    {

        if (arr[i] > pivot) {
            for (int j = i; j < size; j++)
            {

                if (arr[j] < pivot) {
                   
                    index = i;
                    swapInArray(arr, i, j);

                }
            }
        }
 
    }
    swapInArray(arr, index + 1, size-1 );
    
    return index;
}

输出：

before function call { 14, 3, 1, 9, 7, 45, 10};


after function call: {1 3 7 9 10 45 14}

Answer 1

有多种方法可以处理这些参数，但我建议这样做：

int index = quickSortDivide(arr, size);
std::cout << "in recursion:  " << index <<endl;
quickSort(arr, index++);
quickSort(arr + index, size - index));

后增量跳过枢轴位置，第二个递归在该跳过之后重新设置“数组”起始地址的基址，将段大小减小为余数此后的部分。

注意：我仍然在您的实现中发现至少还有一个错误，但这需要您去发现。