c++ - 没有尾递归的快速排序

Question

我使用尾递归编写了以下随机快速排序代码。我想看看不使用尾递归的效果，想看看执行时间和运行时间是如何受到影响的。我们如何从下面的随机快速排序代码中删除尾递归？

#include<iostream>
#include<cstdlib>
using namespace std;

int partition(int low,int high,int a[])
{
    int index=(rand()%(high-low))+low;
    //cout<<endl<<index<<"----"<<endl;
    int temp1=a[index];
    a[index]=a[low];
    a[low]=temp1;
    int left,right,pivot_item=a[low];
    left=low;
    right=high;

    while(left<right)
    {
        while(a[left]<=pivot_item)
            left++;
        while(a[right]>pivot_item)
            right--;
        if(left<right)
        {
            int temp=a[right];
            a[right]=a[left];
            a[left]=temp;
        }
    }
    a[low]=a[right];
    a[right]=pivot_item;
    return right;
}

void quicksort(int low,int high,int a[])
{
    int pivot;
    if(low<high)
    {
        pivot=partition(low,high,a);
        quicksort(low,pivot-1,a);
        quicksort(pivot+1,high,a);
    }
}

int main()
{
    srand(time(NULL));
    int n;
    n=50;
    int a[n];
    int i;
    for(i=0;i<n;i++)
        a[i]=(rand()%(1000-1));

    quicksort(0,n-1,a);
    cout<<endl;

    for(i=0;i<n;i++)
        cout<<a[i]<<endl;
    return 0;
}

编辑:有什么方法可以完全删除 quicksort 函数中的第二个递归调用。这将意味着移除尾递归并且还会显着影响时间。

Answer 1

消除尾递归的一个简单方法是在进行递归调用后在函数中执行其他操作。下面我将函数更改为返回一个值而不是 void，并添加了一个 return 语句以在递归调用完成后 rturn 一些东西。这对性能的影响应该很小。

int quicksort(int low,int high,int a[])
{
    int pivot;
    if(low<high)
    {
        pivot=partition(low,high,a);
        quicksort(low,pivot-1,a);
        quicksort(pivot+1,high,a);
    }
    return 0;
}