建设网站关键词怎么写,263企业邮箱官方入口,wordpress网站静态化,图文生成器快速排序是非常适合使用递归的#xff0c;但是同时我们也要掌握非递归的算法
因为操作系统的栈空间很小#xff0c;如果递归的深度太深#xff0c;容易造成栈溢出
递归改非递归一般有两种改法#xff1a;
改循环借助栈#xff08;数据结构#xff09;
图示算法 不是…快速排序是非常适合使用递归的但是同时我们也要掌握非递归的算法
因为操作系统的栈空间很小如果递归的深度太深容易造成栈溢出
递归改非递归一般有两种改法
改循环借助栈数据结构
图示算法 不是递归我们模拟递归的过程
代码示例
创建一个栈s先入end再入begin先出左再出右
然后找这个区间的keyi找到之后左区间就是[left,keyi-1]右区间就是[keyi1,right]
如果区间不止一个值那就继续入栈单趟排序入栈的顺序应与前面保持一致
stack
stack.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int STDataType;
typedef struct Stack
{int* a;int top;//标识栈顶位置int capacity;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Stack.h
//初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType * )realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst - a[pst-top - 1];
}
//判空
bool STEmpty(ST* pst)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/return pst-top 0;
}
//栈的元素个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}
QuickSortNonR
#define _CRT_SECURE_NO_WARNINGS 1
#includeStack.h
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}elsebreak;}a[end 1] tmp;}
}
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[end] a[begin])return begin;elsereturn end;}
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int keyi begin;int prev begin, cur begin 1;while (cur end){//if (a[cur] a[keyi])//{// prev;// Swap(a[prev], a[cur]);// cur;//}//else// cur;if (a[cur] a[keyi] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[keyi], a[prev]);keyi prev;return keyi;
}
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 PartSort3(a, left, 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);
}
递归相当于把这些数据存到栈帧里边而非递归是将核心区间存存到数据结构栈里面
快速排序的特性总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定
