Java 排序算法

package com.kneel.core.utils;

/**
 * sort is the time:space.
 * 
 * 1. if you want speed, then you need more space, you can use multiple threads to process multiple parts at one time.
 * 2. if you have limit space, then you can process a part of it one by one.
 * 
 * there is no best sort, just have fit of your business logic sort.
 * 
 * @author e557400
 *
 */
public class SortUtils {

	/**
	 * bubble up
	 * 
	 * 1. compare with current value and next value.
	 * 2. if current value big then next value, change position.
	 * 
	 * Example: i need to compare with (n-1), and put the min Number to header
	 *          i+1 need to compare with (n-2), and put the second min Number to header.
	 *          ...
	 *          n-2 need to compare with 1, and put the last min Number to header.
	 *          
	 * 
	 * NOTE:  compare(n*(n-1)/2), no move.
	 *        compare(n*(n-1)/2), every compare need to move, move(n*(n-1)/2)
	 *       
	 *  time:  O(n~2)  bad situation
	 *  space: O(1) 
	 *  
	 * every time sort should be load all datas to memory.
	 *  
	 *  Exp
	 *o. 	60--38--15--75--51--
	 *1. 	38--60--15--75--51--
	 *2. 	15--60--38--75--51--
	 *3. 	15--38--60--75--51--
	 *4. 	15--38--51--75--60--
	 *5. 	15--38--51--60--75--
	 * @param x
	 * @return
	 */
	public static <T extends Comparable<T>> void bubbleUp(T[] array,boolean ascend) {
		for (int i = 0; i < array.length; i++) { 
			for (int j = i + 1; j < array.length; j++) { 
				 int compare = array[i].compareTo(array[j]); 
				if (compare != 0 && compare>0 ==ascend) {
					T temp = array[j];
					array[j] = array[i];
					array[i] = temp;  
				}
			} 
		}
	}
	
	/**
	 * Select up
	 * 
	 * this sort is the upgrade of bubble up, i agree.
	 * 
	 * 1. iterator array, i is the index of the sort, find the min of [i...n-1], then change position of the i.
	 * 2. case of every iterator will be choose min process, so call it select sort.
	 * 
	 * NOTE:  compare(n*(n-1)/2), no move.
	 *        compare(n*(n-1)/2), every compare need to move, move(n)
	 *  
	 *  
	 * Exp
	 *o. 	60--38--15--75--51--
	 *1. 	15--38--60--75--51--
	 *2. 	15--38--60--75--51--
	 *3. 	15--38--51--75--60--
	 *4. 	15--38--51--60--75--
	 *5. 	15--38--51--60--75-
	 * 
	 * @param array
	 */
	public static <T extends Comparable<T>> void selectUp(T[] array,boolean ascend) {
		 int len = array.length;
	     for (int i = 0; i < len; i++) {  
	    	 int selected = i;  
	    	 for (int j = i + 1; j < len; j++) {  
	    		 int compare = array[selected].compareTo(array[j]);  
	    		 if (compare != 0 && compare > 0 ==ascend) {  
	    			 selected = j;  
	    		 }  
	    	 }  
	    	 T temp = array[selected];
	    	 array[selected] = array[i];
	    	 array[i] = temp;
	        }
	}
	
	/**
	 * Insert Up
	 * 
	 * almost element is sorted
	 * 
	 * 1. we set index i 's left is sorted, to find the i the index.
	 * 2. we will be compare i's left's data one by one, if previous value big then current value, insert this index.
	 * 
	 *  
	 * NOTE:  compare(n*(n-1)/2), no move.
	 *        compare(n*(n-1)/2), every compare need to move, move(n)
	 *  
	 * Exp
	 *o. 	60--38--15--75--51--
	 *1. 	38--60--15--75--51--
	 *2. 	15--38--60--75--51--
	 *3. 	15--38--60--75--51--
	 *4. 	15--38--51--60--75--
	 *5. 	15--38--51--60--75-- 
	 * 
	 * @param array
	 */
	public  static <T extends Comparable<T>> void insertUp(T[] array,boolean ascend){ 
		for(int i=1; i<array.length; i++){ 
			T toInsert = array[i];  
			int j=i;
			for(;j>0;j--){
				int compare = toInsert.compareTo(array[j-1]);
				if(compare == 0 || compare>0 == ascend){//next value big then previous value.find break.
					break;
				}
				array[j]=array[j-1];//next value less then previous value, 
			}
			array[j] = toInsert;//we find the position.
		}
	}
	
	/**
	 * Shell Up
	 * 
	 * this sort is the upgrade of insert up, i agree. [group is big, fix need to move so many postions]
	 * 
	 * first group all data as multiple parts, then sort one group by one group, final collect all together.
	 * 
	 * 1. we set index i 's left is sorted, to find the i the index.
	 * 2. we will be compare i's left's data one by one, if previous value big then current value, insert this index.
	 * 
	 *  
	 * NOTE:  compare(n*(n-1)/2), no move.
	 *        compare(n*(n-1)/2), every compare need to move, move(n)
	 * 
	 * @param array
	 */
	public  static <T extends Comparable<T>> void shellUp(T[] array,boolean ascend){ 
		 int length = array.length;  
		 int gap = 1; 
		 while (gap < length / 3) {  
			 gap = gap * 3 + 1;  
		 }  
		 while (gap >= 1) {  
			 for (int i = gap; i < length; i++) {  
				 T next = array[i];  
				 int j = i;  
				 while (j >= gap) {  
					 int compare = next.compareTo(array[j - gap]);  
					 // already find its position  
					 if (compare == 0 || compare > 0 ==ascend) {  
						 break;  
					 }  
					 array[j] = array[j - gap];  
					 j -= gap;  
				 }  
				 if (j != i) {  
					 array[j] = next;
				 }  
			 }  
			 gap /= 3;  
		 }  
	}
	
	/**
	 * quick up
	 * 
	 * C.A.R.Hoare generator in 1962. split sort data as two part, one part of the data is less than other part.
	 * recursive this round,end with two element, one is less than other.
	 * 
	 * 1. get one of the list as the center (example first one)
	 * 2. if the element lesser then it, put to left position.(high-- as index)
	 * 3. if the element bigger then it, put to right position.(low++ as index)
	 * 4. re-pick one of the left list as the center(first one)[2,3]
	 * 5. re-pick one of the right list as the center(first one)[2,3]
	 * 6. until every table have only one element, it is end.
	 * 
	 * you can think as find first people(with NO) as center, make two middle people, one is at end of the list,
	 * one is at begin of the list
	 * 1. first call first people to go temp.
	 * 2. right one find people less then x[0], if find x[a], call him to x[0].[high:a]
	 * 3. left one find people bigger then x[0], if find x[b], call him to x[a].[low:b]
	 * 4. if a<b, right one continue, then left one, until a<b. skip out.
	 * 5. set a[l] to temp. then the list is x[0...l-1] is less then x[l+1,hight], middel is x[l].
	 * 6. condition round. sort by multiple part.
	 * 
	 * NOTE:  compare(n*(n-1)/2), no move.
	 *        compare(n*(n-1)/2), every compare need to move, move(n)
	 * 
	 *o. 	60--38--15--75--51--
	 *1. 	51--38--15--60--75--
	 *2. 	15--38--51--60--75--
	 *3. 	15--38--51--60--75--
	 *4. 	15--38--51--60--75--
	 *5. 	15--38--51--60--75--
	 * 
	 * @param x
	 * @return
	 */
	public static int[] quickUp(int [] x){  
		if(x.length>0){  
		    quicksort(x,0,x.length-1);  
		 }   
		return x;  
	}  
	 
	public static void quicksort(int [] x,int low,int high){ 
		if(low<high){  
			int middle=getmiddle(x,low,high);  
			quicksort(x,0,middle-1);  
			quicksort(x,middle+1,high);  
		}  
	}  
	
	public static int getmiddle(int [] x,int low,int high){  
		int temp=x[low];// pick first element as middle.  
		while(low<high){// all iterator.   
		   while(low<high&&x[high]>=temp){// if element bigger then the middle, no change.
		      high--;   
	       }  
		   x[low]=x[high];//(x[low]>x[high]) set the x[low] as x[high]
		   while(low<high&&x[low]<=temp){// if element lesser then the middle, no change.  
		      low++;  
		      
		   }  
		   x[high]=x[low];//(x[low]>x[high])   
		}  
		x[low]=temp;// put the middle value as x[low]
		return low;  
	}
}