一方向スキャンエクスプレス、双方向スキャンエクスプレスと非再帰エクスプレス
2178 ワード
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);
}
}
}
}
}