ソート・シリーズ(2)--クイック・ソート

//author:lilywangcn
public class QuickSort {
	private static int[] array=new int[]{10,30,20,4,9,-1,6,10,20,4,10,15};
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		print();
		quicksort(0,array.length-1);
		print();
	}
	
	private static void quicksort(int left, int right){
		if(left>=right) return;
		int i=left;
		int j=right+1;
		int key=array[left];
		while(true){
			do{
				i++;
			}while(i<=right&&array[i]<key);
			
			do{
				j--;
			}while(j>=left&&array[j]>key);
			if(j<i) break;
			System.out.println("exchange i="+i+",j="+j);
			int tmp=array[i];
			array[i]=array[j];
			array[j]=tmp;

		}
		System.out.println("exchange left="+left+",j="+j);
		int tmp=array[left];
		array[left]=array[j];
		array[j]=tmp;
		quicksort(left,j-1);
		quicksort(j+1,right);

		
	}
	
	private static void print(){
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println("");
	}
}

アルゴリズム複雑度:O(nlogn),アルゴリズム不安定.
実行結果:
 
10 30 20 4 9 -1 6 10 20 4 10 15 
exchange i=1,j=10
exchange i=2,j=9
exchange i=7,j=7
exchange left=0,j=6
exchange i=1,j=5
exchange left=0,j=3
exchange i=2,j=2
exchange left=0,j=1
exchange left=4,j=4
exchange left=7,j=7
exchange i=9,j=11
exchange left=8,j=9
exchange left=10,j=11
-1 4 4 6 9 10 10 10 15 20 20 30