import java.util.Stack;
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int unsort[]={4,3,5,6,2,1},i;
quickSort3(unsort,0,5);
for(i=0;i<6;i++)
System.out.print(unsort[i]+",");
}
//单向扫描快排
static void quickSort(int p[],int left,int right){
int i,j,x,temp,k;
if(left<right){
i=left-1;
x=p[right];
for(j=left;j<right;j++){
if(p[j]<=x){
i++;
temp=p[i];p[i]=p[j];p[j]=temp;
}
}
temp=p[i+1];p[i+1]=x;p[right]=temp;
quickSort(p,left,i);
quickSort(p,i+2,right);
}
}
//双向扫描快排
static int partition(int p[],int left,int right){
int temp=p[left];
while(left<right){
while(left<right&&p[right]>=temp)
right--;
p[left]=p[right];
while(left<right&&p[left]<=temp)
left++;
p[right]=p[left];
}
p[left]=temp;
return left;
}
static void quickSort2(int p[],int left,int right){
int mid;
if(left<right){
mid=partition(p,left,right);
quickSort2(p,left,mid-1);
quickSort2(p,mid+1,right);
}
}
//非递归快排
static void quickSort3(int p[],int left,int right){
int mid;
Stack<Integer> stack=new Stack<Integer>();
if(left<right){
mid=partition(p,left,right);
if(left<mid-1){
stack.push(left);
stack.push(mid-1);
}
if(right>mid+1){
stack.push(mid+1);
stack.push(right);
}
while(!stack.empty()){
int high=stack.pop();
int low=stack.pop();
mid=partition(p,low,high);
if(low<mid-1){
stack.push(low);
stack.push(mid-1);
}
if(high>mid+1){
stack.push(mid+1);
stack.push(high);
}
}
}
}
}
分享到:
相关推荐
②:双向扫描法 单向扫描法 思路&过程 思路:用两个指针将数组分成成三部分,左边的扫描指针,右边在数组末尾再定义一个指针, 主元默认定义为数组的第一个元素,如果扫描指针指到的元素小于主元,那么元素的位置...
NULL 博文链接:https://z-jls03.iteye.com/blog/836195
双向认证和单向认证双向认证和单向认证
用递归实现单向链表从链尾向链首扫描,里面还比较的普通实现单向链表从链尾向链首扫描的过程。
晶闸管的种类很多,有单/双向晶闸管,可关断晶闸管,快速晶闸管,光控晶闸管等多种,而目前应用最多的就是单向晶闸管和双向晶闸管两种;常用的两种晶闸管到底有什么不同之处呢,下面来详细做一些对比说明: 1.单向...
基于pytorch从头实现了单向,多层,双向LSTM,给出了完整使用代码,并与torch自带的LSTM进行了对比实验。
常见的可控硅外形用符号如上图,内有单向和双向两种可控硅,你能区分出哪种是单向,哪种是双向吗? 具体区别: 引脚功能区别:单向可控硅缩写为SCR,双向可控硅英文缩写TRIAC。单向可控硅的引脚符号是K、G、A,...
本例程包括单向的链表的创建,递归、非递归的方法实现链表的逆置操作,从底层分析了链表逆置的过程,分析理解程序的关键在于理解指针是存放地址值的变量,对学习C/C++编程的同学有极大的帮组。
单向板双向板板筋识图.ppt
详解+实例 vue单向数据绑定,双向数据绑定.zip
1.航班管理员可以——添加航班——查询航班信息——修改航班信息——查询乘客信息(管理员登陆口令:123456) 2.乘客可以——查询航班信息——订票——退票 3.航班链表为单向顺序链表,乘客链表为双向非循环顺序链表
用java解决操作系统中的磁盘调度算法,包括了先来先服务法,最短寻到优先法以及电梯算法
以下是对使用递归和非递归方式反转单向链表的示例进行了详细的分析介绍,需要的朋友可以过来参考下
LSTM 的例子 单向LSTM 双向LSTM 多层LSTM(LSTM long short term memory
用单向链表存储航班信息,双向链表存储乘客信息,并可以订票,退票和查询的航班订票系统!
单向流程图表,双向流程图表,迂回流程图表,强调关系流程图表,6张彩色精美流程图示图表免费下载。
slist.h为单向链表,blist为双向链表
Intel的单向链表与双向链表,C语言源码,非常有参考价值
自动动同步备份 自动动同步备份 单向备份 双向备份 增量备份 单向备份 双向备份 增量备份
支持https单向认证和https双向认证