【数据结构】快速排序——非递归实现快速排序

一、为什么要用非递归方式实现快速排序

内存中分了几个区用于存储数据
栈区比较小，堆区比较大
我们在递归时是在栈区开辟空间
所以当递归深度过深时会有栈溢出的风险
有时在某些特定情况下我们担心会栈溢出
所以采用非递归的方式
就是我们自己建立一个栈
来模拟函数在栈上递归的过程
因为我们自己创立的栈在堆区
所以空间会大很多，就减小的栈溢出的风险

下面是自己建立栈的方式
点这里

二、代码实现

我们将原数组的区间入栈
可以先左后右，也可以先右后左
在取出时按照我们放进去的顺序取出就行

//快速排序(非递归)
void QuickSortNonRST(int* a, int left, int right)
{
//用栈来模拟递归(深度优先遍历)

//建立栈
ST st;
STInit(&st);

//将左右区间入栈，先入左边
STPush(&st, left);
STPush(&st, right);

//排序，栈不空不停止
while (!STEmpty(&st))
{
//将栈中元素出栈,并将左右区间保存
int end1 = STTop(&st);
int end = end1;
STPop(&st);
int begin1 = STTop(&st);
int begin = begin1;
STPop(&st);


//三数取中
int key = The_Mid(a, begin, end);
Swap(&a[key], &a[left]);
key = left;

//单次排序
while (begin < end)
{
//右边找大
while (begin < end && a[end] >= a[key])
{
end--;
}

//左边找小
while (begin < end && a[begin] <= a[key])
{
begin++;
}
Swap(&a[begin], &a[end]);
}

//将key位置数与相遇位置数进行交换
Swap(&a[key], &a[begin]);
key = begin;

//将左右两部分入栈
// [begin1, key - 1] key [key + 1, end1]

//当只有一个数不用排的情况不入栈
//左
if (begin1 < (key - 1))
{
STPush(&st, begin1);
STPush(&st, key - 1);
}
//右
if (key + 1 < end1)
{
STPush(&st, key + 1);
STPush(&st, end1);
}
}
}

我们自己建立的栈也有好处，当只有一个数时，我们就不入栈

原文地址：https://blog.csdn.net/2302_79968411/article/details/143717510

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！