歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

快速排序的遞歸方式和非遞歸方式

我們知道快遞排序大部分的版本都是遞歸的方式來實現的:通過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);
            }
        }

    }
   
}

從上面的代碼可以看出,保存中間變量的時候需要注意保存的順序,因為棧是後進先出的方式。

Copyright © Linux教程網 All Rights Reserved