package com.victor.sort.algorithms;import java.util.ArrayList;import com.victor.sort.seeds.FewUniqueKeys;import com.victor.sort.seeds.NearSorted;import com.victor.sort.seeds.Random;import com.victor.sort.seeds.Reversed;import com.victor.sort.seeds.Seeds;/** * 根排序 * @author 黑妹妹牙膏 * */public class Radix extends SortAlgorithms {	/**	 * (non-Javadoc)	 * @see com.victor.sort.algorithms.SortAlgorithms#_sort(java.util.ArrayList)	 	A: array d: The number of the highest digits	 	RADIX-SORT(A,d)	 		for i<- i to d	 			do use a stable sort to sort array A on digit i	 */		@SuppressWarnings("unchecked")	@Override	protected ArrayList
    
      doSort(ArrayList
     
       Alist) {		ArrayList
      
        a = (ArrayList
       
        )Alist.clone();		for(int i=(a.size()-1)/2;i>=0;i--)		{			a = sink(a,i,a.size());		}		int max = a.get(0);		int d = (max+"").length();		for(int i=1;i<=d;i++)		{			a = _Insertion(a,i);		}		return a;	}		protected ArrayList
        
          _Insertion(ArrayList
         
           Alist,int i) { ArrayList
          
            a = Alist; int n = a.size(); int k; for(int j=1;j
           
            0 && getRadix(temp,i)
            
              sink(ArrayList
             
               a,int i,int n) { //get left child int lc = 2 * i + 1; if(lc >= n) return a; //get right child int rc = lc + 1; //get max of left and right child int mc = (rc >= n) ? lc : (a.get(lc) > a.get(rc) ? lc : rc); // if parent > max of child then return if(a.get(i) >= a.get(mc)) return a; //swap max and parent int temp = a.get(i); a.set(i, a.get(mc)); a.set(mc, temp); moveMentIncrease(); return sink(a,mc,n); } @Override public String getName() { return "Radix"; } public static void main(String[] args) { Seeds seed1 = new Random(); Seeds seed2 = new NearSorted(); Seeds seed3 = new Reversed(); Seeds seed4 = new FewUniqueKeys(); SortAlgorithms SA = new Radix(); SA.sort(seed1,10000);// SA.print(); SA.sort(seed2,10000); SA.sort(seed3,10000); SA.sort(seed4,10000); }}