首页 文章

快速排序的递归如何工作？

提问于
浏览 次
-1

以下功能是快速排序的实现 . 这里我们将最后一个元素作为一个支点 .

我理解 partition 函数（其中枢轴到达其排序位置）但我无法理解递归函数 qs . 函数 qs 递归调用自身以通过 qs(a,start,pi-1) 解析左侧，并通过 qs(a,pi+1,end) 解析分区右侧 .

它解决了左边然后（左边的左边）然后（左边的左边）等，然后左边，左边......右边等等 . 或者通过解决左边来交替一边然后右边 .

PS：我想知道计算机内部发生了什么，这种快速排序的递归机制 . 该程序正在运行，但我想知道它是如何工作的 .

int partition(int *a, int start, int end)
{   
    int pivot=a[end];
    int pi=start;
    for(int i=start; i<end; i++)
    {
        if(a[i]<=pivot)
        {
            swap(a[i],a[pi]);
            pi++;
        }
    }
    swap(a[pi], a[end]);
    return pi;
}

void qs(int*a, int start, int end)
{
    if(start<end)
    {
        int pi=partition(a,start,end);
        qs(a,start,pi-1);
        qs(a,pi+1,end);
    }
}
algorithm sorting recursion quicksort divide-and-conquer

2 回答

  • 1

    Lomuto分区方案的操作顺序示例，其中pivot = array [high] .

    quicksort（array，low，pivot-1），quicksort（array，pivot 1，high） .

    用于显示左子阵列，枢轴，右子阵列的垂直条 .

    11 13 14 12 10  8  9  5  6  4  2  0  1  3  7
   5  6  4  2  0  1  3 11 13 14 12 10  8  9  7 
   5  6  4  2  0  1  3| 7|13 14 12 10  8  9 11
   2  0  1  5  6  4  3 
   2  0  1| 3| 6  4  5
   0  2  1 
   0| 1| 2
               4  6  5
               4| 5| 6
                          10  8  9 13 14 12 11
                          10  8  9|11|14 12 13
                           8 10  9
                           8| 9|10
                                      12 14 13
                                      12|13|14
   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
    回复于
  • 2

    理解我可以建议你发生事情的顺序的最好方法是在 qs 方法中打印一些调试信息 . 为了实现这一点，我将在ref中添加一个额外的参数，其中我将计算调用 qs 函数的次数，并在要解析的分区的边界旁边打印该信息 . 例如

    void qs(int*a, int start, int end, int &stepCount)
{
    if(start<end)
    {
        int currentStep = stepCount++;
        cout << "Solving step " << currentStep << " partition from " << start << " to " << end << endl;
        int pi=partition(a,start,end);
        qs(a,start,pi-1,stepCount);
        qs(a,pi+1,end,stepCount);
        cout << "Finished solving step " << currentStep << endl;
    }
}

    不明白你的PS问题 . 它非常广泛 . 你的意思是在分区中？在如何处理递归？这些位如何在内存中移动？

    回复于

相关问题