湖南做网站最厉害的公司,企业网站开发视频,黄页网站建设,台州自助建站目录
1.引入 2.非递归实现快排的思想
3.非递归实现快排图解
4.完整代码 1.引入 递归不可避免的话题就是防止栈溢出 所以程序员需要具备递归改非递归的能力 #xff0c;一般来说#xff0c;抓住递归中变化的量是关键 void QuickSort(int* a, int left, int right){if (left…目录
1.引入 2.非递归实现快排的思想
3.非递归实现快排图解
4.完整代码 1.引入 递归不可避免的话题就是防止栈溢出 所以程序员需要具备递归改非递归的能力 一般来说抓住递归中变化的量是关键 void QuickSort(int* a, int left, int right){if (left right)return;if (right - left 1 10){InsertSort(a left, right - left 1);}else{int keyi PartSort1(a, left, right);//[left, keyi - 1] keyi [keyi 1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}
} 递归调用实现快速排序类似于二叉树的前序遍历(根、左子树、右子树) 仔细观察可知栈帧中变化的是具体的区间边界 2.非递归实现快排的思想 配合使用栈这种结构以模拟递归实现快排时的前序遍历 先将起始区间边界存入栈中然后取出边界进行快排的单趟排序得到分界位置的下标以此为界将数组分割为左右两部分然后先将右部分的区间边界存入栈中再将左部分的区间边界存入栈中(区间大小大于1才将边界存入栈中)再从栈中取出区间边界进行单趟排序再分割数组并存入区间边界....直到栈为空为止 简单来说就是存边界、取边界排序、分数组存边界、取边界排序、分数组存边界....... 3.非递归实现快排图解 依据思想 存边界、取边界排序、分数组存边界、取边界排序、分数组存边界....... 直到栈为空时停止此时数组有序 4.完整代码
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 val);
//出栈
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//访问栈顶
STDataType STTop(ST* ps);void QuickSortNonR(int* a, int left, int right){//区间不存在就返回if (left right)return;//小规模数组直接优化if (right - left 1 10){InsertSort(a left, right - left 1);return;}//C语言实现的栈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);//小规模数组直接优化if (end - begin 1 10){InsertSort(a begin, end - begin 1);continue;}int keyi PartSort3(a, begin, end);//[begin, keyi - 1] keyi [keyi 1, end]if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}}STDestroy(st);
}注意边界的存入方式 、小规模数组可以进行优化
