我們知道快遞排序大部分的版本都是遞歸的方式來實現的：通過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);
}
}
}
}
從上面的代碼可以看出，保存中間變量的時候需要注意保存的順序，因為棧是後進先出的方式。
