分治法－クイックソート

package divideConquer;

import java.util.Arrays;
/*
 * 		QuickSort Complexity is nlog(n)
 * 		1.select one of a number as benchmark,then find the benchmark's absolute position
 * 		2.with the benchmark seperate array to two part
 * 		3.use the way like 1
 * 
 * */
public class QuickSort {
	
	public static int partion(int data[],int low,int high)
	{
		int i=low,j=high-1;
		while(i<j)
		{
			while(data[j]>=data[i]&&i<j)
				j--;
			if(i<j) {swap(data,i++,j);}
			
			while(data[i]<=data[j]&&i<j)
				i++;
			if(i<j) {swap(data,i,j--);}
		}
		return i;
	}
	public static void swap(int data[],int i,int j)
	{
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	public static void quickSort(int data[],int low,int high)
	{
		if(low+1>=high)
			return ;
		int s = partion(data,low,high);
		quickSort(data,low,s+1);
		quickSort(data,s+1,high);
	}
	public static void main(String args[])
	{
		int data[] = {9,5,1,2,6,3,4,3};
		quickSort(data,0,data.length);
		System.out.println(Arrays.toString(data));
	}
}