快速排序非递归
栈溢出：递归多少层，建立多少个栈
栈不够，会溢出（深度太深）
非递归：循环
有些地方可以用队列，有些不能（二叉树）
所以要用栈，数组在堆上，数组指针不变，递归变的是区间，栈也存于区间。
快速排序非递归：每次单趟排完把子区间入栈。
所以我们要借助栈来实现非递归。
思路：
1.栈里面取一段区间，单趟排序；
2.单趟分割子区间入栈；
3.子区间只有一个值或不存在就不入栈。
下面我们来看一下代码：
先看栈的部分：
头文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//#define N 10
//struct Stack
//{
//int a[N];
//int top;
//};
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);//访问栈顶元素
中间部分：用Stack.c来写
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
perror("malloc fail");
return;
}
ps->capacity = 4;
ps->top = 0;//top栈顶元素的下一个位置
//ps->top = -1;//top是栈顶元素位置
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//扩容
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity*2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
STDataType STTop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
return ps->a[ps->top - 1];
}
快排部分：用Sort来写：
//非递归
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st,right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end= STTop(&st);
STPop(&st);
int keyi = PartSort2(a, begin, end);
//[begin,keyi-1],keyi,[keyi+1,end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi+1);
}
if (begin < keyi)
{
STPush(&st, keyi-1);
STPush(&st, begin);
}
}
STDestroy(&st);
}主函数main部分：
void TestQuickSort()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
PrintArray(a, sizeof(a) / sizeof(int));
QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);
PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
TestQuickSort();
return 0;
}以上就是快速排序非递归的全部代码啦！
原文地址：https://blog.csdn.net/2401_86415114/article/details/142733897
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！