快速排序的递归方式和非递归方式

我们知道快递排序大部分的版本都是递归的方式来实现的:通过Pritation来实现划分,并递归实现前后的划分。由于同学上次百度二面面试官问起快速排序的非递归的实现方式,当时同学不会,因为我们大部分看到的都是递归方式来实现快速排序。并没有关注非递归的方式。但是仔细想想也是可以做的,因为递归的本质是栈,因此我们非递归实现的过程中,借助栈来保存中间变量就可以实现非递归了。在这里中间变量也就是通过Pritation函数划分之后分成左右两部分的首尾指针,只需要保存这两部分的首尾指针即可。

递归的方式显现如下:

首先贴出Pritation函数的实现,因为递归和非递归都需要用到该函数,该函数实现的版本有多种,这里采用我比较熟悉的。

int Pritation(int* a, int left, int right)
{
    if (a == NULL || left < 0 || right <= 0||left>=right)
        return -1;
    int priot = a[left];
    int i = left, j = right;
    while (i < j)
    {
        while (i > j&&a[j] >= priot)
            j--;
        if(i<j)
            a[i]=a[j];
        while (i < j&&a[i] <= priot)
            i++;
        if(i<j)
            a[j]=a[i];
    }
    a[i] = priot;
    return i;
}

然后贴出递归的代码:(代码简洁明了)

void QuickSort(int *a, int left,int right)
{
    if (a == NULL || left < 0 || right <= 0 || left>right)
        return;
    int k = Pritation(a, i, j);
    //下面是递归实现的代码
    if (k > left)
        QuickSort(a, left, k - 1);
    if (k < right)
        QuickSort(a, k + 1, right);
}

最后贴出非递归的实现方式:

void QuickSort(int *a, int left,int right)
{
    if (a == NULL || left < 0 || right <= 0 || left>right)
        return;
    stack<int>temp;
    int i, j;
    //(注意保存顺序)先将初始状态的左右指针压栈
    temp.push(right);//先存右指针
    temp.push(left);//再存左指针
    while (!temp.empty())
    {
        i = temp.top();//先弹出左指针
        temp.pop();
        j = temp.top();//再弹出右指针
        temp.pop();
        if (i < j)
        {
            int k = Pritation(a, i, j);
            if (k > i)
            {
                temp.push(k - 1);//保存中间变量
                temp.push(i);  //保存中间变量
            }
            if (j > k)
            {
                temp.push(j);
                temp.push(k + 1);
            }
        }

}
   
}

从上面的代码可以看出,保存中间变量的时候需要注意保存的顺序,因为栈是后进先出的方式。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/7d7a36526be5365483abe9bdd94ff0b9.html