1、写好划分函数(无论是否递归,这个函数都得有)
2、利用java中的stack对象存储划分的开始节点和结束节点,每次划分完存一次,再取出来划分。
利用stack完成递归的方法
public void nonRecrutQuickSort(int a[]){
if(a==null||a.length<=0)return;
Stack<Integer> index=new Stack<Integer>();
int start=0;
int end=a.length-1;
int pivotPos;
index.push(start); //存进去划分节点
index.push(end);
while(!index.isEmpty()){
end=index.pop(); //取出来
start=index.pop();
pivotPos=partition(a,start,end);
if(start<pivotPos-1){
index.push(start); //再存
index.push(pivotPos-1);
}
if(end>pivotPos+1){
index.push(pivotPos+1); //再存
index.push(end);
}
}
}
划分方法,体现了快排思想,把比标志位大的都放到一边,小的也放到另一边
public int partition(int[] a,int start,int end){//分块方法,在数组a中,对下标从start到end的数列进行划分
int pivot=a[start];
while(start<end){
while(start<end&&a[end]>=pivot) { //从末尾往前排查到第一个比pivot小的数
end--;
}
a[start]=a[end];
while(start<end&&a[start]<=pivot) {//从开头往后排查到第一个比pivot大的数
start++;
}
a[end]=a[start];
}
a[start]=pivot;
return start;//返回划分后的pivot的位置 ,这里start和end一定相等
}
分享到:
相关推荐
用java实现的栈Stack类,不继承任何集合类,用对象数组实现
使用java实现stack的源码与测试案例。
JAVA小程序 CharStack.java 包括push() pop() isEmpty() peek() isFull() RepOk()方程
自己写了一个Java的Stack类,并与原有的Stack比较
很好的一个示例程序,是一次作业,用explicit的方法来描绘一个java stack
一起学习java stack 的信息,如何查看
栈是先进先出的原则,该类实现了栈的移入移除
java数据结构 ArrayList、Stack、Map,为提高效率,未做边界判断(由开发人员保证逻辑上不会出现越界),实现了添加和查询的功能,无修改删除功能
继承的作用以及如何不用继承实现应该具有的功能
用java写的stack小程序
Generic Stack java 源码
C语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 STACKC语言头文件 ...
还有好多,不一一列举了:获取上面这份 Java 8~12 系列新特性干货文章,请在微信搜索关注微信公众号 "Java技术栈" 在后台回复 "java" 即可获取
Full Stack AngularJS for Java Developers 英文无水印原版pdf pdf所有页面使用FoxitReader、PDF-XChangeViewer、SumatraPDF和Firefox测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看...
java中堆(heap)和堆栈(stack)有什么区别
说明可能有些人还不明白:学 Java 到底该学什么?现在市面上都流行什么技术?...目录分类点击快速跳转分类文章:Java8StreamJava9Java10Java11Java12进阶后端技术SpringSpring MVCSpring BootSpring CloudMyBatisD
使用Java Stack实现的Web聊天机器人概念证明 该项目是标准的Maven项目,因此您可以将其导入到您选择的IDE中。 您需要安装Java 11+和Node.js 10+。 要从命令行运行,请使用./mvnw spring-boot:run并在浏览器中打开 ...
主要介绍了java 实现 stack详解的相关资料,需要的朋友可以参考下
JAVA Stack是栈。它的特性是:先进后出(FILO, First In Last Out)。
Full Stack AngularJS for Java Developers Build a Full-Featured Web Application from Scratch Using AngularJS with Spring RESTful