sorting - 我们可以通过尾递归优化随机快速排序吗？

Question

我知道我们可以通过删除超过 1 个递归调用并将其减少到一次单个递归调用来利用尾递归来优化快速排序：-

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
 
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void quickSort(int arr[], int low, int high)
{
start:
    if (low < high)
    {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
 
        low = pi+1;
        high = high;
        goto start;
    }
}

但是我们可以用尾递归优化随机快速排序吗？

Answer 1

尾栈递归侧重于优化递归调用。随机快速排序和普通快速排序之间的唯一区别是在随机快速排序的情况下选择随机枢轴的分区函数。请注意，此分区函数是非递归的。由于随机快速排序和普通快速排序的递归部分是相同的，因此在这两种情况下都可以进行相同的优化。所以，是的。