2. 考研
  3. 写出快速排序的非递归算法。

写出快速排序的非递归算法。

admin2019-08-15  4
问题 写出快速排序的非递归算法。
选项
答案设对记录R[1．．n]进行快速排序，要求用非递归算法。利用一个包含有low和high两个整数成员的记录数组stack[ ]作为栈，low和high成员分别指示某个子文件的首、尾记录的下标号。算法如下： void quicksort(SeqList R，int n){ ／／设待排序记录放在R[1．．n]中，下标从1开始 int i，j，low，high，top=0； struct{ int low，high； }stack[Max]； ／／Max为一个大于n的常量 RecType temp； top=l；stack[top]．low=1；stack[top]．high=n：／／入栈 while(top＞0){ ／／栈非空，则取出一个子文件进行划分 low=stack[top]．low；high=stack[top]．high；top——； ／／出栈 i=low；j=high；temp=R[i]； do{ while(i＜j&&R[i]．key＞temp．key)j一一； if(i＜j){ R[i]=R[j]；i++； while(i＜j＆&R[i]．key＜temp．key)i++； if(i＜j){R[j]=R[i]；j一一；} } }while(i==j)； ／／划分结束 R[i]=temp； ／／基元元素插入 if(i+1＜high){ ／／右子文件有两个以上记录，则首、尾位置入栈 top++；stack[top]．low=i+l；stack[top]．high=high； } if(low＜i一1){ ／／左子文件有两个以上记录，则首、尾位置入栈 top++；stack[top]．low=low；stack[top]．high=i一1； } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/2KCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)