免费网站下载大全,网站建设公司调查报告,wordpress影音,兰州小的网络公司快速排序的非递归
我们写快速排序的时候#xff0c;通常用的递归的方法实现快速排序#xff0c;那么有没有非递归的方法实现快速排序呢#xff1f;肯定是有的。思想还是一样的#xff0c;不过非递归是看似是非递归其实还是递归。
思路解释
快速排序的非递归使用的是栈这…快速排序的非递归
我们写快速排序的时候通常用的递归的方法实现快速排序那么有没有非递归的方法实现快速排序呢肯定是有的。思想还是一样的不过非递归是看似是非递归其实还是递归。
思路解释
快速排序的非递归使用的是栈这个数据结构。我们知道栈是后入先出和先入后出的所以我们可以通过栈的方式模拟递归然后实现快速排序的非递归。 如图所示创建一个栈。然后首先先将数组的起始和末尾的下标存进栈中然后让leftbeginrightend并pop出去。然后进行一次快排找到keyi。此时如果keyi两边的区间绿色的存在就把keyi也存进栈。然后进行一次快排当区间为空或者区间值有序就把值从栈中pop出来如果不是就继续push进去直到栈为空。最后别忘了把栈给销毁。
代码 int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}
int PSort(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key begin;int prev begin;int cur prev 1;while (cur end){if (a[cur] a[key] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[key], a[prev]);key prev;return key;
}
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(s);STPush(s, end);STPush(s, begin);while (!STEmpty(s)){int left STTop(s);STPop(s);int right STTop(s);STPop(s);int keyi PSort(a, left, right);// [left, keyi-1] keyi [keyi1, right]if (left keyi - 1){STPush(s, keyi - 1);STPush(s, left);}if (keyi 1 right){STPush(s, right);STPush(s, keyi 1);}}STDestroy(s);
}下面是栈的头文件和.c文件
#include stdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
typedef struct Stack
{int* a;int top; // 标识栈顶位置的int capacity;
}ST;
void STInit(ST* pst);//初始化栈
void STDestroy(ST* pst);//栈的销毁
void STPush(ST* pst, int x);//栈顶插入
void STPop(ST* pst);//栈顶删除
int STTop(ST* pst);//获取栈顶元素
bool STEmpty(ST* pst);//检查栈是否为空
int STSize(ST* pst);//获取栈中元素的个数
#include stack.h
void STInit(ST* pst)
{/*ST* tmp (ST*)malloc(sizeof(ST));if (tmp NULL){perror(malloc);return;}*/pst-a NULL;pst-top -1;pst-capacity 0;
}
void STPush(ST* pst, int x)
{assert(pst);if (pst-top pst-capacity - 1){int newcapacite pst-capacity 0 ? 4 : pst-capacity * 2;int* tmp (int*)realloc(pst-a, newcapacite * sizeof(int));if (tmp NULL){perror(realloc);return;}pst-a tmp;pst-capacity newcapacite;}pst-a[pst-top 1] x;pst-top;
}
void STPop(ST* pst)
{assert(pst);pst-top--;
}
int STTop(ST* pst)
{assert(pst);if (pst-top -1){printf(此栈为空);return 1;}return pst-a[pst-top];
}
bool STEmpty(ST* pst)
{assert(pst);return pst-top -1;
}
int STSize(ST* pst)
{assert(pst);return pst-top;
}
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity 0;pst-top -1;}
