quicksort.java

用java写的

package oop;

public class QuickSort implements Sort {
	
	private QuickSort(){};

	public void sort(int[] array) {
		// TODO Auto-generated method stub
		quickSort(array,0,array.length-1);

	}
	
	private void quickSort(int[] array,int i,int j){
        int pivotIndex=(i+j)/2;
        //swap
        Swap.swap(array,pivotIndex,j);
        
        int k=partition(array,i-1,j,array[j]);
        Swap.swap(array,k,j);
        if((k-i)>1) quickSort(array,i,k-1);
        if((j-k)>1) quickSort(array,k+1,j);
        
    }
   
    private int partition(int[] array, int l, int r,int pivot) {
        do{
           while(array[++l]<pivot);
           while((r!=0)&&array[--r]>pivot);
           Swap.swap(array,l,r);
        }
        while(l<r);
        Swap.swap(array,l,r);        
        return l;
    }
    
    public static Sort getInstance(){//Singleton 最多只产生一个QuickSort实例
		if (ins==null)
			return new QuickSort();
		else
			return ins;
	}
	
	private static Sort ins=null;

}