快速排序的递归方式和非递归方式
递归的方式显现如下:
首先贴出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
while (i < j&&a[i] <= priot)
i++;
if(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 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);
}
}
}
}
从上面的代码可以看出,保存中间变量的时候需要注意保存的顺序,因为栈是后进先出的方式。