고전 정렬 알고리즘 자바 구현

package xl.com;

public class Sort {	
	/**
	 *      ：
	 * 
	 * 1.    ：               ，           ，            。                     ，        
	 * 			            ，              。                          ，            ，       。
	 * 			                             。  T(n)。 
	 * 2.     ：            ，n       ， n     ，    T(n)      。                  。  ，      
	 * 				       。      ，                   n     ， T(n)  ，        f(n),   n       ，
	 * 				 T（n)/f(n)            ，  f(n) T(n)       。  T(n)=O(f(n)), O(f(n))            ，       。 
	 */
	
	/**
	 *      ：
	 * 
	 * 		           ，          (Space Complexity)S(n)              ，
	 * 		       n   。     (Space Complexity)                         。                    ，
	 * 		                ，                                        。
	 * 		                            ，                ，            。
	 * 		                         ，           ，           。
	 * 		                         ，                  ，              ，
	 * 		        “  /"   ，        ，                ；                        n  ，
	 * 		   n      ， n   ，          ，                            。
	 */
	
	/**
	 *     
	 *     ：                        ，       
	 *      ：O(n2)
	 *    ：  
	 * @param data
	 * @return
	 */
	public void insertSort(int[] data){
		for(int index=1;index<data.length;index++){
			int currPosition;
			currPosition=index;
			int key=data[index];
			while(currPosition>0&&data[currPosition-1]>key){
				data[currPosition]=data[currPosition-1];
				currPosition--;
			}
			data[currPosition]=key;
		}
	}
	
	/**
	 *     
	 *     ：            ，      ，               
	 *      ：O(n2)
	 *    ：  
	 * @param data
	 */
	public void bubbleSort(int[] data){
		for(int i=data.length-1;i>1;i--){
			for(int j=0;j<i;j++){
				if(data[j]>data[j+1]){
					int temp=data[j];
					data[j]=data[j+1];
					data[j+1]=temp;
				}
			}
		}
	}
	
	/**
	 *     
	 *     ：                        。           
	 *      ：O(n2)
	 *    ：  
	 * @param data
	 */
	public void selectSort(int[] data){
		for(int i=0;i<data.length-1;i++){
			int min=i;
			for(int j=i;j<data.length-1;j++){// data[j,data.length-1]  data[j]      
				if(data[j]<data[min]){
					min=j;
				}
			}
			if(min!=i){
				int temp=data[i];
				data[i]=data[min];
				data[min]=temp;
			}
		}
	}
	
	/**
	 *     
	 *     ：                  ，           ，         。     
	 *      ：O(nlogn)
	 *    ：   
	 * @param data
	 * @param start
	 * @param end
	 */
	public void quickSort(int[] data,int low,int high){		
        if(low<high){ 
            int middle = getMiddle(data,low,high);
            quickSort(data, 0, middle-1);
            quickSort(data, middle+1, high);
        }
	}

	private static int getMiddle(int[] data, int low, int high) {
        int temp = data[low];//    
        while(low<high){
            //             
            while(low<high && data[high]>=temp){
                high--;
            }
            data[low] = data[high]; 
            while(low<high && data[low]<=temp){
                low++;
            }
            data[high] = data[low];
        }
        data[low] = temp;
        return low;
	}
	
	/**
	 *     
	 *     ：           ，        ，     。
	 *      ：O(nlogn) 
     *    ：   
	 * @param data
	 * @param left
	 * @param right
	 */
	public void mergeSort(int[] data,int low,int high){
		int mid=(high+low)/2;
		if(low<high){
			mergeSort(data,low,mid);
			mergeSort(data,mid+1,high);
			merge(data,low,mid,high);
		}
	}
	public void merge(int[] data,int low,int mid,int high){//  
		int[] temp=new int[high-low+1];               //         
		int i=low;//   
		int j=mid+1;//   
		int k=0;
		while(i<=mid&&j<=high){
			if(data[i]<=data[j]){                   //            
				temp[k++]=data[i++];
			}else{
				temp[k++]=data[j++];
			}                                  //k          
		}
		while(i<=mid){                                 //                  
			temp[k++]=data[i++];
		}
		while(j<=high){                                  //                  
			temp[k++]=data[j++];
		}
		for(int s=0;s<temp.length;s++){                      //            
			data[s+low]=temp[s];
		}
	}
	
	/**
	 *     
	 *     ：                。         gap ，            .   gap     1
	 *      ：   gap  ，   O(nlogn)
	 *    ：   
	 * @param data
	 */
	public void shellSort(int[] data){
		int size = data.length;  
	    for(int gap = size/2; gap>=1; gap /= 2) {  
	        for(int i=gap; i<size; i++) {  
	            int k;  
	            int temp = data[i];  
	            for(k = i-gap; k>=0 && data[k] > temp; k -= gap) {  
	                data[k+gap] = data[k];  
	            }  
	            data[k+gap] = temp;  
	        }  
	    }  
	}  
	/*************************************************************************************/
	/**
	 *       
	 * @param data
	 */
	public void showAfter(int[] data){
		String result="";
		for(int index=0;index<data.length;index++){
			result+=data[index];
			result+=",";
		}
		System.out.println("   :"+result);
	}
	public void showBefore(int[] data){
		String result="";
		for(int index=0;index<data.length;index++){
			result+=data[index];
			result+=",";
		}
		System.out.println("   :"+result);
	}
	/**
	 *   
	 * @param args
	 */
	public static void main(String[] args){
		Sort sort=new Sort();
		int[] dbl={8,1,2,5,4,3,9,6,4,4,4,8,9,99,77,55,66,3,5,12,12};
		sort.showBefore(dbl);
//		sort.insertSort(dbl);
//		sort.bubbleSort(dbl);
//		sort.selectSort(dbl);
//		sort.quickSort(dbl, 0, dbl.length-1);
//		sort.mergeSort(dbl, 0, dbl.length-1);
		sort.shellSort(dbl);
		sort.showAfter(dbl);
		
	}
}