网站建设与设计试题,专业设计企业logo,石家庄语音网站建设公司,网站内外链怎么做概述
递归实现快速排序在一些场景下有栈溢出的风险#xff0c;下面就谈谈如何用非递归的方法实现快速排序。
非递归实现的思想
递归实现与非递归实现快速排序的本质是一致的#xff0c;效率并不会因为用了非递归实现而有所提升。递归实现快速排序的本质就在于通过递归下面就谈谈如何用非递归的方法实现快速排序。
非递归实现的思想
递归实现与非递归实现快速排序的本质是一致的效率并不会因为用了非递归实现而有所提升。递归实现快速排序的本质就在于通过递归可以对不同长度的子数组进行快速排序例如第一次调用时处理的区间是[0,9]第二次调用时处理的区间是[0,4]……借助栈也可以实现递归的本质功能——分割数组对子数组进行快速排序。
非递归过程展开图 代码 void QuickSortNonR(int* a, int begin, int end)
{ST st;//创建栈STInit(st);//初始化栈STPush(st, end);//插入数据STPush(st, begin);//插入数据while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int keyi PartSort(a, left, right);//判断区间是否为空或只有一个值if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}//判断区间是否为空或只有一个值if (left keyi - 1){STPush(st, keyi - 1);STPush(st, left);}}
}
