package com.xsz.demo;/**    * @author cwqi   * @date 2015-1-6   *///排序之快速排序，基本思路為分治+挖坑，方法有兩種：一是雙邊掃面；二是單邊掃描。public class QuickSort {	public static void main (String[] args){		int a[] ={2,3,30,1,4,56,2,7,3,8};		//int a[] ={4,5,6,2,7,3,8};		//int a[] ={1,5,4,3,8};		//int a[] ={1,1};		//int a[] ={1};		//int a[] ={};		//int a[] =null;		int start=0;		int end= a==null? -1:a.length -1;		//singleScan(a,start,end);		doubleScan(a,start,end);		print(a,end);	}	static void doubleScan(int[] a, int start, int end) {		 if(start < end){  		        int i = start, j = end, key = a[start];  		        while(i < j){  		        	//從後面往前找比key值小的元素		            while( i < j && a[j] >= key){  		                j--;  		            }  		            if(i < j){  		                a[i++] = a[j];  		            }  		            		            //從前面往後找比key值大的元素		            while(i < j && a[i] <= key){  		                i++;  		            }  		            if(i < j){  		                a[j--] = a[i];  		            }  		        }  		        		        a[i] = key;  //i為分區中心		        doubleScan(a, start, i-1);  		        doubleScan(a, i+1, end);  		    }   	}	static void singleScan(int[] a, int s, int e) {		int j = s+1;//遍歷下標		int p = s;//分區位置		if (s < e) {			int key =a[s];//key值			while (j<=e){				if(a[j] <= key){					p++ ;					//System.out.println("key->"+key);					int temp =a[p];					a[p] = a[j];					a[j]=temp;					//System.out.println("交換----->"+a[j]+" "+a[p]);					j++ ;				}else {					j++ ;				}			}						//將key值放在分區位置			int temp =a[s];			a[s] = a[p];			a[p]=temp;						singleScan(a, s, p-1);			singleScan(a, p+1, e);		}	}		static void print(int[]array ,int l){		for (int i = 0; i <= l; i++) {			System.out.print(array[i]+" ");		}	}}