package sort.quick;

import java.util.Random;

public class QuickSort3Ways {

//快速排序之三路排序
public  static   int[]   quickSort3Ways(int[]  arr,int n) {
	_quickSort3Ways(arr,0,n-1);
	return  arr;
}

private static void _quickSort3Ways(int[] arr, int min, int max) {
	int randomIndex=0;
	try {
		randomIndex = new Random().nextInt(max-min+1)+min;
	} catch (Exception e) {
		System.out.println("max="+max+",min="+min);
	}
	int   a  =arr[randomIndex];
	arr[randomIndex]=arr[min];
	arr[min]=a;
	
	int  v=arr[min];
	int  left=min,i=min+1,right=max+1;
	while(i<right) {
		//arr[i]余arr[left+1]互换位置，left++,i++
		if(arr[i]<v) {
			int  b=arr[i];
			arr[i]=arr[left+1];
			arr[left+1]=b;
			left++;
			i++;
			
		}else  if(arr[i]>v) {//arr[i]与 arr[right-1]互换位置,right--;
			int  c=arr[i];
			arr[i]=arr[right-1];
			arr[right-1]=c;
			right--;
		}else {
			i++;
		}
	}
//互换arr[min]与arr[left的位置]
	int d=arr[left];
	arr[left]=arr[min];
	arr[min]=d;
	_quickSort3Ways(arr, min, left-1);
	_quickSort3Ways(arr, right, max);
}
//生成随机数组
public static  int[]  generateRandomArray(int num,int min ,int  max) {
	int[]  arr=new int[num];
	for(int i=0;i<=num-1;i++) {
		arr[i]=new Random().nextInt(max-min)+min;
	}
	return  arr;
}

//生成随机数组
public static  void  printArray(int[] arr) {
	for(int i=0;i<=arr.length-1;i++) {
		System.out.print(arr[i]+"  ");
	}
}
public static void main(String[] args) {
int[]  arr=generateRandomArray(200, 1, 100);
int n=arr.length;
arr=quickSort3Ways(arr, n);
printArray(arr);
}

}