昆明网站建设 技术支持,涿州吧,蜘蛛网站长工作职责,社交网站的建设现状前言#xff1a; 上一期分析了快速排序的三种写法#xff0c;这三种写法有一个相同点#xff0c;都是采用递归形式来实现的#xff0c;那么有没有非递归的方法实现呢#xff1f;答案是当然有#xff0c;用非递归的方法实现快速排序#xff0c;其实可以借助数据结构中的栈…前言 上一期分析了快速排序的三种写法这三种写法有一个相同点都是采用递归形式来实现的那么有没有非递归的方法实现呢答案是当然有用非递归的方法实现快速排序其实可以借助数据结构中的栈来模拟实现递归的过程。
思路图分析: 因为使用c语言写的所以需要我们自己写一个栈栈的实现我这里不再过多赘述我会把栈的码放在最后。假如我们现在有下面这组数组我们要对它进行排序。注意下面的数字代表下标 好接下来开始用栈模拟递归图中栈中的数字均表示下标
1.第一次入栈 将整个数组入栈也就是下标为0-8
2.第一次出栈 每次出栈对出栈的下标区间进行一次部分排序这里的部分排序就是选出key将其放在正确的位置有3种实现方法如有不懂可以看我上一期博客这里我选的是双指针法。第一次出栈进行第一趟部分排序后数组的元素变为如下图 此时的key也就是45就被放在了正确的位置也就是左边的元素都比它小右边的元素都比它大。
然后再将key的左区间和右区间分别入栈也就是0-3和5-8 3.第二次出栈
根据栈的性质后入先出所以我们让5-8出栈 跟上面一样每次出栈对相应区间进行一次部分排序排序完如下图 因为在对这个区间进行部分排序时67被选为key此时67的右边已经全部比他大所以排完序后不变然后再将key的左区间和右区间分别入栈注意此时的左区间和右区间加起来应该是5-8因为我们是对5-8这个区间进行部分排序的而不是0-8左区间没有元素了也就是4-4右区间6-8注意这时候左区间就已经没有必要入栈了因为少于2个元素必定有序了只需将没排好序的右区间入栈即可
4.第二次入栈 然后只要栈不为空我们就出栈然后进行和上面一样的操作。
现在就不难感受出这其实是在模拟递归的过程。
5.第三次出栈 部分排序后如下图 跟上面同理左区间少于两个元素不必入栈右区间入栈7-8
6.第三次入栈 然后又是7-8出栈再判断是否入栈出栈判断是否入栈出栈判断是否入栈一直重复直到栈里面为空就排好了所以循环的使用在这里面也很重要下面来看一下全部代码吧
代码
#includestdio.h
#includeStack.hvoid Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}int PartSort3(int* a, int begin, int end)//双指针法
{int keyi begin;int prev begin;int cur begin 1;while (cur end){if (a[cur] a[keyi] prev ! a[cur]){Swap(a[cur], a[prev]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}void QuickSortNonR(int* a, int begin, int end)
{Stack s;StackInit(s);StackPush(s, end);StackPush(s, begin);//第一次入栈首尾下标while (!StackEmpty(s))//栈只要不为空就一直出栈判断是否入栈......{int left StackTop(s);StackPop(s);int right StackTop(s);StackPop(s);//出栈首元素下标放在left尾元素下标放在right很形象int keyi PartSort3(a, left, right);//进行一次部分排序并将最后key的下标返回//[left,keyi-1]keyi[keyi1,right]//拆分成的区间//下面为判断是否入栈if (left keyi - 1)//如果左区间元素个数不少于2{StackPush(s, keyi - 1);StackPush(s, left);//入栈}if (keyi 1 right)//如果右区间元素个数不少于2{StackPush(s, right);StackPush(s, keyi1);//入栈}}//循环结束栈为空排序完成StackDestroy(s);//销毁栈
}
栈的实现代码
#includeStack.h
void StackInit(Stack* ps)//初始化栈
{ps-a NULL;ps-top -1;ps-capacity 0;
}
void StackPush(Stack* ps, STDateType data)//入栈
{StackCheck(ps);ps-top;ps-a[ps-top] data;
}
void StackCheck(Stack* ps)//检查容量
{assert(ps);if(ps-top1ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a, sizeof(STDateType) * newcapacity);if (tmp NULL){perror(realloc);return;}else{ps-a tmp;ps-capacity newcapacity;}}
}
bool StackEmpty(Stack* ps)//判空函数
{return ps-top -1;
}
STDateType StackTop(Stack* ps)//获取栈顶元素
{assert(ps);assert(ps-top1 0);return ps-a[ps-top];
}
void StackPop(Stack* ps)//出栈
{assert(ps);ps-top--;
}
int StackSize(Stack* ps)//获取栈中有效元素的个数
{assert(ps);return ps-top1;
}
void StackDestroy(Stack* ps)//销毁栈
{assert(ps);free(ps-a);ps-a NULL;ps-top -1;ps-capacity 0;
}
栈的头文件
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
typedef int STDateType;
typedef struct Stack
{STDateType* a;int top;//栈顶int capacity;//容量
}Stack;
void StackInit(Stack* ps);//初始化栈
void StackCheck(Stack* ps);//检查容量
void StackPush(Stack* ps, STDateType data);//入栈
void StackPop(Stack* ps);//出栈
bool StackEmpty(Stack* ps);//判空函数
STDateType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素的个数
void StackDestroy(Stack* ps);//销毁栈
