排序系列（二）--快速排序

 

//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