首页 > 代码库 > 快排的非递归算法和最大子串乘积
快排的非递归算法和最大子串乘积
快排的原理是，让一个数作为中间值A，使得左边的数都小于(大于)等于A，右边的数都大于(小于)A。
1 public static void quickSort(Integer[] arrayList,int begin,int end){2 if(begin>=end)3 return;4 int par=paration3(arrayList, begin, end);5 if(begin<par-1)6 quickSort(arrayList, begin, par-1);7 if (par<end) 8 quickSort(arrayList, par+1, end);9 }
public static int paration(Integer[] arrayList,int begin,int end){ int temp=arrayList[begin]; while (begin<end) { while (begin<end&&arrayList[end]>temp) { end--; } if (begin<end) { arrayList[begin]=arrayList[end]; begin++; } while (begin<end&&arrayList[begin]<temp) { begin++; } if (begin<end) { arrayList[end]=arrayList[begin]; end--; } } arrayList[begin]=temp; return begin; }
一般来说，递归算法都可以用非递归来实现，添加一个栈， 保存相关信息即可。快速排序的非递归算法亦是如此，每次保存下下次需要排序的。
public static void quickSort2(Integer[] arrayList,int begin,int end){ int par=paration3(arrayList, begin, end); Stack<Integer> stack=new Stack<Integer>(); if(begin>par-1){ stack.push(begin); stack.push(par-1); } if(par+1<end){ stack.push(par+1); stack.push(end); } while (!stack.empty()) { end=stack.pop(); begin=stack.pop(); par=paration3(arrayList, begin, end); if(begin<par-1){ stack.push(begin); stack.push(par-1); } if(par+1<end){ stack.push(par+1); stack.push(end); } } }
快排的非递归算法和最大子串乘积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。